Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambung-menyambung, dinamis dan terbatas.

Linked List saling terhubung dengan bantuan variabel pointer

Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.

Singly Linked ListLinier circular

Doubly Linked ListLinier Circular

Pengertian:Single : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULLLinked List : artinya node-node tersebut saling terhubung satu sama lain.

Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.

Definisi Nodetypedef struct TNode{int data;TNode *next;};

Deklarasi Head

Dibutuhkan satu buah variabel pointer: headHead akan selalu menunjuk pada node pertama

TNode *head;

Fungsi Inisialisasi Single LinkedListvoid init(){head = NULL;}Function untuk mengetahui kosong tidaknya Single LinkedListJika pointer head tidak menunjuk pada suatu node maka kosong

int isEmpty(){if(head == NULL) return 1;else return 0;}

Penambahan node baru akan dikaitkan di node paling depan

Pada saat data masih kosong, penambahan data dilakukan dengan cara: node head ditunjukkan ke node baru tersebut.

Prinsipnya adalah mengkaitkan node baru dengan head, kemudian head akan menunjuk pada data baru tersebut.

5HeadBaru20

void insertDepan(int databaru){ TNode *baru; baru = new TNode; baru->data = databaru; baru->next = NULL; if(isEmpty()==1){ head=baru; head->next = NULL; } else {baru->next = head;head = baru; } printf(Data masuk\n);}

Penambahan data dilakukan di belakang

Jika pertama kali, node langsung ditunjuk oleh head.

membutuhkan pointer bantu untuk mengetahui node terbelakang, kemudian setelah itu, dikaitkan dengan node baru.

Untuk mengetahui data terbelakang perlu digunakan perulangan.

52025

