Senarai / Link List

Daftar bertaut atau kadang-kadang disebut dengan senarai bertaut atau senarai berantai dalam ilmu komputer merupakan sebuah struktur data yang digunakan untuk menyimpan sejumlah objek data biasanya secara terurut sehingga memungkinkan penambahan, perulangan, dan pencarian atas elemen data yang tersimpan dalam daftar dilakukan secara lebih efektif.
Pada praktiknya sebuah struktur data memiliki elemen yang terdapat pada daftar abstrak ini seringkali disebut sebagai node. karena mekanisme rujukan yang saling terkait inilah disebut daftar berantai.
Daftar berantai merupakan bentuk struktur data paling umum dan sederhana yang banyak digunakan untuk mengimplementasikan model struktur data lainnya, termasuk antrian, stack, ataupun larik assosiatif.

• Setiap elemen (node) dari suatu linked list terdiri atas dua bagian, yaitu :
  1. INFO
     berisi informasi tentang elemen data yang bersangkutan
  2. NEXT
     (link field/next pointer field), berisi alamat dari elemen (node) selanjutnya yang dituju.

Berikut ini sebuah contoh linked list yang terdiri atas 4 node :

Pada node ke-4 field NEXT-nya berisi NULL, artinya node ke-4 tsb. adalah node terakhir.

Node-node dalam linked list tidak harus selalu digambarkan paralel seperti pada gambar diatas. Linked list pada contoh diatas dapat pula digambarkan seperti berikut ini :

CATATAN :
Ada dua hal yang menjadi kerugian dengan representasi suatu data dengan linked list ini, yaitu :

1. Diperlukan ruang tambahan untuk menyatakan/tempat field pointer.
2. Diperlukan waktu yang lebih banyak untuk mencari suatu node dalam linked list.

Sedangkan keuntungannya adalah :

1. Jenis data yang berbeda dapat di-link.
2. Operasi REMOVE atau INSERT hanya dilakukan dengan mengubah pointer-nya saja.

OPERASI DASAR PADA LINKED LIST.
Ada beberapa aturan yang didefinisikan pada operasi didalam linked list, yaitu :

• Jika P adalah suatu variabel pointer, maka nilainya adalah alamat atau lokasi dari variabel lain yang dituju.
• Operasi yang didefinisikan pada suatu variabel pointer adalah :
  
  1. Test apakah sama dengan NULL.
  2. Test untuk kesamaan dengan variabel pointer lain.
  3. Menetapkan sama dengan NULL.
  4. Menetapkan menuju ke node lain.

Notasi yang didefinisikan sehubungan dengan operasi diatas adalah :

1. NODE(P), artinya node yang ditunjuk oleh pointer P.
2. INFO(P), artinya nilai INFO dari node yang ditunjuk pointer P.
3. NEXT(P), artinya hubungan (link) selanjutnya dari node yang ditunjuk oleh pointer P.

Sebagai contoh, perhatikan linked list dibawah ini :

NODE(P) = node yang ditunjuk oleh P yaitu node pertama.
INFO(P) = A
NEXT(P) = node ke-dua
INFO(NEXT(NEXT(P))) = C


Operasi-Operasi yang ada pada Linked List

1. Insert
   Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
2. IsEmpty
   Fungsi ini menentukan apakah linked list kosong atau tidak.
3. Find First
   Fungsi ini mencari elemen pertama dari linked list
4. Find Next
   Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
5. Retrieve
   Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
6. Update
   Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu
7. Delete Now
   Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
8. Delete Head
   Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
9. Clear
   Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.

Operasi-operasi untuk Stack dengan Linked List

1. IsEmpty
   Fungsi memeriksa apakah stack yang adamasih kosong.
2. Push
   Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.
3. Pop
   Fungsi ini mengeluarkan elemen teratas dari stack.
4. Clear
   Fungsi ini akan menghapus stack yang ada.

Operasi-operasi Queue dengan Double Linked List

1. IsEmpty
   Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.
2. IsFull
   Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.
3. EnQueue
   Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).
4. DeQueue
   Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).

MENGHAPUS SUATU NODE DARI LINKED LIST (REMOVE).
Untuk menghapus node dalam linked list digunakan procedure FREENODE. Jika Q adalah suatu variabel pointer, maka FREENODE(Q) akan menyebabkan node yang ditunjuk oleh variabel pointer Q dihapus dari linked list.
Perhatikan linked list berikut :

• langkah ke-1 :
  Q := Next(P)
  
  
  
  
  
• langkah ke-2 :
  Next(P) := Next(Q)
  
  
  
  
  
• langkah ke-3 :
  Freenode(Q)

procedure Freenode(Q)

• Next(Q) := Avail
  
  
  
  
  
• Info(Q) := Null


• Avail := Q
  
  
  

Contoh Coding Linked List Sederhana C++ :

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

typedef struct simpul {
 char nama[20];
 float nilai;
 struct simpul *next_simpul;
} simpulku;
 void main(){
  simpulku *simpul1, *simpul2, *simpul3, *simpul4, *temp;
  //alokasikan memorinya dulu
  simpul1 = (simpulku *)malloc(sizeof(simpulku));
  simpul2 = (simpulku *)malloc(sizeof(simpulku));
  simpul3 = (simpulku *)malloc(sizeof(simpulku));
  //isi data masing2 simpul
  strcpy(simpul1->nama, "Amin");
  strcpy(simpul2->nama, "Budi");
  strcpy(simpul3->nama, "Citra");
  simpul1->nilai=90; simpul2->nilai=20;
  simpul3->nilai=100;
  simpul1->next_simpul = NULL;
  //sambungkan link masing2 simpul
  simpul1->next_simpul = simpul2;
  simpul2->next_simpul = simpul3;
  simpul3->next_simpul = NULL;
  //tampilkan hasilnya, mulai dr simpul 1
  temp = simpul1; //cara satu per satu
  printf("%s, %f\n", temp->nama, temp->nilai);
  temp = temp->next_simpul;
  printf("%s, %f\n", temp->nama, temp->nilai);
  temp = temp->next_simpul;
  printf("%s, %f\n", temp->nama, temp->nilai);
  printf("\n");
  temp = simpul1;

   for(;temp!=NULL; temp=temp->next_simpul) //cara looping
    printf("%s, %f\n", temp->nama, temp->nilai);
    //skenario menambahkan simpul baru
    simpul4 = (simpulku *)malloc(sizeof(simpulku)); //siapkan
    strcpy(simpul4->nama, "Dewi");simpul4->nilai=80; //isi
    simpul2->next_simpul = simpul4; //update link
    simpul4->next_simpul = simpul3;
    printf("\n");
    temp = simpul1;
     for(;temp!=NULL; temp=temp->next_simpul) //cara looping
     printf("%s, %f\n", temp->nama, temp->nilai);
     //menghapus simpul budi
     simpul1->next_simpul = simpul4; //update link
     free(simpul2); //hapus simpul
     printf("\n");
     temp = simpul1;
      for(;temp!=NULL; temp=temp->next_simpul) //cara looping
      printf("%s, %f\n", temp->nama, temp->nilai);
 }

Sumber :
Definisi
Dokumen
Coding