Algoritma : Linked List

Rumahit.ID - Linked List adalah suatu cara untuk menyimpan data dengan struktur sehingga programmer dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data kapan saja diperlukan. Secara rinci, programmer dapat menulis suatu struct atau definisi kelas yang berisi variabel yang memegang informasi yang ada di di dalamnya, dan mempunyai suatu pointer yang menunjukan ke suatu struct sesuai dengan tipe datanya.

Struktur dinamis ini mempunyai beberapa keuntungan dibandingkan struktur array yang bersifat statis. Struktur linked list lebih dinamis, karena banyaknya elemen dengan mudah ditambah atau dikurangi, berbeda dengan arrayb yang ukuranya bersifat tetap. Disamping itu, manipulasi terhadap setiap elemen seperti menyisipkan, menghapus, maupun menambah dapat dilakukan dengan lebih mudah.

Untuk lebih memahami konsep linked list perhatikan permasalahan berikut ini:
Misalkan anda diminta untuk membuat sebuah algoritma dan program untuk memasukan 2 buah daftar ke dalam suatu daftar atau senarai (linked list), dimana senarai tersebut masih kosong, sehingga setelah anda masukan 2 buah data tersebut, senarai tersebut berisi 2 buah data.


Algoritma dari permasalahan diatas adalah sebagai berikut:

1. Tentukan struktur untuk menampung data yang dimasukan
2. Senarai masih keadaan kosong
3. Tentukan fungsi untuk memasukan data ke dalam senarai
4. Fungsi untuk memasukan data ke dalam senarai adalah:
        if (p==nul){
        t → next = *s
        *s = t }
5. masukan data tersebut ke dalam senarai
6. tampilkan data
7. selesai

Implementasi dari algoritma diatas pada program C++ adalah sebagai berikut :

/*Program:link1.cpp */ 

#include <stdio.h> 
#include <stdlib.h> 
#include <malloc.h> 

typedef struct nod { int data; 

struct nod *next;
} NOD, *NODPTR;
        void CiptaSenarai (NODPTR *s)
{
       *s = NULL;
}
   NODPTR NodBaru(int m)
{
       NODPTR n;
             n = (NODPTR) malloc(sizeof(NOD)); if (n != NULL) {
             n -> data = m;
             n -> next = NULL;
}
   return n;
}
   void SisipSenarai (NODPTR *s, NODPTR t, NODPTR p)
{
         if (p==NULL) {
             t -> next = *s;
             *s = t;

         }
         else {
             t -> next = p -> next; p -> next = t;

   }
}
    void CetakSenarai (NODPTR s) { NODPTR ps;
        for (ps = s; ps != NULL; ps = ps -> next) 
             printf("%d --->", ps -> data); 
             printf("NULL\n");
}
    int main ()
{
        NODPTR pel; NODPTR n;
        CiptaSenarai(&pel);
        n = NodBaru(55); 
        SisipSenarai(&pel, n, NULL); 
        n = NodBaru(75); 
        SisipSenarai(&pel, n, NULL); 
        CetakSenarai(pel);
    return 0;
}

1. Teknik-teknik Dalam Linked List

Teknik-teknik yang ada pada linked list antara lain:

1. Pengulangan linked list
2. Mengubah sebuah Pointer dengan referensi Pointer
3. Membuat kepala senarai dengan perintah push()
4. Menambah Ekor pada akhir senarai
5. Membuat referensi lokal

Pengulangan linked list

Teknik yang sering dalam linked list adalah pengulangan keseluruhan node dalam list. Secara umum pengulangan ini dikenal sebagai while loop. Head pointer dikopikan dalam variabel lokal current yang kemudian dilakukan perulangan dalam linked list. Hasil akhir dalam linked list dengan current!=NULL. Pointer lanjut dengan current=current -> next.

Proses pengulangan linked list seperti pada penggalan program berikut ini:

// return the number of nodes in a list (while-loop version) 
int length(struct node *head) {
int count = 0;
struct node * current = head; 
while (current != NULL) { count++
current = current -> next
}
   return(count);
}

Mengubah sebuah pointer dengan referensi pointer

