Linked List Rangkuman | Computer Science

Linked List Rangkuman
Jeysen Liemuel - 2301850632
CC01 - LS01

Linked List
Linked list yang juga dikenal dengan senarai berantai adalah struktur data linear (seperti array) yang terdiri dari catatan data sehingga setiap catatan data ada bidang yang berisi referensi ke catatan berikutnya dalam urutan. Tetapi Linked List tidak seperti array karena dalam Linked List elemen tidak disimpan dalam lokasi yang berurutan, elemen - elemennya dihubungkan dengan pointer.

Mengapa menggunakan Linked List? Berikut adalah beberapa perbedaan antara Linked List dan array:

Array:

Statis
Akses acak(random access) dimungkinkan
Penghapusan array tidak mungkin

Linked List:

Dinamis
Tidak bisa melakukan akses acak(random access), tetapi menggunakan akses sekuensial

Dimungkinkan dilakukan penghapusan Linked List, bahkan penambahan di lokasi manapun

Linked List memiliki beberapa bentuk, yaitu:

Single Linked List
Double Linked List
Circular Singly Linked List
Circular Doubly Linked LIst

Setiap Linked List memiliki 2 proses, yaitu:

Insert (push)
Delete (pop)

Setiap proses dibagi lagi menjadi 3, yaitu:

Insert at head
Insert at tail
Insert at middle
Delete at head
Delete at tail
Delete at middle

Untuk membuat Linked List, pertama - tama kita perlu mendefinisikan struktur node untuk list - nya.
Misal kita ingin membuat sebuah daftar bilangan bulat (integer)

struct node{
int angka;
struct node *next; };
struct node *head = 0;
struct node *tail = 0;
struct node *curr = 0;
Head adalah sebuah pointer yang menunjuk pada elemen pertama pada Linked List
Tail adalah sebuah pointer yang menunjuk pada elemen terakhir pada Linked List
curr adalah sebuah pointer yang berfungsi sebagai penanda, untuk memudahkan iterasi pada Linked List

Single Linked List
Single Linked List merupakan Linked List yang hanya memiliki 1 tangan yang menunjuk pada elemen selanjutnya yang berupa pointer, biasanya dinamakan pointer next.

sumber foto:
https://www.geeksforgeeks.org/difference-between-a-static-queue-and-a-singly-linked-list/

Single Linked List insert at head:
Metode ini akan menambahkan elemen baru di depan elemen - elemen yang sudah ada. Untuk menambahkan sebuah nilai baru, pertama - tama kita harus mengalokasikan sebuah node baru dan menetapkan (assign) nilai kepadanya dan kemudian menghubungkannya dengan Linked List yang sudah ada. Perlu diperhatikan untuk mengecek kondisi apakah Linked List sudah terbentuk atau belum.

void insertAtHead(int x){
   struct node *newnode = (struct node*)malloc(sizeof(struct node));
   newnode -> angka = x;
   if(head == NULL){ //bila Linked List nya belum ada
       head = newnode;
       head -> next = NULL;
   }
   else{
   newnode -> next = head;
   head = newnode;
   }
}

Single Linked List insert at tail:
Metode ini akan menambahkan elemen baru di belakang elemen - elemen yang sudah ada. Prosesnya tidak beda jauh dengan insert at head.

void insertAtTail(struct node *head, int x){
   struct node *newnode = (struct node*)malloc(sizeof(struct node));
   struct node *last = *head;
   newnode -> angka = x;
   newnode -> next = NULL;
   if(*head == NULL){ //kalau linked list kosong
*head = newnode;
return;
   }
   while(last -> next != NULL){ //traverse sampai belakang
last = last -> next;
   }
   last -> next = newnode;
}
Single Linked List insert at middle:
Metode ini akan menambahkan elemen di tengah - tengah/ pada posisi tertentu pada Linked List yang sudah ada. Prosesnya tidak jauh berbeda dengan metode insert sebelum - sebelumnya.

void insertAtMiddle(int x, int posisi){
   int i;
   struct node *newnode, *temp;
   newnode = (struct node*)malloc(sizeof(struct node));
   if(newnode == NULL){ //newnode tidak ada, alokasi memori gagal
printf("error tidak bisa mengalokasi memori\n");
   }
   else{
newnode -> angka = x;
newnode -> next = NULL;
temp = head;
//traverse elemen ke n - 1 posisi
for(int i = 2; i < posisi - 1; i++){
   temp = temp -> next;
   if(temp == NULL){
break;
   }
}
if(temp != NULL){
   newnode -> next = temp -> next; //link alamat ke newnode
   temp -> next = newnode; //link alamat ke n - 1 posisi
   //data masuk
}
else{
   printf("terjadi error, data tidak masuk\n");
}
   }
}

