SENARAI BERANTAI(LINKED LIST)

 1.Senarai Berantai(Linked List) adalah jenis struktur data yang berisi kumpulan data yang tersusun secara linier dengan masing-masing data disimpan dalam sebuah simpul dan antara satu simpul dengan simpul lain dihubungkan melalui pointer.

Bentuk dasarnya membuat data disisipkan kedalam senarai melalui salah satu ujungnya.

2. Berikut merupakan jenis-jenis Linked List :

1.Singly Linked List :

Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya dan juga memiliki field yang berisi data.Akhir linked list ditandai dengan node terakhir akan menunjuk ke null yang akan digunakan sebagai kondisi berhenti saat pembacaan linked list.

2.Double Linked List :

Linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu: 1 field pointer yang menunjuk ke pointer berikutnya, 1 field pointer yang menunjuk ke pointer sebelumnya dan field yang berisi data dari node tersebut. Pointer next dan prev-nya menunjuk ke null.

3.Single Circular Linked List :

Single Linked List yang pointer next-nya menunjuk ke dirinya sendiri, jika terdiri dari beberapa node maka pointer terakhirnya akan menunjuk ke pointer terdepannya.

4.Double Circular Linked List :

Double Linked List yang pointer next dan prev-nya menunjuk ke dirinya sendiri secara circular.

Jika dilihat pengaksesannya, Linear dan Circular Linked List dapat dibedakan sebagai berikut :

Linear Linked List	Circular Linked List
Tail.next dihubungkan ke null	Tail.next dihubungkan ke head
Pada perulangan, akan break pada now = null	Pada perulangan, akan break pada now = null
Method lebih sederhana	Method lebih sulit debandingkan dengan Linear linked list
Algoritma akan lebih sulit jika kita melakukan penyelesaian masalah dengan menggunakan konsep circular queue	Akan lebih mudah pada konsep – konsep tertentu salah satunya seperti konsep queue.

Menurut saya, lebih baik membiasakan diri untuk menggunakan circular linked list. Karena akan lebih membantu mempersingkat langkah – langkahnya. Akan tetapi berbeda lagi jika kita melihat dari segi kemudahannya. Akan lebih mudah jika kita menggunakan Linear list karena tidak harus menghubungkan tail dan head.

3. Operasi-Operasi yang ada pada Linked List

1.Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
2.IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
3.Find First
Fungsi ini mencari elemen pertama dari linked list
4.Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
5.Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.

 6.update

          Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu

          7.Delete Now

          Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus

          adalah elemen pertama dari linked list (head), head akan berpindah ke

          elemen berikut.

         8.Delete Head

         Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen

         sesudahnya.

         9.Clear

         Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan

         bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda

         melakukannya, data-data yang dialokasikan ke memori pada program

         sebelumnya akan tetap tertinggal di dalam memori.

        Operasi Penghapusan

 Penghapusan node dilakukan dengan memutus rantai node

       kemudian menghapus node. Jika node berada di tengah rangkaian,

      rangkaian yang terputus perlu disambung kembali. Untuk

      memudahkan penghapusan simpul dibutuhkan dua cursor sebagai

      simpul bantu. Selain cursor juga dibutuhkan simpul head sebagai

      acuan awal simpul dalam rangkaian.

     Berikut langkah langkah untuk menghapus simpul dalam rangkaian:

•      Buat cursor bantu yang menunjuk ke awal node(simpul).

•      Pindahkan cursor ke node berikutnya

•      Putus sambungan awal node dengan node berikutnya.

•      Hapus rangkaian

•      Jika berada di akhir rangkaian, putuskan dari rangkaian sebelumnya.

•      Jika di tengah rangkaian, pindahkan penunjukan node berikutnya,atau di akhir, atau setelah node yang akan dihapus

    Pengertian:

    Node : rangkaian beberapa simpul

    Single : artinya field pointer-nya hanya satu buah saja dan satu arah.

    Linked List : artinya node-node tersebut saling terhubung satu sama lain.

   Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar

  

