Linked List

Linked List adalah suatu struktur data linier. Berbeda dengan array yang juga merupakan struktur

data linier dan tipe data komposit, linked list dibentuk secara dinamik. Pada saat awal program

dijalankan elemen linked list belum data. Elemen linked list (disebut node) dibentuk sambil jalan

sesuai instruksi. Apabila setiap elemen array dapat diakses secara langsung dengan

menggunakan indeks, sebuah node linked list diakses dengan menggunakan pointer yang

mengacu (menunjuk) ke node tersebut.

Node Pembentuk Linked List

Elemen pembentuk linked list disebut node. Node terdiri dari dua bagian, bagian data dan bagian
kait (link). Bagian data berupa satu atau beberapa field. Bagian link terdiri dari pointer. Linked list
yang node-nya mempunyai satu buah pointer disebut singly-linked list. Linked list yang node-nya
mempunyai dua pointer, satu untuk mengait ke node berikutnya dan yang lain untuk mengait ke
node sebelumnya, disebut doubly-linked list. Node dibentuk dengan structure. Untuk
menyederhanakan pembahasan, dalam tulisan ini bagian data berupa satu buah field

struct tnode {
int data;
struct tnode *next;
};

Operasi Pada Linked List

Operasi yang berkaitan dengan struktur data linked list adalah: create, empty, insertathead,
insertaftercurr, insertattail, retrieve, update, findfirst, findnext, findprev, deletenode, dan clear.

• create( )

membentuk linked list kosong

• empty( )

memeriksa status kosong suatu linked list

• insert_head( )

menambah node baru pada posisi awal linked list sehingga node ini menjadi node yang pertama,
pointer current menunjuk ke node yang baru ditambahkan ini

• insert_curr( )

menambah node baru pada posisi setelah pointer current, pointer current menunjuk ke node yang
baru ditambahkan ini

• insert_tail( )

menambah node pada akhir linked list, sehingga node ini menjadi node terakhir linked list; pointer
current menunjuk kepada node yang baru ditambahkan ini

• retrieve( )

mengembalikan nilai data node yang ditunjuk pointer current

• update( )

mengubah nilai data node yang ditunjuk pointer current

• findfirst( )

memindahkan pointer current ke posisi node pertama

• findnext( )

memindahkan pointer current ke posisi node berikutnya apabila tidak sedang berada pada posisi
node terakhir

• findprev( )

memindahkan pointer current ke posisi node sebelumnya apabila tidak sedang berada pada posisi
node pertama

• deletenode( )

menghapus node pada posisi current dan memindahkan pointer current ke posisi node pertama

• clear( )

menghapus linked list dengan membebaskan seluruh node satu persatu.

Implementasi Linked List

Fungsi create( ) memberi nilai awal NULL kepada pointer head dan curr (current).

void create(struct tnode **head, struct tnode **curr) {
*head= *curr= NULL;
}

Fungsi empty( ) mengembalikan nilai satu apabila linked list masih kosong yang ditandai dengan
pointer head yang bernilai NULL., selain itu dikembalikan nilai nol.

int empty(struct tnode *head) {
if (head== NULL) return 1;
return 0;
}

Fungsi insert_head( ) menambah node baru pada posis awal linked list. Node baru ini menjadi
node pertama

Fungsi insert_curr( ) menambah node baru pada posisi setelah pointer curr. Apabila linked list
masih kosong maka node ini menjadi node pertama. Pointer curr menunjuk ke node baru tersebut.

Fungsi insert_tail( ) menambah node baru pada posis akhir linked list. Pointer curr digerakkan
sampai menunjuk node terakhir, lalu node baru dikaitkan. Node baru ini menjadi node terakhir.
Pointer curr diubah sehingga mengacu ke node ini.

Fungsi retrieve( ) mengembalikan data pada node yang sedang ditunjuk pointer curr atau
mengembalikan suatu nilai tertentu apabila linked list dalam keadaan kosong.

 int retrieve(struct tnode *head, struct tnode *curr) {
  if (empty(head)) return -32768;
  return curr->data;
} 

Fungsi update( ) mengubah nilai data pada node yang ditunjuk pointer curr jika linked list tidak
kosong. Nilai satu akan dikembalikan apabila perubahan data berhasil dilakukan.

 int update(struct tnode *head, struct tnode* curr, int e) {
  if (empty(head)) return 0;
  curr->data= e;
  return 1;
}

Fungsi findfirst( ) akan memindahkan pointer curr ke posisi node pertama, yaitu node yang
ditunjuk pointer head, jika linked list tidak kosong. Nilai satu akan dikembalikan apabila
pemindahan pointer curr berhasil dilakukan.

 int findfirst(struct tnode *head, struct tnode **curr) {
  if (empty(head)) return 0;
  *curr= head;
  return 1;
}

Fungsi findnext( ) akan memindahkan pointer curr ke posisi node berikutnya apabila linked list
tidak kosong dan pointer curr tidak sedang berada pada posisi node terakhir. Nilai satu akan
dikembalikan apabila pemindahan pointer curr berhasil dilakukan.

 int findnext(struct tnode *head, struct tnode **curr) {
  if (empty(head)) return 0;
  if ((*curr)->next ==  NULL) return 0;
  *curr= (*curr)->next;
  return 1;
}

Fungsi findprev( ) akan memindahkan pointer curr ke posisi node sebelumnya apabila linked list
tidak kosong dan pointer curr tidak sedang berada pada posisi node pertama. Nilai satu akan
dikembalikan apabila pemindahan pointer curr berhasil dilakukan. Pemindahan dilakukan dengan
bantuan sebuah pointer lain. Pada mulanya pointer ini mengacu kepada node pertama. Pointer ini
berpindah ke node selanjutnya sampai pada posisi satu node sebelum node yang diacu pointer
curr.

int findprev(struct tnode *head, struct tnode **curr) {
  if (*curr== head) return 0;
  struct tnode *temp= head;
  while (temp->next!= *curr) temp= temp->next;
  *curr= temp;
  return 1;
}