Pertemuan 2-Linked List Implementation I-2101655475-Daniel Yuan Markus

LINKED LIST

Linked List adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat dari record selanjutnya.

- Linked List lebih efisien dalam penggunaan memori, karena ketika kita hendak menyimpan data, baru kemudian dia akan meminta memorinya.
- Linked List akan mendukung bentuk struktur data yang lain

Ada beberapa macam Linked List yaitu :
1. Single Linked List
2.  Circular Single Linked List
3. Double Linked List
4. Circular Double Linked List
5.  Header Linked List

Single Linked List

Single Linked List = Menggunakan sebuah variabel  pointer   dan Pointer next nya menunjuk ke

node selanjutnya.

Nodes = Objek yang mereferensikan dirinya sendiri

Syntax :

struct tnode{

   int value;

   struct tnode *next;

};

struct tnode *head =0;

- Single Linked List : Insert

Untuk insert ada 4 macam cara :

1. Didepan (head)

Syntax :

struct tnode * node =

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

node -> value = x; //Berarti kita isi variable value yang ada di node yang baru

node -> next = head;

head = node;

2. Dibelakang (tail)

3. Ditengah (Setelah node yang kita tentukan)

4. Ditengah (Sebelum node yang kita tentukan)

- Single Linked List : Delete

   Ada 2 kondisi yang harus kita perhatikan : Jika x ada didepan node / x tidak ada didepan node

Syntax :

struct tnode *curr = head;

//Jika x ada dibagian depan node

if(head -> value == x){

   head = head -> next; //Maka head akan pindah ke sebelahnya

   free(curr);

}

//Jika x ada dibagian belakang node

else if(tail -> value == x ){

   while (curr -> next !=tail) curr = curr-> next;

   free(tail); tail = curr;

   tail -> next = NULL;

}

//Jika x tidak ada di depan node, cari lokasinya

else{

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

   struct tnode *del = curr -> next;

   curr -> next = del -> next;

   free(del);

}

Polynomial Representation

Contoh :

Polynomial p(x) = p(x) = 8x⁵ + 7x⁶ + 4x²  + 8. Secara khusus, polynomial dibagi menjadi 2 bagian

yaitu Koefisien dan Eksponen dari suku yang bersangkutan. Maka dapat direpresentasikan seperti

berikut :

| 8 | 5 |   | -> | 7 | 6 |   | -> | 4 | 2 |   | -> | 8| 0 | x |

Circular Single Linked List

Circular Single Linked List =  Single Linked List yang pointer nextnya menunjuk pada dirinya

sendiri. 

- Jika terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node

  terdepannya sehingga Linked List tersebut berputar. 

- Node terakhir akan menunjuk lagi ke head.

Double Linked List

Double Linked List  = Memiliki 2 variabel pointer yaitu pointer yang menunjuk ke node selanjutnya

dan pointer yang menunjuk ke node sebelumnya 

Syntax :

struct tnode{

   int value;

   struct tnode *next;

   strcut tnode *prev;

};

struct tnode *head = 0;

struct tnode *tail = 0;

- Double Linked List : Insert

   Pertama, kita harus mengalokasi node baru  dan memberikan nilai kepadanya. Lalu kita hubungkan

   node tersebut dengan Linked List yang sudah ada

Syntax :

struct tnode *node =

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

 node -> value = x;

 node -> next = NULL;

 node -> prev = tail

 tail -> next = node;

 tail = node;

- Double Linked List : Delete

   Ada 4 kondisi yang perlu diperhatikan ketika "Delete":

  1. Kondisi jika Node tersebut hanya satu - satunya di Linked List

Syntax :

free(head);

head = NULL;

tail = NULL;

  2. Kondisi jika Node ada di Head

Syntax :

head = head -> next;

free (head -> prev);

head -> prev = NULL;

  3. Kondisi jika Node ada di Tail

Syntax :

tail = tail -> prev;

free (tail -> next);

tail -> next = NULL;

  4. Kondisi jika Node tidak di Head / Tail

Syntax :

struct tnode *curr = head;

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

struct tnode *a = curr;

struct tnode *del = curr -> next;

a -> next = b;

b -> prev = a;

free(del);

Circular Double Linked List

Circular Double Linked List = Terdapat node yang 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.

Header Linked List

Header Linked List = Header spesial yang terdiri dari node headernya. Jadi Linked List tersebut

tidak menunjuk pada node pertama (head) namun hanya menyimpan alamat dari node headernya.

Contoh Tanpa Header Node:

L : |   |  ->  |  ant |   |  ->  |  bat  |   |  -> | cat |  \  |

Contoh dengan Header Node : 

L : |   |  ->   |       |     |  ->  |  ant |   |  ->  |  bat  |   |  -> | cat |  \  |