Banyak fungsi pada pada  linked  list perlu untuk  merubah   pointer  kepala.  Dalam
C++,   anda   juga   dapat   menyatakan  parameterpointer  sebagai  argumen   &.  Untuk
melakukan ini bahasa C++, lewati pointer ke pointer kepala. Pointer ke pointer kadang- kadang ” reference pointer”
langkah utama untuk teknik ini adalah:

• Merancang sebuah fungsi untuk mengambil pointer ke pointer kepala. Ini teknik standar yang  digunakan dalam C++ untuk melewati pointer ke “value of interest” yang membutuhkan untuk diubah. Untuk mengubah struct node*, lewati struct node**
• Gunakan '&' dalam panggilan untulk menghitung dan melewati pointer ke value of interest
• Gunakan '*' pada parameter dalam fungsi pemanggil untuk mengakses dan mengubah value of interest

Fungsi Sederhana berikut ini adalah untuk membuat pointer kepala ke NULL dengan menggunakan parameter reference

void changeToNull (struct node ** headRef)
*headRef = NULL;} 
void ChangeCaller() { 
Struct node* head1 
Struct node* head2
ChangeToNull (&head1); 
ChangeToNull (&head2); }

Gambar di bawah ini menunjukan bagaimana pointer headRef dalam ChangeToNull menunjukan ke head1 pada Change Caller.

Pointer headRef dalam ChangeToNull menunjuk ke head1

Membuat head list (kepala senarai) dengan perintah Push()

Cara termudah untuk membuat sebuah senarai (list) dengan menambah node pada “akhir kepala (last head)” adalah dengan push().

Perhatikan fungsi berikut ini :

struct node* AddAthead() { 

Struct node*head =NULL; 

int i;

for (i=1; i<6; i++) { 

push (&head,i);

}

// head == {5, 4, 3, 2, 1}; 

return (head);

}

Dalam membuat tambahan node pada akhir senarai (list) dengan menggunakan perintah Push(), sebaiknya anda berhati-hati, sebab salah urutan untuk masing-masing scrip maka urutannya akan terbalik

Menambah Tail (Ekor) pada akhir List

Untuk menambahkan node ekor pada list, sebagian melibatkan penempatan pada node terakhir, dan kemudian merubahnya, next field dari NULL untuk menunjuk pada node baru seperti variabel tail, dalam contoh berikut ini yaitu menambah node 3 ke akhir daftar {1,2}

Membuat ekor pada akhir list

Untuk memasukan atau menghapus node di dalam list, anda membutuhkan pointer ke node sebelum posisi itu, sehingga anda dapat merubahnya .next field.

Pada gambar tersebut penjelasannya adalah sebagai berikut :

1. Head pointer akan menunjukan ke node 1
2. Kemudian node 1 akan menunjukan ke node 2, yang merupakan ekor.
3. Misalkan ada node baru misalnya node 3, maka dari node 2 akan menunjuk ke node baru yaitu 3. sehingga posisi node 3 adalah posisi terakhir.

Pertanyaanya, bagaimana membuat data-data {1,2,3,4,5} yang ada pada list dengan menambahkan node di akhir ekor. Kesulitannya adalah bahwa node yang pertama pasti ditambah pada head pointer, tetapi semua node yang lain dimasukkan sesudah node terakhir dengan menggunakan tail pointer. Cara yang terbaik untuk berhubungan dengan kedua hal adalah menambah head node {1}. kemudian melakukan perulangan yang terpisah yang menggunakan tail pointer untuk menambah semua node yang lain. Tail pointer digunakan untuk menunjuk pada last node, dan masing-masing node baru ditambah dengan tail → next

Perhatikan penggalan program berikut ini:

struct node* BuildWidthSpecialCase (){ 

struct node* head = NULL;

struct node*tail; 

int i;

// Deal With the head node here, and set the tail pointer 

Push (&head, 1);

tail =head;

// Do all the other nodes using 'tail'

for (i=2; i<6; i++) {

   push(&(tail → next), I); //add node at tail → next

   tail = tail → next; // advance tail to point to last node

}

   return(head); // head == {1, 2, 3, 4, 5};

}