4.Algoritma dancontoh program untuk operasi didalamnya

1. Linked List Circular

Double Linked List    
       Pengertian secara umumnya DLLC itu Linked list yang menggunakan pointer, dimana setiap node memiliki 3 field, yaitu:
1 field pointer yang menunjuk pointer berikutnya "next",
1 field menunjuk pointer sebelumnya " prev ",
1 field yang berisi data untuk node tersebut .

Double Linked List Circular pointer next dan prev nya menunjuk kedirinya sendiri secara circular. Bentuk Node DLLC

 

contoh program Double Linked List 

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

struct node

{

        struct node *prev;

        int data;

        struct node *next;        

};

typedef struct node node;

node *pHead = NULL;

node *alokasiNodeBaru()

{ 

  node *pNew = NULL; 

  pNew = (node *) malloc(sizeof(node)); 

  return(pNew); 

}
void tambahAwal(node *pNew)

{

     printf("masukkan bilangan: "); scanf("%d",&pNew->data);

     

     if(pHead == NULL)

{

              pNew->prev = pHead;

              pNew->next = pHead;

              pHead = pNew;

     }

     else

    {

              //cari node yang menunjuk ke pHead

              pNew->prev = pHead;

              pNew->next = pHead;

              pHead->prev= pNew;

              pHead = pNew;   

     }

}
void cetak()

{

     node *pWalker = pHead; int i=1;

     while(pWalker!=NULL)

{

         printf("node ke-%d = %d\n",i,pWalker->data);

         i++;

         pWalker=pWalker->next;        

     }

     printf("NULL\n");

}

void tambahTengah(node *pNew)

{

     node *pWalker;

     pWalker=pHead;

     int nilai,sisip;

     printf("masukkan nilai yang ingin ditambahkan: "); scanf("%d",&pNew->data);

     cetak(); 

     printf("data disisipkan setelah nilai : "); scanf("%d",&sisip);

     while(pWalker!=NULL && pWalker->data!=sisip)

{

                         pWalker=pWalker->next; 

}

                       

     if(pWalker==NULL) {printf("\ndata tidak ditemukan"); getch();

}

     else 

{

           pNew->next=pWalker->next;

           pWalker->next->prev=pNew;

           pWalker->next=pNew;

           pNew->prev=pWalker;

           }

}
void tambahAkhir(node *pNew)

{

     node *pEnd;

     pEnd=pHead;

     printf("masukkan nilai yang ingin ditambahkan: "); scanf("%d",&pNew->data);   

     while(pEnd->next!=NULL)

{

                         pEnd=pEnd->next; 

}

     pEnd->next=pNew;

     pNew->prev=pEnd;

     pNew->next=NULL;        

}
void hapusAwal()

{

     node *pHapus;

     pHapus=pHead;

     pHead=pHead->next;

     pHead->prev=NULL;

     free(pHapus);

}
void hapusTengah()

{

     node *pCari;int hapus;

     pCari=pHead;

     cetak();

     printf("masukkan bilangan yang ingin dihapus: "); scanf("%d",&hapus);

     while(pCari!=NULL && pCari->data!=hapus)

{

                               pCari=pCari->next;

                               }                      

    pCari->prev->next=pCari->next;

    pCari->next->prev=pCari->prev;

     free(pCari);

}
void hapusAkhir()

{

     node *pEnd;

     pEnd=pHead;

     while(pEnd->next!=NULL)

{

                              pEnd=pEnd->next;

                              }

     pEnd->prev->next=NULL;

     free(pEnd); 

}  

 int main(int argc, char *argv[])

 {

    node *pNew; int pilih,bil;

    do{system("cls");

    printf("----------MENU-----------");

    printf("\n1.tambah awal");

    printf("\n2.tambah tengah");

    printf("\n3.tambah akhir");

    printf("\n4.hapus awal ");

    printf("\n5.hapus tengah");

    printf("\n6.hapus akhir");

    printf("\n7.cetak");

    printf("\n9.exit");

    printf("\npilihan : ");scanf("%d",&pilih);

    if(pilih==1){pNew=alokasiNodeBaru();

                 tambahAwal(pNew); 

                 }

    else if(pilih==2){pNew=alokasiNodeBaru();

                 tambahTengah(pNew);

                 }

    else if(pilih==3){pNew=alokasiNodeBaru();

                 tambahAkhir(pNew);

                 }

    else if(pilih==4){hapusAwal();

}

    else if(pilih==5){hapusTengah();

}

    else if(pilih==6){hapusAkhir();

}

    else if(pilih==7){cetak();getch();

}                        

}

  while(pilih!=9);

  

  printf("\n");

  system("PAUSE");    

  return 0;

}

