Pertemuan ke 2 - Linked List Implementation- 2101656553 - Laurensius Haryo R. P.

Linked list adalah struktur data yang mempunyai data yang berurut dimana setiap data memiliki tempat yang men-reference data setelahnya (berurut).  Linked list merupakan suatu cara untuk menyimpan data dengan struktur sehingga dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data yang diperlukan.

Linked list merupakan struktur yg memiliki fungsi layaknya array tapi memiliki perbedaaan tersendiri:

Array :

• Kumpulan dari elemen data.
• Tersimpan didalam memori yang berurutan
• Bisa diakses secara acak.

Linked List:

• Kumpulan dari nodes.
• Tidak tersimpan pada alamat memori yang berurut
• Dalam pengaksesannya harus Sequence.

Kelebihan linked list

• fleksibilitas – memasukkan (atau menghapus) dari posisi mana saja dalam waktu yang konstan.
• Alokasi memori dinamis – tidak perlu mengalokasikan memori.

Kekurangan linkedlist

• Penggunaan dan pengaksesan yang kompleks – secara relatif linked list lebih kompleks jika dibandingkan dengan array
• Waktu yang dibutuhkan untuk mengakses elemen tidak konstan – hal ini karena tidak memasukkan rumus penghitungan yang diterapkan oleh array untuk menghitung alamat memori, jadi linked list relatif tidak efisien dibandingkan dengan array

Single linked list

Single linked list adalah jenis linked list yang paling sederhana dimana masing-masing node berisi beberapa data dan sebuah pointer ke node berikutnya dari tipe data yang sama. Daftar berantai tunggal memungkinkan transversal data hanya dengan satu cara.

Untuk membuat daftar, pertama kita perlu mendefinisikan struktur node untuk daftar.

Seharusnya kita ingin membuat daftar bilangan bulat.

Contoh struct:

struct tnode {

                int value;

                struct tnode *next;

};

struct tnode *head = 0;

head adalah pointer terhadap element pertama pada linked list ini.

Single Linked List: Insert

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

Ada empat kasus yang berbeda dalam memasukkan value ke dalam linked list:

1. Node baru disisipkan di awal.
2. Node baru disisipkan di bagian akhir.
3. Node baru dimasukkan setelah node yang diberikan.
4. Node baru dimasukkan sebelum node yang diberikan.

Contoh:

//Jika memasukan node baru di depan head

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

node->value = x;

node->next  = head;

head = node;

operator (->) maksudnya ialah:

 (*node).value = x;

 (*node).next = head;

     Single Linked List: Delete

Untuk men-delete sebuah value, pertama kita harus mencari lokasi node yang menyimpan value yang ingin kita delete, remove, dan dihubungkan dengan sisa linked list. Seharusnya value yang ingin kita delete adalah x dan asumsi x ada dalam linked list dan unik. Ada dua kondisi yang harus kita perhatikan:

• Jika x berada dalam head node
• x tidak berada dalam head node

Contoh:

struct tnode *curr = head;

// jika x adalah heade node

if ( head->value == x ) {

                head = head->next;

                free(curr);

}

// jika x adalah tail node

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

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

                free(tail); tail = curr;

                tail->next = NULL;

}

// jika x bukanlah head node atau tail node, cari lokasi

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 6x³ + 9x²+ 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 masing-masing memiliki 3, 2, 1, dan 0 masing-masing.
• Setiap istilah polinomial dapat direpresentasikan sebagai node dari linked list.

Circular Single Linked List

• Dalam circular, 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 two-way linked list adalah struktur data linked list dengan dua link, satu yang berisi referensi ke data berikutnya dan data yang berisi referensi ke data sebelumnya.

Contoh:

struct tnode {

                int value;

                struct tnode *next;

                struct tnode *prev;

};

struct tnode *head = 0;

struct tnode *tail = 0;

doubly link list: insert

Sama seperti dalam single linked list, pertama kita harus mengalokasikan node baru dan memberikan nilai padanya, dan kemudian kita menghubungkan node dengan linked list yang ada.

Contoh:

//jika node baru masuk dari belakang 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 node baru dimasukan dari tengah linked

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:

free(head);

head = NULL;

tail = NULL;

• node yang akan dihapus adalah head:

                head = head->next;

                free(head->prev);

                head->prev = NULL;

• node yang akan dihapus adalah tail:

                tail = tail->prev;

                free(tail->next);

                tail->next = NULL;

• node yang akan dihapus bukan head atau 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 Double Linked List

Hal ini mirip dengan single circular linked list, namun total pointer pada setiap node di sini adalah 2 pointer.

Header Linked List

• Header linked list adalah jenis daftar tertaut khusus 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.