Pertemuan 2 - Linked Lists Implementation - 2101696973 - Rifqi Amru Bakti

Nama : Rifqi Amru Bakti
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
   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;

Delete

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