LINKED LIST

Linked list adalah bagian struktur data yang biasa disebut juga senarai berantai adalah sebuah rangkaian yang terdiri dari data dan alamat elemen record selanjutnya(pointer) yang biasa juga disebut node.  Dalam sebuah linked list terdapat istilah head  dan tail.

·         Head = Elemen yang berada di posisi pertama dalam suatu linked list.

·         Tail = Elemen yang berada di posisi terakhir dalam suatu linked list.

Ada beberapa jenis linked list sebagai berikut:

1.       Single Linked List

Single linked list merupakam suatu linked list yang haya memiliki satu variable pointer saja, diana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail tersebut menunju ke NULL. Pembuatan Single Linked List dapat menggunakan 2 metode:
•     LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
•     FIFO (First In First Out), aplikasinya : Queue (Antrean)

Contoh:

 struct Mahasiswa{

            char nama[25];

            int usia;

            struct Mahasiswa *next;

}*head,*tail;

2.      Double Linked List

Salah astu kelemahhan single linked list adalah pointer hanya dapat bergerak satu arah saja, maju/mundur atau, kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak ke satu arah saja. Double linked list merupakan suatu linked list yang memiliki dua pointer, yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumya, sehingga linked list tersebut dapat menunjuk ke dua arah data. Setiap head dan tailnya juga menunjuk ke NULL.

Contoh:

Struct Mahasiswa{

            char nama[25];

 int usia;

            struct Mahasiswa *next,*prev;

}*head,*tail

3.       Circular Linked List

Dalam circular linked list, node terakhir dalam struktur memiliki pointer yang mengarah ke node pertama(head), jadi tidak ada pointer yang menunjuk ke NULL. Ada dua jenis circular linked list, yaitu:

a.       Circular single linked list

b.       Circular doubly linked list

Circular doubly linked list merupakan double linked list yang node terakhirnya menunjuk ke ke node awal yang menunjuk ke  node terakhir.

Berikut adalah operasi-operasi yang terdapat dalam linked list:

-          Insert : menambahkan sebuah node baru ke dalam suatu linked list

-          IsEmpty : menentukan apakah linked list kosong atau tidak.

-          Find first : mencari elemen pertama pada linked list.

-          Find next : mencari elemen seudah elemen yang ditunjuk now.

-          Retrieve : mengambil elemen yang ditunjuk oleh now, elemen tersebut lalu dikembalikan oleh fungsi.

-          Update : megnubah elemen  yang ditunjuk oleh now dengan isi dari sesuatu.

-          Delete now : menghapus elemen yang ditunjuk oleh now, jika yang diihapus adalah elemen pertama dari linked list(head), head akan berpindah ke elemen berikut.

-          Delete head : menghapus elemen yang ditunjuk head, dan head berpindah ke elemen berikutnya.

-          Clear : menghapus inked list yang sudah ada. Fungsi ini wajib dilakukan bila ingin mengakhiri program yang menggunakan linked list. Jika dilakukan, data data yang dialokasikan ke memori program senelumnya akan tetap tertinggal di dalam memori.

Contoh coding:

                Doubly linked list

                                Struct tnode{

                                Int value;

                                Struct tnonde *next;

                                Struct tnode *prev;

                                };

Struct tnode *head = 0;

Struct tnode *tail = 0;



Implementasi:

                Insert :

                                Code 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;

Code baru diantara head dan tail:

Struct tnode *a = ??;

Struct tnode *b = ??;

//code baru akan ditaro 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;

                Delete:

                                Jika node yang dihapus adalah node satu satunya:

                                Free(head);

                                Head = NULL;

                                Tal = NULL;

                                Jika node yang ingin dihapus adalah head:

                                Head = head -> next;

                                Free(head -> prev);

                                Tail -> next = NULL;

                                Jika node yang ingin dihapus adalah tail:

                                Tail = tail -> prev;

                                Free(tail -> next);

                                Tail -> next = NULL;

                                Jika node yang dihapus bukanlah 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);



Source:

https://zoneblog123.blogspot.com/2018/04/pengertian-linked-list-beserta-jenis.html
alvinstrukturdata.blogspot.com/2016/01/apa-itu-linked-list.html


(approved by mr. henry chong)