void insertBelakang (int databaru){ TNode *baru,*bantu; baru = new TNode; baru->data = databaru; baru->next = NULL; if(isEmpty()==1){ head=baru; head->next = NULL; } else { bantu=head; while(bantu->next!=NULL){ bantu=bantu->next; } bantu->next = baru; } printf("Data masuk\n);}

void tampil(){TNode *bantu;bantu = head;if(isEmpty()==0){while(bantu!=NULL){cout

digunakan suatu pointer lain yang digunakan untuk menunjuk node yang akan dihapus, misalnya pointer hapus

Sebelum data terdepan dihapus, head harus ditunjukkan ke node sesudahnya terlebih dahulu agar list tidak putus.

menghapus pointer hapus dengan menggunakan perintah delete.

Jika head masih NULL maka berarti data masih kosong!

void hapusDepan (){TNode *hapus;int d;if (isEmpty()==0){ if(head->next != NULL){hapus = head;d = hapus->data;head = head->next;delete hapus; } else {d = head->data;head = NULL; } printf(%d terhapus\n,d);} else cout

Membutuhkan pointer bantu dan hapus.

Pointer hapus digunakan untuk menunjuk node yang akan dihapus, dan pointer bantu digunakan untuk menunjuk node sebelum node yang dihapus yang kemudian selanjutnya akan menjadi node terakhir.

Pointer bantu akan digunakan untuk menunjuk ke nilai NULL(menjadi node paling belakang yang baru).

Pointer bantu akan selalu bergerak sampai sebelum node yang akan dihapus, baru kemudian pointer hapus diletakkan setelah pointer bantu. Setelah itu pointer hapus akan dihapus, pointe bantu akan menunjuk ke NULL.

void hapusBelakang(){TNode *hapus,*bantu;int d;if (isEmpty()==0){ if(head->next != NULL){bantu = head;while(bantu->next->next!=NULL){ bantu = bantu->next;}hapus = bantu->next;d = hapus->data; bantu->next = NULL;delete hapus; } else {d = head->data;head = NULL; } printf(%d terhapus\n,d);} else printf(Masih kosong\n);}

void clear(){TNode *bantu,*hapus;bantu = head;while(bantu!=NULL){hapus = bantu;bantu = bantu->next;delete hapus;}head = NULL;}

Dibutuhkan dua buah variabel pointer: head dan tailHead akan selalu menunjuk pada node pertama, sedangkan tail akan selalu menunjuk pada node terakhir.

Inisialisasi LinkedListTNode *head, *tail;

Fungsi Inisialisasi LinkedListvoid init(){head = NULL;tail = NULL;}Function untuk mengetahui kosong tidaknya LinkedListint isEmpty(){if(tail == NULL) return 1;else return 0;}

Penambahan data baru di depan akan selalu menjadi head.void insertDepan(int databaru){ TNode *baru; baru = new TNode; baru->data = databaru; baru->next = NULL; if(isEmpty()==1){head=tail=baru;tail->next=NULL;} else {baru->next = head;head = baru; } printf(Data masuk\n);}

void tambahBelakang(int databaru){TNode *baru,*bantu;baru = new TNode;baru->data = databaru;baru->next = NULL;if(isEmpty()==1){ head=baru; tail=baru; tail->next = NULL;}else {tail->next = baru;tail=baru;} printf("Data masuk\n);}

Kelebihan dari Single Linked List dengan Head & Tail adalah pada penambahan data di belakang, hanya dibutuhkan tail yang mengikat node baru saja tanpa harus menggunakan perulangan pointer bantu.

void tampil(){TNode *bantu;bantu = head;if(isEmpty()==0){while(bantu!=NULL){printf(%d\n,bantu->data);bantu=bantu->next;}printf(\n);} else printf(Masih kosong\n);}

void hapusDepan(){TNode *hapus;int d;if (isEmpty()==0){if(head!=tail){ hapus = head; d = hapus->data; head = head->next; delete hapus;} else { d = tail->data; head=tail=NULL;}printf(%d terhapus\n,d);} else printf("Masih kosong\n);}

void hapusBelakang(){TNode *bantu,*hapus;int d;if (isEmpty()==0){bantu = head;if(head!=tail){while(bantu->next!=tail){bantu = bantu->next;}hapus = tail;tail=bantu;d = hapus->data;delete hapus;tail->next = NULL;}else {d = tail->data;head=tail=NULL;}cout

void clear(){TNode *bantu,*hapus;bantu = head;while(bantu!=NULL){hapus = bantu;bantu = bantu->next;delete hapus;}head = NULL;tail = NULL;}

Tiga langkah:

Cari dimana tempat untuk penyisipan

Buat node baru

Sisipkan node baru kedalam linked list

Untuk menyisipkan: 50Gunakan current pointer. Jika nilai X yang ingin disisipkan lebih kecil daripada nilai yang ada ( current number), maka pindahkan current pointer ke posisi berikut.

cur = head;while (X > cur->data)cur = cur->next;

50X

Problem 1: untuk melakukan penyisipan harus diketahui elemen sebelum tempat dimana item akan disisipkan

Solusi: tambahkan pointer yang selalu berada pada posisi sebelum cur

prev = NULL;cur = head;while ( X > cur data) { prev = cur; cur = cur next;}

50XNull

Problem 2: jika nilai baru X lebih besar daripada semua nilai dalam list, maka pada akhir loop akan menunjukkan

Cur->next = NULL //Akan terjadi crash!

Solusi: Periksa kondisi khusus untuk NULL.

prev = NULL;cur = head;while ((cur != NULL) && ( X > cur data)) { prev = cur; cur = cur next;}

Tempat dimana akan dilakukan penyisipan: yang ditunjuk prev .

Ditambahkan satu pointer newitem.

newitem = new node;Newitem->data = X;

50X

1) Perlu pointer dari node [41] ke node [50].2) Perlu pointer dari [50] ke [66].Pointer apa yang menunjuk ke [66]? cur !!!Newitem->next = cur;Pointer apa yang menunjuk ke [50]? newitem !!!Prev->next = newitem;

Permasalahan selanjutnya, bagaimana jika penyisipan dilakukan pada awal list, prev = NULL.

prev->next = newitem; // Akan CRASH!

if (prev != NULL) {Newitem->next = cur;Prev->next = newitem;}else {Newitem->next = head;head = newitem;}

Bagaimana jika penyisipan dilakukan ketika list masih kosong ? head harus diinisialisasi sebelum digunakan. if (head = =NULL) { head = new node; head->data = X; head->next = NULL;}

Bagaimana jika nilai yang akan disisipkan sudah ada dalam list ? if((cur = = NULL) || (X != cur->data)) // not a duplicateelse // its a duplicate

Ada 3 Langkah:

Cari dimana node yang akan dihapus.

Lewati node tsb dalam linked list.

Mengatur node jika diperlukan

Langkah 1 : Seperti pada penyisipan

Prev next = cur next;

if ((cur != NULL) && (X = = curdata)) {Prev next = cur next;Success = boolean(1);}elseSuccess = boolean(0);

Jika yang dihapus pada awal list, harus merubah head

if ((cur != NULL) && (X = curdata)) {if (prev != NULL)Prev->next = cur->next;elsehead = cur->next;Success = boolean(1);}elseSuccess = boolean(0);

Setelah dihapus, cur masih menyimpan node yang sudah dihapus.

Dari sudut pandang linked list sudah dihapus, tapi memori masih menyimpan.

Untuk Menghapus node dari memori :

delete cur;

alokasikan kembali cur untuk proses berikutnya

Menyisipkan X pada lokasi setelah current.

Newitem->next = cur->next;Cur->next=newitemcurrent

1 Buat langkah-langkah untuk memasukkan data dan menghapus data pada stack menggunakan linked list2 Buat langkah-langkah untuk memasukkan data dan menghapus data pada queue menggunakan linked list

********