Pertemuan 2 - Implementasi Linked List - 2101711122 - Bela Kristianti

Single Linked List

Untuk membuat list, pertama kita perlu mendefinisikan struktur node untuk list. Jika kita ingin membuat list dari integer.

struct tnode {

int value;
struct tnode *next;
};
struct tnode *head = 0;

note : head is the pointer to the
first element in our linked list

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.

Jika kita ingin menambahkan node baru di depan "kepala" (head).

struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next  = head;
head = node;
Operator -> has the same meaning as:
(*node).value = x;
(*node).next  = head

Tambahkan node baru di depan head. Dengan asumsi sudah ada linked list yang berisi 10, 35, 27.

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. Jika nilai yang ingin kita hapus adalah x dan 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);
}

Deleting 31 (located at head)

Deleting 35 (not located at head)

Polynomial Representation
Polinomial diberikan sebagai 6x3 + 9x2 + 7x + 1
Setiap istilah individual dalam polinom terdiri dari dua bagian, koefisien dan kekuatan
di sini, 6, 9, 7, dan 1 adalah koefisien dari persyaratan yang memiliki 3, 2, 1, dan 0 sebagai kekuatan mereka masing-masing. Setiap istilah polinomial dapat direpresentasikan sebagai node dari linked list.

Circular Single Linked List

Dalam circular(melingkar), node terakhir berisi pointer ke node pertama.
Kita bisa memiliki list saling terkait melingkar dan juga circular doubly linked list.
Tidak ada penyimpanan nilai NULL dalam list.

Doubly Linked List
Doubly linked atau linked list dua arah adalah struktur data linked list dengan dua link, satu yang berisi referensi ke data berikutnya dan data yang berisi referensi ke data sebelumnya.

struct tnode {
int value;
struct tnode *next;
struct tnode *prev;
};
struct tnode *head = 0;
struct tnode *tail = 0;

Doubly Linked List : Insert
Sama seperti single linked list, pertama kita harus mengalokasikan node baru dan memberikan nilai padanya, dan kemudian kita menghubungkan node dengan linked list yang ada. Seharusnya kita ingin menambahkan node baru di belakang "ekor"(tail).

Struct tnode *node =(struct tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next  = NULL;
node->prev  = tail;
tail->next  = node;
tail = node;

Jika kita ingin memasukkan node baru pada posisi tertentu (setiap lokasi antara kepala dan ekor)

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;

Double Linked List : Delete
Ada 4 kondisi yang harus kita perhatikan saat menghapus: node yang akan dihapus adalah satu-satunya node dalam linked list. Node yang akan dihapus adalah kepala. Node yang akan dihapus adalah ekor. Node yang akan dihapus bukan kepala atau ekor
1. Jika node yang akan dihapus adalah satu-satunya node :
free(head);
head = NULL;
tail = NULL;
2. Jika node yang akan dihapus adalah kepala(head) :
head = head->next;
free(head->prev);
head->prev = NULL;
3. Jika node yang akan dihapus adalah tail(ekor) :
tail = tail->prev;
free(tail->next);
tail->next = NULL;
4. Jika node yang akan dihapus adalah bukan kepala atau ekor :
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 Double Linked List
Mirip dengan circular single linked list, namun total pointer pada setiap node di sini adalah 2 (dua) pointer.

Header Linked List
Sebuah header linked list adalah tipe khusus linked list yang berisi node header di awal list. Jadi, dalam sebuah header linked list, START (L) tidak akan mengarah ke node pertama dari daftar tapi START (L) akan berisi alamat node header.