DATA STRUCTURES

Linked List

Linked List atau senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya. Elemen data yang dihubungkan dengan dengan link pada Linked List disebut Node. Di dalam Linked List, biasanya terdapat Head yang merupakan elemen yang berada pada posisi pertama dalam suatu Linked List dan Tail yang merupakan elemen yang berada pada posisi terakhir dalam suatu Llinked List.

Meski memiliki konsep yang mirip dengan Array, Linked List memiliki keuntungan dalam penyisipan dan pembuangan data dibandingkan Array. Hanya saja, kelemahannya terletak pada cara mengakses data didalamnya. Pada konsep Linked List, pengaksesan data didalamnya harus secara berurutan dari awal, hal ini dikarenakan linked list tidak mengenal indeks seperti Array.

Jika pada Array dikenal istilah index (indeks), maka Linked List mengenal istilah nodes atau titik. Hal ini terjadi karena Linked List menggunakan alokasi memori yang selalu berbeda dan menghubungkannya dengan memory address yang lain, sehingga kita akan lebih mudah memahaminya dengan nodes.

Macam-macam Linked List: 

1. Circular Single Linked List

Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,  maka pointer next pada node terakhir akan menunjuk ke node terdepannya. Circular  artinya pointer nextnya akan menunjuk pada dirinya sendiri sehingga berbentuk seperti berputar. Single Linked List hanya memiliki satu variabel pointer saja. Biasanya field pada tail menunjuk ke NULL. Contoh:

typedef struct TNode{ 

int data; 

TNode *next; 

};

2. Doubly Linked List

Doubly Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu prev dan next. Doubly Linked List memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list. Operasi pada Doubly Linked List: 

        1. Insert

struct tnode *a = ??;

struct tnode *b = ??;

// the new node will be inserted between a and 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;

2. Delete

          -   If the node to be deleted is the only node:

         free(head);

     head = NULL;

     tail = NULL;

    -    If the node to be deleted is head:

     head = head->next;

     free(head->prev);

     head->prev = NULL;

    -   If the node to be deleted is tail:

            tail = tail->prev;

      free(tail->next);

      tail->next = NULL;

         -   If the node to be deleted is not in head or 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);

 Contoh:

struct tnode {

  int value;

  struct tnode *next;

  struct tnode *prev;

  };

struct tnode *head = 0;

struct tnode *tail = 0;

3. Circular Doubly Linked List

Circular Doubly Linked List mirip dengan Single Linked List, namun jumlah pointer pada setiap node adalah 2. Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & 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.

Contoh: 
#include <stdio.h>
struct TNode{
char data[30];
TNode *next;
TNode *prev;
};

4.Multiple Linked List

Multiple linked list merupakan senarai berantai yang memiliki link atau pointer lebih darisatu. Untuk multiple linked list yang memiliki dua link biasanya disebut sebagai doublylinked list (senarai berantai ganda). Senarai berantai ganda memiliki dua buah pointer yang biasanya masing-masing menunjuk ke simpul sebelumnya dan ke simipul sesudahnya.