LIST Dewi Sartika, M.Kom
PENDAHULUAN
Linked List adalah sejumlah objek yang dihubungkan (linked) satu dengan yang lainnya membentuk suatu list. Objek adalah gabungan dari beberapa data (variable) yang dijadikan satu kelompok (tipe data bentukan) Untuk menghubungkan beberapa objek diperlukan setidaknya satu buah pointer
Dewi Sartika, M.Kom
CONTIGUOUS LIST (ARRAY)
Array adalah sejumlah objek yang saling bersambung antara satu dengan lainnya. Pengalokasian array bersifat statis karena jumlah elemennya tetap tidak dapat ditambah maupun dihapus sewaktu proses sedang berlangsung (running).
ARRAY A
20
45
25
Dewi Sartika, M.Kom
55
LINKED LIST 30 KET :
1 20
30
45 2
DATA
3
POINTER
55 5 25 4 30
20 1
45 2
25 3
55 4
Dewi Sartika, M.Kom
5
LINIER SINGLY-LINKED LIST LAST
FIRST 20
45
25
55
Simpul pertama dalam list akan ditunjuk oleh pointer FIRST Simpul terakhir dalam list akan ditunjuk oleh pointer LAST. Pointer NEXT dari simpul terakhir ini akan berisikan NULL yang menandakan bahwa tidak ada lagi simpul selain simpul tersebut. Dewi Sartika, M.Kom
Deklarasi Simpul
Simpul merupakan tipe data bentukan yang terdiri dari info untuk menyimpan data/nilai dan pointer next yang dipakai untuk menunjukkan alamat dari simpul selanjutnya P
Struct simpul { int info; struct simpul *next; }; simpul *P, *first, *last;
X
P->info
Dewi Sartika, M.Kom
P->next
Inisialisasi List
Inisialisasi list bertujuan untuk memberikan nilai awal pada suatu list yang masih kosong. Inisialisasi dilakukan menggunakan prosedur
void awal() { first = null; }
FIRST
Dewi Sartika, M.Kom
Membuat Sebuah Simpul
Gunakan pointer *P yang sudah dideklarasikan untuk menunjuk sebuah simpul baru. Setiap simpul dibuat satu per satu yang nanti akan dihubungkan menjadi sebuah list. jumlah simpul tidak ada batasnya, selama ruang memori masih tersedia maka simpul baru masih bisa dibuat. Jika ruang memori sudah penuh, maka pembuatan simpul dinyatakan gagal. Setiap pembuatan simpul akan dilakukan pengecekan terhadap pointer *P, jika berisi NULL maka pembuatan simpul dinyatakan gagal Dewi Sartika, M.Kom
Membuat Sebuah Simpul (Lanjutan) void buat_simpul(int x) { P = (simpul*) malloc (sizeof(simpul)); if (P != null) { P->info = x; } else { cout<<“Pembuatan simpul gagal”; } } Dewi Sartika, M.Kom
Pembuatan Simpul Awal
Pembuatan simpul awal dilakukan setelah berhasil membuat sebuah simpul baru. Untuk membuat simpul awal, digunakan pointer *first yang sudah dideklarasikan sebelumnya. Lakukan pemeriksaan terhadap pointer *first, jika tidak berisi null berarti list sudah ada.
Dewi Sartika, M.Kom
Pembuatan Simpul Awal (lanjutan) void simpul_awal() { last if(first == null) first P { first = p; last = p; p->next = null; } else { cout<<“linked list sudah ada”; } }
X
Dewi Sartika, M.Kom
Insert
Insert adalah proses menambah atau menghubungkan list yang sudah ada dengan sebuah simpul baru Insert kanan adalah menambahan simpul baru diakhir list sehingga simpul baru tersebut akan menjadi simpul akhir list (penggunaan pointer last) Insert kiri adalah menambahkan simpul baru diawal list sehingga simpul tersebut menjadi simpul awal list (penggunaan pointer first) Insert tengah adalah menambahkan simpul baru ditengahtengah list (penggunaan pointer tambahan)
Dewi Sartika, M.Kom
Insert Kanan first
last
25
P
12
first
30
last
25
12
Dewi Sartika, M.Kom
30
Insert Kanan (Lanjutan)
Syarat : list harus sudah ada, minimal 1 simpul (first tidak null)
void insert_kanan() { if(first !=null) { last->next = P; last = P; P->next = null; } else {cout<<“list belum ada”;} } Dewi Sartika, M.Kom
Insert Kiri first
last
25
P
12
first
30
last
30
25
Dewi Sartika, M.Kom
12
Insert Kiri (Lanjutan)
Syarat : list harus sudah ada, minimal 1 simpul (first tidak null)
void insert_kiri() { if(first !=null) { P->next = first; first = P; }
else { cout<<“list belum ada”; } }
Dewi Sartika, M.Kom
Insert Tengah first
Q
25
last
P
30
12
8
first last
25
30
8
12
Dewi Sartika, M.Kom
Insert Tengah (Lanjutan)
Syarat : list harus sudah ada, minimal 1 simpul (first tidak null) Deklarasikan pointer tambahan bernama pointer *Q dengan tipe simpul (karena akan menunjuk simpul) Lakukan penempatan pointer *Q pada simpul sebelum simpul baru akan diinsertkan
Dewi Sartika, M.Kom
Insert Tengah (Lanjutan) void insert_tengah(int n) { int i; Q = first; for(i=1;i
next; } P->next = Q->next; Q->next = P; } Dewi Sartika, M.Kom
Delete
Delete adalah proses menghapus sebuah simpul yang ada didalam list Delete kanan adalah menghapus simpul paling kiri didalam list sehingga pointer last akan menunjuk ke simpul sebelumnya. Delete kiri adalah menghapus simpul paling kiri didalam list sehingga pointer first akan menunjuk ke simpul setelahnya. Delete tengah adalah menghapus simpul yang bukan merupakan simpul awal maupun akhir
Dewi Sartika, M.Kom
Delete Kanan
Deklarasikan pointer tambahan bernama pointer *Q dengan tipe simpul (karena akan menunjuk simpul) Lakukan penempatan pointer *Q pada simpul sebelum simpul akhir.
Dewi Sartika, M.Kom
Delete Kanan (Lanjutan) first
Q
last free 25
30
first
8
12
last
25
30
8
Dewi Sartika, M.Kom
Delete Kanan (Lanjutan) void delete_kanan() { Q = first; while(Q->next != last) {Q = Q->next;} free(last); last = Q; last->next = null; }
Dewi Sartika, M.Kom
Delete Kiri
Deklarasikan pointer tambahan bernama pointer *Q dengan tipe simpul (karena akan menunjuk simpul) Lakukan penempatan pointer *Q pada simpul first yang akan dihapus, sehingga pointer *first dapat dipindahkan pada simpul setelahnya.
Dewi Sartika, M.Kom
Delete Kiri (Lanjutan) Q
first
last free 25
30
first
8
12
last
30
8
12
Dewi Sartika, M.Kom
Delete Kiri (Lanjutan) void delete_kiri() { Q = first; first = Q->next; free(Q); }
Dewi Sartika, M.Kom
Delete Tengah
List minimal memiliki lebih dari 2 simpul. Deklarasikan pointer tambahan bernama pointer *Q dan pointer *R dengan tipe simpul (karena akan menunjuk simpul) Lakukan penempatan pointer *Q pada simpul sebelum simpul yang akan dihapus. Pointer *R digunakan untuk menunjuk simpul yang akan dihapus.
Dewi Sartika, M.Kom
Delete Tengah (Lanjutan) first
Q
R
last
free 25
30
first
8
12
last
25
30
12
Dewi Sartika, M.Kom
Delete Tengah (Lanjutan) void delete_tengah(int n) { int i; Q = first; for(i=1;inext;} R = Q->next; Q->next = R->next; free(R); } Dewi Sartika, M.Kom
Selesai Terus berlatih!!
Dewi Sartika, M.Kom