Single Linked List         

     Single Linked List Circular (SLLC) adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

contoh program Single Linked List

// Program for singly linked Circular list #include <iostream>

#include <string> struct SLinkCircularList

{

    std::string data;

    SLinkCircularList *next;

    SLinkCircularList() : data(""), next(this) 

{ 

}

    SLinkCircularList(const char *value) : data(value), next(this)

 { 

}     SLinkCircularList* InsertNext(const char *data)

    {

        SLinkCircularList *node = new SLinkCircularList(data);

        if(this->next == this) // only one node in the circular list

        {

            // Easy to handle, after the two lines of executions,

            // there will be two nodes in the circular list

            node->next = this;

            this->next = node;

        }

        else

        {

            // Insert in the middle

            SLinkCircularList *temp = this->next;

            node->next = temp;

            this->next = node;

        }

        return node;

    }     bool DeleteNext()

    {

        if(this->next == this)

        {  

            std::cout << "\nThe node can not be deleted as there is only one node in the circular list\n";

            return false;

        }

        SLinkCircularList *pNode = this->next;

        this->next = this->next->next; 

        delete pNode;

    }     void Traverse(SLinkCircularList *node = NULL)

    {

        if(node == NULL)

            node = this;

        std::cout << "\n\nTraversing in Forward Direction\n\n";

        SLinkCircularList *startnode = node;

        do

        {

            std::cout << node->data;

            std::cout << "\n";

            node = node->next;

        }

        while(node != startnode);

    }     int GetNumberOfNodes(SLinkCircularList *node = NULL)

    {

        if(node == NULL)

            node = this;

        int count = 0;

        SLinkCircularList *startnode = node;

        do

        {

            count++;

            node = node->next;

        }

        while(node != startnode);

        std::cout << "\nCurrent Node Value: " << node->data.c_str();

        std::cout << "\nTotal nodes in Circular List: " << count;

        std::cout << "\n";

        return count;

    }

}; int main()

{

    SLinkCircularList *node1 = new SLinkCircularList("ONE");

    node1->DeleteNext(); // Delete will fail in this case.

    SLinkCircularList *node2 = node1->InsertNext("TWO");

    node1->DeleteNext(); // It will delete the node2.

    node2 = node1->InsertNext("TWO"); // Insert it again

    SLinkCircularList *node3 = node2->InsertNext("THREE");

    SLinkCircularList *node4 = node3->InsertNext("FOUR");

    SLinkCircularList *node5 = node4->InsertNext("FIVE");

    node1->GetNumberOfNodes();

    node3->GetNumberOfNodes();

    node5->GetNumberOfNodes();

    node1->Traverse();

    node3->DeleteNext(); // delete the node "FOUR"

    node2->Traverse();

    std::cout << "\n";  

    node1->GetNumberOfNodes();

    node3->GetNumberOfNodes();

    node5->GetNumberOfNodes();

    std::cout << "\n";

    return 0;

}

2. Linked List Non Circular

Double Linked List Non Circular (DLLNC)
   adalah Double Linked List yang memiliki 2 buah pointer yaitu pointernext dan prev.
Pointer next menunjuk pada node setelahnya dan pointer prev menunjuk pada node sebelumnya.
Pengertian:
Double : artinya field pointer-nya dua buah dan dua arah, ke node sebelum dan sesudahnya.
Linked List : artinya node-node tersebut saling terhubung satu sama lain.
Non Circular : artinya pointer prev dan next-nya akan menunjuk pada NULL. 

