Session 2 – 27/2/2018
Linked List Implementation I
Sub Topics :
- Single Linked List
- Polynomial Representation
- Circular Single Linked List
- Doubly Linked List
- Circular Doubly Linked List
- Header Linked List
Linked List
Linked list merupakan struktur data (bertipe sama) yang terdiri dari sekumpulan node yang secara bersama-sama merepresentasikan sebuah urutan. Linked list juga disebut sebagai sebuah metode untuk menyimpan data dengan struktur sehingga dapat secara otomatis menciptakan suatu tempat di memory untuk menyimpan data.
Ada beberapa jenis dari linked list, antara lain :
- Single Linked List
Single linked list merupakan sekumpulan node, dimana masing-masing node memiliki field data dan kolom yang hanya memiliki 1 penghubung ke node lain.
Untuk membuat list, pertama kita perlu mendefinisikan struktur node untuk list.
Misalkan kita ingin membuat list integer, maka ketentuannya adalah :
struct tnode {
int value;
struct tnode *next;
};
struct tnode *head = 0;
- Single Linked List : Insert
Untuk menambah value baru, pertama kita harus mengalokasikan node baru secara dinamis dan memberikan nilai pada node tersebut dan kemudian menghubungkannya dengan linked list yang ada.
Misalkan kita ingin menambahkan node baru di depan head, maka ketentuannya adalah :
struct tnode *node =
(struct tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = head;
head = node;
note : Head adalah pointer pada elemen pertama di linked list ini.
Menambahkan node baru di depan head.
Dengan asumsi bahwa 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 kita ingin hapus, lalu remove dan hubungkan pada linked list yang tersisa.
Misalkan nilai yang ingin kita remove adalah x dan asumsikan bahwa x ada di dalam linked list.
Ada dua kondisi yang harus diperhatikan :
Jika x berada pada head node atau x tidak berapa pada head node.
struct tnode *curr = head;
// Jika x berada pada head node
if ( head->value == x ) {
head = head->next;
free(curr);
// Jika x berada pada tail node
else if(tail->value == x){
while(curr->next!=tail) curr = curr->next;
free(tail); tail = curr;
tail->next = NULL;
}
// jika x tidak berada pada head node, dan mencari lokasi nilai x.
else {
while ( curr->next->value != x ) curr = curr->next;
struct tnode *del = curr->next;
curr->next = del->next;
free(del);
}
Contoh :
untuk menghapus nilai 31 dan nilai tersebut berada pada head node.
Untuk menghapus nilai 35 dan nilai tersebut tidak berada di head node.
- Polynomial Representation
Diketahui sebuah polinomial adalah : 6x3+9x2+1
Dari setiap individu dalam polinomial terdiri dari dua bagian, koefisien dan kekuatan.
6,9,7, dan 1 adalah koefisien yang memiliki 3,2,1, dan 0 sebagai kekuatan mereka masing-masing.
Setiap istilah polinomial dapat diwakili sebagai node dari linked list.
- Circular Single Linked List
Dalam circular single linked list, node terakhir berisi pointer ke node pertama dari list.
Kita dapat memiliki circular singly linked list serta circular doubly linked list. Saat melintasi circular linked list, kita dapat memulai pada setiap node dan dapat melintasi list berbagai arah, forward atau backward, hingga kita mencapai node yangg sama di mana kita mulai. Dengan demikian, circular linked list tidak memiliki awal dan akhir.
- Doubly Linked List
Doubly linked list adalah jenis linked list yang berisi pointer ke berikutnya serta node sebelumnya dalam urutan yang lebih kompleks, oleh karena itu, terdiri dari tiga bagian yaitu : data, pointer ke node berikutnya, dan pointer ke 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 dalam singly linked list, pertama kita harus mengalokasikan node baru dan menetapkan nilai node tersebut, dan kemudian kita menghubungkan node dengan linked list yang sudah ada.
Misalkan kita ingin menambahkan node baru dibelakang tail.
struct tnode *node =
(struct tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = NULL;
node->prev = tail;
tail->next = node;
tail = node;
misalkan kita ingin menambahkan node baru di posisi tertentu (lokasi manasaja antara head dan tail) :
struct tnode *a = ??;
struct tnode *b = ??;
// node baru akan ditambahkan diantara a dan 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;
- Doubly Linked List : Delete
Ada 4 kondisi yang harus diperhatikan saat menghapus :
- Node yang dihapus hanya node yang terdapat dalam linked list
- Node yang dihapus adalah head
- Node yang dihapus adalah tail
- Node yang dihapus adalah bukan head atau tail.
- Jika node yang dihapus hanya node
-free(head);
-head = NULL;
-tail = NULL;
2. Jika node yang dihapus adalah head
-head = head->next;
-free(head->prev);
-head->prev=NULL;
3. Jika node yang dihapus adalah tail
-tail = tail->prev;
-free(tail->next);
-tail->next = NULL;
4. Jika node yang 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 Doubly Linked List
Sama seperti dengan circular singly linked list, tetapi total pointer pada tiap node disini adalah 2 (dua) pointer.
- Header Linked List
Header linked list adalah jenis dari linked list yang berisi sebuah header node pada awal list.
Jadi, dalam header linked list, START (L) tidak akan mengarah ke node pertama dari list tapi START(L) akan berisi alamat dari header node.
Farhan Adji Nugroho - 2101711356
