SINGLY LINKED LIST (SENARAI BERKAIT TUNGGAL)

Pengertian Linked List

          Senarai berkait adalah struktur data yang paling dasar. Senarai berkait terdiri atas sejumlah unsur-unsur dikelompokkan, atau terhubung, bersama-sama di suatu deret yang spesifik. Senarai berkait bermanfaat di dalam memelihara koleksi-koleksi data, yang serupa dengan array/larik yang sering digunakan. Bagaimanapun juga, senarai berkait memberikan keuntungan-keuntungan penting yang melebihi array/larik dalam
banyak hal.
         Secara teori, linked list adalah sejumlah node yang dihubungkan secara linier dengan bantuan pointer. Dikatakan singly (single) linked apabila hanya ada satu pointer yang menghubungkan setiap node. Singly artinya field pointer-nya hanya satu buah saja dan satu arah.

     Senarai berkait adalah struktur data yang paling dasar. Senarai berkait terdiri atas sejumlah unsur-unsur dikelompokkan, atau terhubung, bersama-sama di suatu deret yang spesifik.

       Abstraksi Tipe Data Singly Linked List Non Circular

Pembuatan struct bernama tnode berisi 2 field, yaitu field data bertipe integer
dan field next yang bertipe pointer dari tnode.

Deklarasi node dengan struct
struct tnode
{
int data;
struct tnode *next;
}

Gambar 1. Sebuah node pada Singly Linked List
          Asumsikan kita memiliki sejumlah node yang selalu menoleh ke sebelah dalam arah yang sama. Atau, sebagai alat bantu, Anda bisa mengasumsikan beberapa orang yang bermain kereta api. Yang belakang akan memegang yang depan, dan semuanya menghadap arah yang sama. Setiap pemain adalah node. Dan tangan pemain yang digunakan untuk memegang bahu pemain depan adalah variabel next. Sampai di sini,
kita baru saja mendeklarasikan tipe data dasar sebuah node. Selanjutnya, kita akan mendeklarasikan beberapa variabel pointer bertipe struct tnode. Beberapa variabel tersebut akan kita gunakan sebagai awal dari linked list, node aktif dalam linked list, dan node sementara yang akan digunakan dalam pembuatan node
di linked list. Berikan nilai awal NULL kepada mereka. Deklarasi node untuk beberapa keperluan, seperti berikut ini:      struct tnode *head=NULL, *curr=NULL, *node=NULL;

         Dengan demikian, sampai saat ini, telah dimiliki tiga node. Satu sebagai kepala (head), satu sebagai node aktif dalam linked list (curr) dan satu lagi node sementara (node). Sekarang telah siap untuk membuat singly linked list. Untuk itu, akan dimasukkan nilai tertentu sebagai nilai untuk field data dengan cara melakukan perulangan sehingga campur tangan user tidak diperlukan. Seperti yang diungkapkan sebelumnya, bahwa akan dibuat Singly Linked List (SLL) dengan cara first-create-first-access. Dengan cara ini, node yang dibuat pertama akan menjadi head. Node-node yang dibuat setelahnya akan menjadi node-node pengikut. Untuk mempermudah pengingatan, ingatlah gambar anak panah yang mengarah ke kanan. Head akan berada pada pangkal anak panah, dan node-node berikutnya akan berbaris ke arah bagian anak panah yang tajam.

Gambar 2 Singly Linked List 

Apabila diperhatikan, setiap node memiliki petunjuk untuk node sebelahnya. Bagaimana dengan node terakhir? Akan diberikan nilai NULL. Dengan demikian, setiap node kebagian jatah.

int i;
for (i=0; i<5; i++)
{
node = (struct tnode *)
malloc (sizeof(struct tnode));
node -> data = i;
if (head == NULL)
{
head = node;
curr = node;
}else
{
curr -> next = node;
curr = node;
}
}
curr -> next = NULL;

Berikut adalah penjelasan kode-kode pembuatan singly linked list tersebut. Pertama-tama, akan dibuat perulangan dari 0 sampai 4, yang dimaksudkan untuk membuat lima buah node yang masing-masing field data nya berisikan nilai dari 0 sampai 4. Pembuatan node dilakukan dengan fungsi malloc().

for (i=0; i<5; i++)
{
node = (struct tnode *)
malloc (sizeof(struct tnode));
node -> data = i;
...
...
}

   Setelah itu, perlu dibuat node dan penghubung. Pertama-tama, akan diuji apakah head bernilai NULL. Kondisi head bernilai NULL hanya terjadi apabila belum dimiliki satu node pun. Dengan demikian, node tersebut akan dijadikan sebagai head. Node aktif (curr), juga kita dapat dari node tersebut. Sekarang, bagaimana kalau head tidak bernilai NULL alias telah dimiliki satu atau lebih node? Yang pertama dilakukan adalah menghubungkan pointer next dari node aktif (curr) ke node yang baru saja dibuat. Dengan demikian, baru saja dibuat penghubung antara rantai lama dengan mata rantai baru. Atau, dalam permainan kereta
api, pemain paling depan dalam barisan lama akan menempelkan tangannya pada bahu pemain yang baru bergabung. Node aktif (curr) kemudian dipindahkan ke node yang
baru dibuat.


if (head == NULL) 
{
head = node;
curr = node;
}



                Gambar 3 Membuat elemen pertama SLL

 else
{
curr->next=node;
curr = node;
}

Gambar 4. Penambahan elemen dibelakang SLL

Setelah semuanya dibuat, sudah saatnya bagi kita untuk menghubungkan pointer next
untuk mata rantai terakhir ke NULL.
                                                      curr -> next = NULL;
         Dan selamat! Singly linked list baru saja diciptakan. Ada yang terlupa? Ada. Bagaimana
kita tahu bahwa linked list yang kita ciptakan adalah linked list yang benar? Salah satu
cara untuk mengetahuinya adalah dengan mencetak field x untuk semua node. Dari head
sampai node terakhir.
curr = head;
while (curr != NULL)
{
printf(“%d “, curr -> data);
curr = curr -> next;
}
printf(“\n”);

                    Pertama-tama, kita meletakkan node aktif (curr) ke posisi head. Setelah itu, kita akan
pindahkan kunjungi satu per satu node dengan memindahkan node aktif (curr) ke posisi
sebelahnya. Semua kunjungan tersebut akan kita lakukan apabila node aktif (curr) tidak
menemui NULL. Anda mungkin ingin menambahkan pemanggilan free() untuk
melakukan dealokasi.
Kode selengkapnya:

#include <stdio.h>
#include <stdlib.h>
int main()
{
struct tnode
{
int data;
struct tnode *next;
};
struct tnode *head=NULL,
5
*curr=NULL, *node=NULL;
int i;
for (i=0; i<5; i++)
{
node = (struct tnode *)
malloc (sizeof(struct tnode));
node -> data = i;
if (head == NULL)
{
head = node;
curr = node;
}else
{
curr -> next = node;
curr = node;
}
}
curr -> next = NULL;
curr = head;
while (curr != NULL)
{
printf(“%d “, curr -> data);
curr = curr -> next;
}
printf(“\n”);
free();
return 0;
}

Sumber :  Andri Kristanto. 2003. Struktur Data dengan C++. Yogyakarta: Graha Ilmu
                Karve, Sanchit. Basic Data Structures in C++.