Single Linked List Non Circular (SLLNC)

             Adalah Linked List yang pointer nya selalu mengarah ke Node yang menampung *next bernilai NULL, jadi arahnya tidak menunjuk pointer didepannya sehingga tidak dapat kembali ke pointer - pointer sebelumnya. SLLNC ini juga memiliki 2 bagian, ada Tambah dan ada Hapus, masing - masing bagian ini juga masih meliputi 3 fungsi lain yaitu Belakang, Tengah, dan depan. untuk Contoh Tambah & Hapus (Depan & belakang).

 

Contoh Program Single Linked List Non Circular (Tambah : Depan & belakang dan Hapus : Depan & Belakang) 

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

#include <alloc.h>

int pil;

void pilih();

void buat_baru();

void tambah_belakang();

void tambah_depan();

void hapus_belakang();

void hapus_depan();

void tampil();

struct simpul

{

    char nim[8], nama [20];

    int umur;

    struct simpul *next;

} mhs, *baru, *awal=NULL, *akhir=NULL,*hapus,*bantu;

int main()

{

    do

    {

        clrscr();

        cout<<"MENU SINGLE LINKEDLIST"<<endl;

        cout<<"1. Tambah Depan"<<endl;

        cout<<"2. Tambah Belakang"<<endl;

        cout<<"3. Hapus Depan"<<endl;

        cout<<"4. Hapus Belakang"<<endl;

        cout<<"5. Tampilkan"<<endl;

        cout<<"6. Selesai"<<endl;

        cout<<"Pilihan Anda : ";

        cin>>pil;

        pilih();

    } while(pil!=6);

    return 0;

}

void pilih()

{

    if(pil==1)

        tambah_depan();

    else if(pil==2)

        tambah_belakang();

    else if(pil==3)

        hapus_depan();

     else if(pil==4)

        hapus_belakang();

      else if(pil==5)

        tampil();

    else

        cout<<"selesai";

}

void buat_baru()

{

    baru=(simpul*)malloc(sizeof(struct simpul));

    cout<<"input nim   : ";cin>>baru->nim;

    cout<<"input nama  : ";cin>>baru->nama;

    cout<<"input umur  : ";cin>>baru->umur;

    baru->next=NULL;

}

void tambah_belakang()

{

    buat_baru();

    if(awal==NULL)

    {

        awal=baru;

    }

    else

    {

        akhir->next=baru;

    }

    akhir=baru;

    akhir->next=NULL;

    cout<<endl<<endl;

    tampil();

}

void tambah_depan()

{

    buat_baru();

    if(awal==NULL)

    {

        awal=baru;

        akhir=baru;

        akhir->next=NULL;

    }

    else

    {

        baru->next=awal;

        awal=baru;

    }

    cout<<endl<<endl;

    tampil();

}

void hapus_depan()

{

    if (awal==NULL)

        cout<<"Kosong";

    else

    {

        hapus=awal;

        awal=awal->next;

        free(hapus);

    }

   cout<<endl<<endl;

    tampil();

}

void hapus_belakang()

{

    if (awal==NULL)

        cout<<"Kosong";

    else if(awal==akhir)

    {

         hapus=awal;

         awal=awal->next;

         free(hapus);

    }

    else

    {

        hapus=awal;

        while(hapus->next!=akhir)

             hapus=hapus->next;

        akhir=hapus;

        hapus=akhir->next;

        akhir->next=NULL;

        free(hapus);

    }

    cout<<endl<<endl;

    tampil();

}

void tampil()

{

     if (awal==NULL)

          cout<<"Kosong";

     else

     {

         bantu=awal;

         while(bantu!=NULL)

         {

            cout<<"nim : "<<bantu->nim;

            cout<<"  nama : "<<bantu->nama;

            cout<<"  umur : "<<bantu->umur<<endl;

            bantu=bantu->next;

         }

     }

     getch();

}