Kamis, 14 Maret 2013

Link List



LINK LIST
Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian Linked list juga merupakan suatu cara untuk menyimpan data dengan struktur sehingga dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data yangdiperlukan. Struktur ini lebih dinamis karena banyaknya elemen dengan mudah ditambah atau dikurangi, berbeda dengan array yang ukurannya tetap. berikut gambaran kecil mengenai linked list.
 Didalam Linked List terdapat beberapa bagian lagi.

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();
}
Diposting oleh di

2 komentar:

Langganan: Posting Komentar (Atom)