Single Linked List delete at head:
Metode ini akan menghapus elemen pertama yang ada pada Linked List. Perlu diperhatikan kondisi apakah hanya ada 1 elemen pada Linked List atau tidak.

void deleteAtHead(){
   curr = head;
   if(head == tail){ // bila hanya ada 1 elemen dalam Linked List
free(curr);
head = tail = curr = NULL;
   }
   else{
      node *temp = head;
head = head -> next;
temp -> next = NULL;
free(temp);
   }
}

Single Linked List delete at tail:
Metode ini akan menghapus elemen terakhir yang ada pada Linked List. Prosesnya tidak jauh berbeda dengan delete at head.

void deleteAtTail(){
   curr = head;
   if(tail == head){ //bila hanya ada 1 elemen dalam linked list
free(curr);
curr = head = tail = NULL;
   }
   else{
while(curr -> next != tail){ //traverse sampai belakang
   curr = curr -> next;
}
             tail = curr;
      free(tail -> next);
tail -> next = NULL;
   }
}

Single Linked List delete at mid:
Metode ini akan menghapus elemen dengan nilai tertentu yang terdapat pada Linked List. Perlu diperharikan kondisi Linked List ada atau tidak.

void deleteAtMiddle(int x){
   curr = head;
   if(head == NULL){
printf("Tidak ada data, tidak bisa menghapus\n");
   }
   else if(head -> angka == x){
deleteAtHead();
   }
   else if(tail -> angka == x){
deleteAtTail();
   }
   else{
node *temp = head;
while(temp -> next -> angka != x){
   temp = temp -> next;
}
x = temp -> next;
temp -> next = temp -> next -> next;
      free(x);
   }
}

Double Linked List
Double Linked List atau yang dikenal juga sebagai Linked List 2 arah adalah sebuah Linked List struktur data yang memiliki 2 pointer, yang satu berisi referensi ke elemen setelahnya, yang satunya berisi referensi ke elemen sebelumnya.

struct node{
   int angka;
   struct node *next;
   struct node *prev;
};
struct node *head = 0;
struct node *tail = 0;
struct node *curr;

Sumber foto:

https://www.geeksforgeeks.org/doubly-linked-list/

Proses - proses di Double Linked List tidak jauh berbeda dengan single linked list.

Sama seperti Single Linked List, pertama - tama kita harus mengalokasikan sebuah node baru dan menetapkan (assign) nilai kepadanya dan kemudian menghubungkannya dengan Linked List yang sudah ada.

Misalkan kita mau menambahkan elemen setelah elemen terakhir pada Linked List:

void insertAtTail(int x){
   struct node *newnode = (struct node*)malloc(sizeof(struct node));
   newnode -> angka = x;
   node -> next = NULL;
   if(head == NULL){ //kalau linked list kosong
head = newnode;
return;
   }
   else{
newnode -> prev = tail;
      tail -> next = newnode;
      tail = newnode;
   }
}

Misal kita ingin memasukan elemen baru pada posisi diantara head dan tail:

void insertAtMiddle(int x){
struct node *a = head;
struct node *b = tail;
//elemen baru akan ditambahkan diantara a dan b
struct node *newnode = (struct node*)malloc(sizeof(struct node));
newnode -> angka = x;
newnode -> next = b;
newnode -> prev = a;
a -> next = newnode;
b -> prev = newnode;
}

Double Linked List Delete:
proses penghapusan pada Double Linked List hampir mirip seperti pada Single Linked List. Ada 4 kondisi yang perlu diperhatikan ketika akan menghapus elemen pada Linked List:

apakah elemen yang akan dihapus adalah elemen satu -satunya pada Linked List
apakah elemen yang akan dihapus adalah head
apakah elemen yang akan dihapus adalah tail
apakah elemen yang akan dihapus adalah bukan head atau tail

void deleteAtMiddle(int x){
   curr = head;
   if(head == tail){
free(head);
head = tail = NULL;
   }
   else if(head -> angka == x){
head = head -> next;
      free(head -> prev);
      head -> prev = NULL;
   }
   else if(tail -> angka == x){
tail = tail -> prev;
      free(tail -> next);
      tail -> next = NULL;

   }
   else{
while(curr -> next -> angka != x){
         curr = curr -> next;
      }
      struct node *a = curr;
      struct node *del = curr -> next;
      struct node *b = curr -> next -> next;
      a -> next = b;
      b -> prev = a;
      free(del);
   }
}

Circular Single Linked List
Dalam Circular Single Linked List, elemen terakhir berisi pointer yang menunjuk pada elemen pertama dalam Linked List. Tidak ada penyimpanan nilai NULL pada list.