Materi Struktur Organisasi Data Linked List
Hay hay sahabat blogger, balik lgi nih sama aku Ali Hanafiah jadi disini aku mau memberikan materi tentang linked list, pasti blom ada yang tau kan ? nahh langsung ajah kita ke materinya, Cekidotttt... XD
LINKED LIST
Pengertian Linked List
Salah satu bentuk struktur data yang berisi kumpulan data yang tersusun secara
sekuensial, saling bersambungan, dinamis dan terbatas adalah senarai berkait (linked list).
Suatu senarai berkait (linked list) adalah suatu simpul (node) yang dikaitkan dengan simpul yang lain dalam suatu urutan tertentu. Suatu simpul dapat berbentuk suatu struktur atau class. Simpul harus mempunyai satu atau lebih elemen struktur atau class yang berisi data. Secara teori, linked list adalah sejumlah node yang dihubungkan secara linier dengan bantuan pointer. Senarai berkait lebih efisien di dalam melaksanakan penyisipan-penyisipan dan penghapusan-penghapusan. Senarai berkait juga menggunakan alokasi penyimpanan secara dinamis, yang merupakan penyimpanan yang dialokasikan pada runtime. Karena di dalam banyak aplikasi, ukuran dari data itu tidak diketahui pada saat kompile, hal ini bisa merupakan suatu atribut yang baik juga. Setiap node akan berbentuk struct dan memiliki satu buah field bertipe struct yang sama, yang berfungsi sebagai pointer. Dalam menghubungkan setiap node, kita dapat menggunakan cara first-create-first-access ataupun first-create-last-access. Yang berbeda dengan deklarasi struct sebelumnya adalah satu field bernama next, yang bertipe struct tnode. Hal ini sekilas dapat membingungkan. Namun, satu hal yang jelas, variabel next ini akan menghubungkan kita dengan node di sebelah kita, yang juga bertipe struct tnode. Hal inilah yang menyebabkan next harus bertipe struct tnode.
infotype à sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list next à address dari elemen berikutnya (suksesor) .
Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu dengan notasi : first (L)
Sebelum digunakan harus dideklarasikan terlebih dahulu :
#define First(L) (L)
Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi : info(P)deklarasi #define info(P) P->info next(P)deklarasi #define next(P) P->next
Beberapa Definisi :
1. List l adalah list kosong, jika First(L) = Nil
2. Elemen terakhir dikenali, dengan salah satu cara adalah karena Next(Last) = Nil Nil adalah pengganti Null, perubahan ini dituliskan dengan #define Nil Null
Single linked list adalah apabila hanya ada satu pointer yang menghubungkan setiap node (satu arah “next”).
1. Single Linked List non Circular
Pembuatan struct bernama tnode berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari tnode.
Deklarasi node dengan struct:
Asumsikan kita memiliki sejumlah node yang selalu menoleh ke sebelah dalam arah yang sama. Atau, sebagai alat bantu, kita bisa mengasumsikan beberapa orang yang bermain kereta api. Yang belakang akan memegang yang depan, dan semuanya menghadap arah yang sama. Setiap pemain adalah node. Dan tangan pemain yang digunakan untuk memegang bahu pemain depan adalah variabel next. Sampai di sini, kita baru saja mendeklarasikan tipe data dasar sebuah node. Selanjutnya, kita akan mendeklarasikan beberapa variabel pointer bertipe struct tnode. Beberapa variabel tersebut akan kita gunakan sebagai awal dari linked list, node aktif dalam linked list, dan node sementara yang akan digunakan dalam pembuatan node di linked list. Berikan nilai awal NULL kepada mereka. Deklarasi node untuk beberapa keperluan, seperti berikut ini:
struct tnode *head=NULL, *curr=NULL, *node=NULL;
Dengan demikian, sampai saat ini, telah dimiliki tiga node. Satu sebagai kepala (head), satu sebagai node aktif dalam linked list (curr) dan satu lagi node sementara (node). Untuk mempermudah pengingatan, ingatlah gambar anak panah yang mengarah ke kanan. Head akan berada pada pangkal anak panah, dan node-node berikutnya akan berbaris ke arah bagian anak panah yang tajam.
Apabila diperhatikan, setiap node memiliki petunjuk untuk node sebelahnya. Node terakhir akan diberikan nilai NULL. Dengan demikian, setiap node kebagian jatah.
Berikut adalah penjelasan kode-kode pembuatan singly linked list tersebut. Pertama-tama, akan dibuat perulangan dari 0 sampai 4, yang dimaksudkan untuk membuat lima buah node yang masing-masing field data nya berisikan nilai dari 0 sampai 4. Pembuatan node dilakukan dengan fungsi malloc().
Setelah itu, perlu dibuat node dan penghubung. Pertama-tama, akan diuji apakah head bernilai NULL. Kondisi head bernilai NULL hanya terjadi apabila belum dimiliki satu node pun. Dengan demikian, node tersebut akan dijadikan sebagai head. Node aktif (curr), juga kita dapat dari node tersebut. Kalau head tidak bernilai NULL alias telah dimiliki satu atau lebih node, yang pertama dilakukan adalah menghubungkan pointer next dari node aktif (curr) ke node yang baru saja dibuat. Dengan demikian, baru saja dibuat penghubung antara rantai lama dengan mata rantai baru. Atau, dalam permainan kereta api, pemain paling depan dalam barisan lama akan menempelkan tangannya pada bahu pemain yang baru bergabung. Node aktif (curr) kemudian dipindahkan ke node yang baru dibuat.
2. Single Linked List Circular
Hampir sama dengan single linked list non circular, bahwa dibutuhkan sebuah kait untuk menghubungkan node-node data yang ada, dimana pada node terakhir atau tail yang semula menunjukkan NULL diganti dengan menunjuk ke kepala atau head. Dimana inisialisasi senarai berkait tunggal sirkular menggunakan struc adalah sebagai berikut:
Deklarasi Single Linked List Circular:
Menambah node dan membuat tail dari single linked list circular
Deklarasi penambahan node baru:
Void main(){
node = new tnode;
tail = new tnode;
node->next = head->next;
head->next = node;
tail = node;
}
Menyisipkan Node baru
Deklarasi menyisipkan node baru menggunakan sintak berikut:
Void main()
{
node = new tnode;
node->next = head->next;
head->next = node;
}Menghapus Node dari Single Linked List Circular
Deklarasi menghapus node dari single linked list circular, menggunakan sintaks berikut:
Void main()
{
hapus = new tnode;
if( head != tail)
{
hapus = head;
head = head->next;
tail->next = head;
delete hapus;
}else
{
head = NULL;
tail = NULL;
}
}
b. Double Linked List (Senarai berkait ganda)
Double Linked List adalah elemen-elemen yang dihubungkan dengan dua pointer dalam satu elemen dan list dapat melintas baik di depan atau belakang. Elemen double linked list terdiri dari tiga bagian :
1. Bagian data informasi2. Pointer next yang menunjuk ke elemen berikutnya
3. Pointer prev yang menunjuk ke elemen sebelumnya
Double Linked List non Circular
Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya dan ke node sebelumnya. Untuk pembentukan node baru, mulanya pointer next dan prev akan menunjuk ke nilai NULL. Selanjutnya, pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node selanjutnya pada list.
Deklarasi node dibuat dari struct berikut ini :typedef struct TNode{
int data;
Tnode *next;
Tnode *prev;
};
Deklarasi Pointer Penunjuk Kepala Double Linked List
Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju, melainkan harus melalui node pertama dalam linked list. Deklarasinya sebagai berikut:
Function untuk mengetahui kosong tidaknya DLLNC
int isEmpty(){
if(head == NULL) return 1; else return 0;
}
Penambahan data di depan
Penambahan node baru akan dikaitkan di ode paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head-nya. Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir dengan node terdepan dibutuhkan pointer bantu.
Fungsi Menambah Di Depan
void insert Depan (int databaru){ TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
baru->prev = NULL;
if(isEmpty()==1){
head=baru;
head->next = NULL;
head->prev = NULL;
}
else {
baru->next = head;
head->prev = baru;
head = baru;
}
cout<<”Data masuk\n”;
}
Penambahan data di belakang
Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya. Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.
Fungsi penambahan Node ke belakang :
Ilustrasi Penambahan Node di Belakang
Fungsi untuk menghapus node terbelakang
Ilustrasi Penghapusan Node
Menghapus Node Double Linked List
Tidak diperlukan pointer bantu yang mengikuti pointer hapus yang berguna untuk menunjuk ke NULL. Karena pointer hapus sudah bisa menunjuk ke pointer sebelumnya dengan menggunakan elemen prev ke node sebelumnya, yang akan diset agar menunjuk ke NULL setelah penghapusan dilakukan.
Fungsi Menghapus Semua Elemen
Double Linked List Circular
Double Linked List Circular (DLLC) adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut dengan pointer next dan pre-nya menunjuk ke dirinya sendiri secara circular.
Ilustrasi DLLC
Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya dan ke node sebelumnya. Untuk pembentukan node baru, mulanya pointer next dan prev akan menunjuk ke dirinya sendiri. Jika sudah lebih dari satu node, maka pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node sesudahnya.
Deklarasi dan Node baru DLLC
Pembentukan node baru
Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya.
TNode *baru;
baru = new TNode; baru->data = databaru; baru->next = baru; baru->prev = baru;
Penambahan data di depan
Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head nya. Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir dengan node terdepan dibutuhkan pointer bantu.
void insertDepan(int databaru){
TNode *baru, *bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
baru->prev = baru;
if(isEmpty()==1){
head=baru;
head->next = head;
head->prev = head;
}
else {
}
bantu = head->prev;
baru->next = head;
head->prev = baru;
head = baru;
head->prev = bantu;
bantu->next = head;
cout<<"Data masuk\n";
}
Penambahan data di belakang
Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya. Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.
void insertBelakang (int databaru){
Tnode *baru, *bantu;
baru = new Tnode;
baru->data = databaru;
baru->next = baru;
baru->prev = baru;
if(isEmpty()==1){
head=baru;
head->next = head;
head->prev = head;
}
else{
bantu=head->prev;
bantu->next = baru;
baru->prev = bantu;
baru->next = head;
head->prev = baru;
}
Cout<<”Data masuk\n”;
}
Function untuk menampilkan isi linked list
Function untuk menghapus node terbelakang
Function untuk menghapus node terbelakang
0 komentar :
Posting Komentar