Membuat referensi lokal

Untuk teknik ini, kita menggunakan “reference pointer” local yang selalu menunjuk ke pointer terakhir dalam list. Semua tambahan pada list dibuat dengan refernce pointer. Reference pointer tidak menunjuk ke head pointer, tetapi menunjuk ke .next field di dalam last node terakhir dalam list.

Perhatikan penggalan program berikut ini:

struct node* BuildWidthLocalRef(){
struct node* head = NULL;
struct node** lasyPtrRefn=&head
int I;
for (i=1; i<6; i++);
   Push (lastPtrRef, I);
   LastPtrRef = &((*lastPtrRef)-> next);
}
   Return(head);
}

Teknik ini pendek, tetapi di dalam perulangan cara ini agak membahayakan. Teknik ini jarang sekali digunakan, tetapi itu merupakan cara yang baik untuk memahami
pengertian sebuah pointer. Cara kerja dari teknik ini adalah:

1. Pada puncak putaran, lastPtrRef menunjuk pointer terakhir dalam list. Pada permulaaanya menunjuk ke head pointer itu sendiri. Berikutnya kemudian akan menunjuk ke .next field di last node dalam list
2. Push (LastPtrRef); menambah node baru pada pointer akhir. Node baru menjadi node terakhir dalam list.
3. LastPtrRef= &((*lastPtrRef) → next; last PtrRef lanjut ke . Next field dan .next field sekarang menjadi pointer terakhir dalam list.

Membuat referensi local

2. Operasi Dalam Linked List

Operasi yang ada pada linked list adalah Menambah Node dan juga menghapus node 

Menambah Node Baru

Untuk menambahkan sebuah node di dalam list, kita perlu mendefinisikan sebuah kepala (head) dan ekor (tail). Pada awal list, posisi head dan tail masih menjadi satu. Setelah ada tambahan node yang baru, maka posisinya berubah. Posisi kepala tetap pada awal list dan posisi ekor pada akhir list atau node yang baru. Seterusnya, bila ada tambahan node, maka posisi ekor akan bergeser sampai ke belakang dan akhir list ditunjukkan dengan NULL. Adapun prosedurnya ditunjukkan pada penggalan program berikut ini:

void SLList :: AddANode()
{Tail -> Next = new list;
Tail=Tail ->Next;
}

menambah node baru

Adapun penjelasan dari gambar diatas adalah sebagai berikut:

1. Tentukan dan Definisikan head dan tail, dimana dalam kondisi pertama kepala dan ekor menunjuk pada node yang sama.
2. Misalkan ada node baru yang masuk, posisi head dan tail akan berubah. Head tetap akan menunjuk pada node yang lama, sedangkan ekor akan menunjuk pada node yang baru
3. Misalkan ada node yang baru, head tetap pada posisi awal, sedangkan tail akan terus bergeser ke belakang dan pada akhir list ditunjukan oleh NULL.

Menghapus Node

Untuk menghapus node, dapat dilihat pada penggalan program berikut ini :

void SLList::DeleteANode(ListPtr corpse)) // <-- i though it was funny:)
{
   ListPtr temp;
   if (corpse === Head) //case 1 corpse = Head
   {
     temp=Head;
     Head=Head->Next;
   }
   else if(corpse == Tail) //case 2 corpse is at the end
   {
      temp = Tail;
      Tail=Previous(Tail);
      Tail->Next=NULL;
      delete temp;
   }
   else //case 3 corpse is in middle somewhere
   {
      temp=Previous (corpse);
      temp->Next=corpse->Next; delete corpse;
   }
CurrentPtr=Head; //Reset the class tempptr
}

Daftar Pustaka : 

Andri Kristanto, Algoritma & Pemrograman dengan C++ Edisi 2, Graha Ilmu, Yogyakarta, 2009.
Moh. Sjukani, Struktur Data [ Algoritma & Struktur Data 2 ] dengan C, C++, Mitra Wacana Media, Jakarta, 2008.
Teddy Marcus Zakaria dan Agus Prijono, Konsep dan Implementasi Struktur Data, Informatika, Bandung, 2006