Pertemuan ke 2 - Linked List Implementation - 2101682242 - Mohammad Refardy

Sub Topics

Linked List:

-Single Linked List

-Polynomial Representation

-Circular Single Linked List

-Doubly Linked List

-Circular Doubly Linked List

-Header Linked List 

Single Linked List

Untuk membuat daftar, pertama kita perlu mendefinisikan struktur simpul untuk daftar.
Seharusnya kita ingin membuat daftar bilangan bulat.

struct tnode {
nilai int;
struct tnode * next;
};


struct tnode * head = 0;

Single Linked List: Insert

Untuk menyisipkan nilai baru, pertama kita harus mengalokasikan node baru secara dinamis dan memberikan nilai padanya dan kemudian menghubungkannya dengan linked list yang ada.

Seharusnya kita ingin menambahkan simpul baru di depan kepala.

struct tnode * node =
(struct tnode *) malloc (sizeof (struct tnode));
node-> nilai = x;
node-> next = head;

kepala = simpul;

Single Linked List: Delete

Untuk menghapus sebuah nilai, pertama kita harus mencari lokasi
node yang menyimpan nilai yang ingin kita hapus, keluarkan,
dan hubungkan sisa linked list.

Seharusnya nilai yang ingin kita hapus adalah x dan
dengan asumsi x ada dalam linked list dan unik.

Ada dua kondisi yang harus kita perhatikan:

Jika x berada dalam head node atau x tidak berada dalam head node

struct tnode *curr = head;

// if x is in head node

if ( head->value == x ) {

  head = head->next;

  free(curr);
}

// if x is in tail node

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

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

  free(tail); tail = curr;

  tail->next = NULL;

}

// if x is not in head node, find the location

else {

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

  struct tnode *del = curr->next;

  curr->next = del->next;

  free(del);

}

Polynomial Representation

• Polinomial diberikan sebagai 6x3 + 9x2 + 1
• Setiap istilah individu dalam polinom terdiri dari dua bagian, koefisien dan kekuatan
• Di sini, 6, 9, 7, dan 1 adalah koefisien dari persyaratan yang masing-masing memiliki 3, 2, 1, dan 0 sebagai kekuatan masing-masing.
• Setiap istilah polinomial dapat direpresentasikan sebagai simpul dari linked list.

Circular Single Linked List

• Dalam lingkaran, simpul terakhir berisi pointer ke simpul pertama

• Kita bisa memiliki daftar saling terkait melingkar dan juga daftar ganda yang saling terkait.

• Tidak ada penyimpanan nilai NULL dalam daftar

Doubly Linked List

Doubly linked list atau linked list dua arah adalah data daftar tertaut

struktur dengan dua link, satu yang berisi referensi ke data berikutnya

dan satu yang berisi referensi ke data sebelumnya.

struct tnode {

nilai int;

struct tnode * next;

struct tnode * prev;

};

struct tnode * head = 0;

struct tnode * tail = 0;

Doubly Linked List: Insert

Sama seperti dalam satu linked list, pertama kita harus mengalokasikan

simpul baru dan tetapkan nilainya ke sana, lalu kita

hubungkan node dengan linked list yang ada.

Seharusnya kita ingin menambahkan simpul baru di belakang ekor.

struct tnode *node =

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

node->value = x;

node->next  = NULL;

node->prev  = tail;

tail->next  = node;

tail = node;

Seharusnya kita ingin memasukkan simpul baru dalam posisi tertentu (apapun

lokasi antara kepala dan ekor)

struct tnode * a = ??;

struct tnode * b = ??;

// node baru akan dimasukkan antara a dan b

struct tnode * node =

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

node-> nilai = x;

node-> next = b;

node-> prev = a;

a-> next = node;

b-> prev = simpul;

Doubly Linked List: Delete

Ada 4 kondisi yang harus kita perhatikan saat menghapus:

Node yang akan dihapus adalah satu-satunya simpul dalam linked list.

Simpul yang akan dihapus adalah kepala.

Simpul yang akan dihapus adalah ekor.

Simpul yang akan dihapus bukan kepala atau ekor.

1.  If the node to be deleted is the only node:

–   free(head);

–    head = NULL;

–    tail = NULL;

2.If the node to be deleted is head:

•  head = head->next;

•  free(head->prev);

•  head->prev = NULL;

3.If the node to be deleted is tail:

•  tail = tail->prev;

•  free(tail->next);

•  tail->next = NULL;

4.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);

Circular Doubly Linked List

Ini mirip dengan linked list melingkar tunggal, tapi total

pointer di setiap node di sini adalah 2 (dua) pointer.

Header Linked List

• Daftar taut header adalah jenis daftar tertaut khusus yang berisi simpul header di awal daftar.

• Jadi, dalam sebuah header linked list, START (L) tidak akan mengarah ke simpul pertama dari daftar tapi START (L) akan berisi alamat simpul header.