NIM : 2101696973
Session 2
Linked Lists Implementation
Linked List :
Linked lists merupakan sebuah struktur data yang digunakan untuk menyimpan sejumlah objek data biasanya secara terurut sehingga memungkinkan penambahan, pengurangan, dan pencarian atas elemen data yang tersimpan dalam linked lists dilakukan secara lebih efektif.
Linked lists memiliki beberapa implementasi yang bekerja secara berbeda-beda, implementasi tersebut adalah :
- Singly Linked List
Singly linked list adalah bentuk tipe data struktur linked list dimana tiap node dalam listnya menyimpan suatu data dan pointer atau referensi ke node selanjutnya yang ada di list tersebut. Untuk mengimplementasikan single linked list, hanya pointer atau referensi pada node pertama di list yang harus disimpan. Node terakhir pada single linked list tidak menunjuk pada apapun atau NULL.
contoh Kodingan Singly Linked List :
Mendefinisikan List
struct tnode
{
int value;
struct tnode *next;
};
struct tnode *head = 0;
Insert List
struct tnode *node =
(struct tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = head;
head = node;
Delete List
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);
}
Doubly Linked List adalah bentuk tipe data struktur Linked List yang memiliki dua variabel pointer, pointer yang menunjuk ke node berikutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga tidak menunjuk pada apapun atau bisa dibilang menunjuk NULL.
Contoh Koding :
List
struct tnode
{
int value;
struct tnode *next;
struct tnode *prev;
};
struct tnode *head = 0;
struct tnode *tail = 0;
Insert
struct tnode *node =
(struct tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = NULL;
node->prev = tail;
tail->next = node;
tail = node;
free(head);
head = NULL;
tail = NULL;
(Mendelete satu node)
head = head->next;
free(head->prev);
head->prev = NULL;
(Node yang di delete node Head)
- Polynomial Representation
Dalam Polynomial Representation dapat diasumsikan bahwa tiap linked list menyimpan dua nilai yang berbeda-beda. Dalam bentuk polinom dibawah, setiap nilai dalam node memiliki nilai asli dan pangkat variabelnya.
Dimisalkan polinom yang didapat adalah 6x^3 + 9x^2 + 7x + 1 .
dalam polinom tersebut 6, 9, dan 1 adalah koefisiennya sedangkan pangkat koefisien tersebut adalah 3, 2, 1, dan 0 karena mereka tidak memiliki nilai x.
- Multi Linked List
Multi Linked List merupakan bentuk unik linked list dimmana tiap node memiliki pointer kepada satu atau lebih node dalam linked list tersebut.
- Circular Linked List
Circular Linked List merupakan bentuk linked list dimana node terakhir(tail) menunjuk kepada node pertama(head). Oleh karena ini, node dalam Circular Linked List tidak ada yang menunjuk NULL.
Ada dua jenis Circular Linked List, List tersebut ialah :
> Circular Single Linked List
> Circular Doubly Linked List
- Header Linked List
Header Linked List adalah suatu bentuk linked list dimana ada sebuah node yang dijadikan sebagai "Header" di awal dari list. Bentuk dari Header Linked List dapat dilihat pada gambar dibawah, Header node berada pada awal list tersebut.
Rifqi Amru Bakti-2101696973
