Pertemuan ke2-Linked list implementation I-2101660941-Leo Yuanto

Nama : Leo Yuanto
NIM : 2101660941
Pertemuan ke-2

Linked List Implementation

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

• Linked List lebih efisien dalam penggunaan memori, karena ketika kita hendak menyimpan 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

Pengertian

Single Linked List menggunakan sebuah variabel pointer dan pointer nextnya menunjuk node selanjutnya. 

*Nodes artinya Objek yang mereferensikan dirinya sendiri

Syntax

struct tnode {

    int value;

    struct tnode, *next;

};

struct tnode *head = 0;

Insert in Single Linked List- Di depan atau head 

  Syntax :

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

  node->value = x;

  node->next = head;

  head = node;

Delete in Single Linked List

Syntax :

struct tnode *curr = head;

// jika x di head

if (head->value == x){

   head = head->next;

   free(curr);

}

//jika x di tail

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

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

  free (tail);

  tail->next = NULL;

}

//jika x tidak di head dan tidak di tail
else {
  while (curr->next->value != x) curr = curr->next;
  struct tnode *del = curr->next;
  curr->next = del->next;
  free(del);
}

Polynomial Representation
Secara khusus, polynomial dibago menjadi 2 bagian yaitu Koefisien dan Eksponen dari suku yang bersangkutan.


Circular Single Linked List
Pengertian
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 yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya.

Syntax : 
struct tnode {
  int value;
  struct tnode *next;
  struct tnode *prev;
};

struct tnode *head = 0;
struct tnode *tail = 0;

Insert in Double Linked List
Pertama-tama, kita harus mengalokasikan 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;

Delete in Double Linked List
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 ada 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 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.