Linked List

Apa itu Linked List ?

Linked List adalah struktur data yang terdiri dari urutan rekaman data sehingga setiap catatan ada bidang yang berisi referensi ke catatan berikutnya dalam urutan.

Linked list berfungsi untuk menampung data lebih dari satu, kita dapat menggunakan array dalam program kita. Tapi array memesan memori secara statis

Linked List dibagi menjadi 2 jenis :

1. Singly Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya, biasanya field pada tail menunjuk ke NULL.
2. Doubly Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

CARA MENGGUNAKAN UNTUK MEMASUKAN DATA:

Singly Linked List

• pertama-tama kita perlu mendefinisikan struktur node untuk daftar.
• Misalkan kita ingin membuat daftar bilangan bulat.

struct tnode { 

int value; 

struct tnode *next; 

}; 

struct tnode *head = 0; 

head diatas merupakan pointer.

• Untuk menyisipkan nilai baru, pertama-tama kita harus secara dinamis mengalokasikan node baru dan menetapkan nilai padanya lalu menghubungkannya dengan daftar yang ada.
• Misalkan kita ingin menambahkan node baru di depan head.

 struct tnode *node =  

(struct tnode*) malloc(sizeof(struct tnode)); 

 node->value = x; 

 node->next  = head; 

 head = node;

operator diatas sama halnya dengan :

(*node).value = x; 

(*node).next  = head;

Tambahkan node baru di depan head. Dengan asumsi mengandung 10, 35, 27.

Doubly Linked list

• Sama seperti dalam Singly Linked List , pertama-tama kita harus mengalokasikan node baru dan menetapkan nilainya, dan kemudian kita menghubungkan node dengan daftar yang ada.
• Misalkan kita ingin menambahkan node baru di belakang tail. 

struct tnode *node =   

 (struct tnode*) malloc(sizeof(struct tnode));

node->value = x; 

node->next  = NULL;

node->prev  = tail; 

tail->next  = node;  

tail = node;

• Misalkan kita ingin menyisipkan simpul baru di posisi tertentu (setiap lokasi antara head dan tail) 

struct tnode *a = ??;

struct tnode *b = ??;

// node baru akan dimasukan diantara a dan b

struct tnode *node =

    (struct tnode*) malloc(sizeof(struct tnode));

node->value  = x;

node->next  = b;

node->prev  = a;

a->next  = node;

b->prev  = node;

CARA MENGGUNAKAN UNTUK MENGHAPUS DATA :

Singly Linked List

• Pertama-tama kita harus menemukan lokasi node yang menyimpan nilai yang ingin kita hapus, memindahkan, dan menghubungkan daftar yang tersisa. 

• Misalkan nilai yang ingin kita hapus adalah x dan anggap x ada dalam daftar tertaut dan unik.

• Ada dua kondisi yang harus kita perhatikan:

• jika x ada di head node.
• jika x tidak dalam head node. 

 struct tnode *curr = head; 

   // jika x di head node 

if ( head->value == x ) {  

head = head->next; 

          free(curr); 

}

// jika x tidak di head node(mencari lokasi) 

   else { 

   while ( curr->next->value != x )  

   curr = curr->next; 

   struct tnode *del = curr->next;

   curr->next = del->next; 

   free(del);

   } 

• Menghapus 31 (terletak di head)

• Menghapus 35 (tidak terletak di head)

Doubly Linked List

• Untuk menghapus data di Doubly Linked List ada 4 kondisi yang harus diperhatikan :

• Node yang akan dihapus adalah satu-satunya simpul dalam daftar tertaut.

  free(head);

  head = NULL;

  tail = NULL; 

• Node yang akan dihapus adalah head.

   head = head->next;
   free(head->prev);
  head->prev = NULL;

• Node yang akan dihapus adalah tail.

     tail = tail->prev;
  free(tail->next);
  tail->next = NULL;

• Node yang akan dihapus bukan head atau tail.

   struct tnode *curr = head;
    while ( curr->next->value != x ) 
    curr = curr->next;

    struct tnode *a   = curr;

    struct tnode *del = curr->next;

    struct tnode *b   = curr->next->next;

    a->next = b;

    b->prev = a;

    free(del);

Kalian dapat juga belajar melalui video yang telah saya berikan.


Mohon maaf, Jika pembahasan kurang lengkap dan memiliki banyak kesalahan dalam penulisan. Demikian pembahasan tentang Linked List.

Terima kasih.