Pembuatan Linked List Pada C++

Salah satu bentuk struktur data yang berisi kumpulan data yang tersusun secara sekuensial, saling bersambungan, dinamis adalah senarai berkait (linked list).Suatu senarai berkait (linked list) adalah suatu simpul (node) yang dikaitkan dengan simpul yang lain dalam suatu urutan tertentu. Suatu simpul dapat berbentuk suatu struktur atau class. Simpul harus mempunyai satu atau lebih elemen struktur atau classyang berisi data.
Secara teori, linked list adalah sejumlah node yang dihubungkan secara linier dengan bantuan pointer. Dikatakan single linked apabila hanya ada satu pointer yang menghubungkan setiap node single artinya field pointernya 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. 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 rinci, senarai berkait lebih efisien di dalam melaksanakan penyisipan-penyisipan dan penghapusan-penghapusan. Senarai berkait juga menggunakan alokasi penyimpanan secara dinamis, yang merupakan penyimpanan yang dialokasikan pada runtime . Karena di dalam banyak aplikasi, ukuran dari data itu tidak diketahui pada saat kompile, hal ini bisa merupakan suatu atributyang baik juga. Setiapnodeakan berbentuk struct dan memiliki satu buahfield bertipe structyang sama, yang berfungsi sebagai pointer.
Dalam menghubungkan setiap node, kita dapat menggunakan cara first-create-first-access ataupun first-createlast-access. Yang berbeda dengan deklarasi struct sebelumnya adalah satu field bernama next, yang bertipe struct node. Hal ini sekilas dapat membingungkan. Namun, satu hal yang jelas, variabel next ini akan menghubungkan kita dengan node di sebelah kita, yang juga bertipe struct node.Hal inilah yang menyebabkan next harus bertipe struct node
Deklarasi node:
struct node
{
char nama[20]
; int umur;
float tinggi;
node *next; // Pointer menyambung ke node selanjutnya
};

Gambar sebuah node

• Bagian pertama, disebut medan informasi, berisi informasi yang akan disimpan dan diolah.
• Bagian kedua, disebut medan penyambung (link field), berisi alamat simpul berikutnya

Pada gambar di atas, pointer awal menunjuk ke simpul pertama dari senerai tersebut. Medan penyambung (pointer) dari suatu simpul yang tidak menunjuk simpul lain disebut pointer kosong, yang nilainya dinyatakan sebagai null (null adalah kata baku yang berarti bahwa pointer 0 atau bilangan negatif). Jadi kita bisa melihat bahwa dengan hanya sebuah pointer Awal saja maka kita bisa membaca semua informasi yang tersimpan dalam senerai

MENAMBAH SIMPUL DI BELAKANG
Sekarang kita akan mempelajari bagaimana menambah simpul baru ke dalam senerai berantai. Kita anggap bahwa simpul baru yang akan ditambah selalu menempati posisi setelah posisi yang terakhir dari senerai berantai yang diketahui. Untuk menjelaskan operasi ini baiklah kita gunakan deklarasi pointer dan simpul seperti di bawah ini:
struct node
{
char nama[20];
int umur;
float tinggi;
node *next;
};
Menambahkan simpul diakhir list
Misalkan simpul baru yang dibentuk diberi nama temp. Untuk menambahkan simpul baru perlu kita uji apakah Linked list masih kosong atau tidak. Linked list yang kosong ditandai dengan awal_ptr bernilai NULL. Jika tidak kosong maka dibaca senarai yang ada mulai dari posisi awal sampai terakhir misalkan dengan menggunakan pointer temp2. Simpul terakhir ditandai dengan medan penyambung dari temp2 bernilai NULL.Jika sudah berada pada simpul terakhir kita tunjukkan medan penyambung temp2 dengan temp.
Program lengkap menambahkan simpul diakhit senarai sebagai berikut:

node *temp, *temp2; // pointer sementara

// Isi data temp = new node; //menciptakan node baru
cout << "Nama : ";cin >> temp->nama;
cout << "Umur : ";cin >> temp->umur;
cout << "Tinggi : ";cin >> temp->tinggi;
temp->next = NULL;
// Inisialisasi pointer ketika masih kosong
if (awal_ptr == NULL)
{
awal_ptr = temp;
posisi = awal_ptr;
}
else
{
temp2 = awal_ptr; // list tidak kosong
while (temp2->next != NULL)
{
temp2 = temp2->next;
// pindah ke link berikutnya
}
temp2->next = temp;
}

Menghapus simpul diakhir list kita gunakan cara sebagai berikut :

Untuk menghapus simpul diakhir perlu kita uji apakah senarai masih kosong atau tidak, jika kosong tampilkan pesan bahwa list masih kosong. Jika tidak kosong perlu diuji apakah jumlah simpul dalam senarai hanya satu yang ditandai dengan medan penyambung yang bernilai null. Jika simpul lebih dari satu maka dibaca semua simpul sampai simpul terakhir yaitu medan penyambung bernilai null.

node *temp1, *temp2;
if (awal_ptr == NULL)
cout << "List kosong!" << endl;
else
{
temp1 = awal_ptr;
if (temp1->next == NULL)
{
delete temp1
; awal_ptr = NULL;
}
else
{
while (temp1->next != NULL)
{
temp2 = temp1;
temp1 = temp1->next;
} delete temp1; temp2->next = NULL; }
}

Menghapus simpul diawal list

Menghapus simpul diawal dilakukan dengan cara menampung simpul awal pada pointer temp, kemudian mengarahkan awal_ptr ke simpul selanjutnya. Kemudian simpul yang ditampung dalam pointer temp dihapus.

node *temp;
temp = awal_ptr;
awal_ptr = awal_ptr->next;
delete temp;

Menampilkan list
Sebelum menampilkan linked list perlu kita uji apakah senarai kosong atau tidak. Jika senarai kosong kita tampilkan pesan bahwa List kosong. Jika senarai tidak kosong maka kita baca senarai mulai posisi awal sampai simpul terakhir.

node *temp;
temp = awal_ptr;
cout << endl;
if (temp == NULL)
cout << "List kosong!" << endl;
else
{
while (temp != NULL)
{
// Menampilkan isi cout << "Nama : " << temp->nama << " ";
cout << "Umur : " << temp->umur << " ";
cout << "Tinggi : " << temp->tinggi;
if (temp == posisi)
cout << " <– Posisi node";
cout << endl; temp = temp->next;
}
cout << "Akhir list!" << endl;
}

Program Lengkap:

#include <iostream.h> 
struct node {
    char nama[20];
    int umur;
    float tinggi;
    node *next;
 };
 node *awal_ptr=NULL;
 node *posisi;
 int pilih; 

void tambah_simpul_akhir()
 {
  node *temp, *temp2; //simpul sementara
   //isi data
    temp=new node;
    cout<<"Nama   : ";cin>>temp->nama;
    cout<<"Umur   : ";cin>>temp->umur;
    cout<<"Tinggi : ";cin>>temp->tinggi;
    temp->next=NULL;
    //inisialisasi pointer ketika kosong
    if(awal_ptr==NULL)
    {
      awal_ptr=temp;
      posisi=awal_ptr;
    }
    else
    {
     temp2=awal_ptr;
     while(temp2->next != NULL)
       {
          temp2 = temp2->next;
       }
       temp2->next=temp;
    }
 }

void tampil_senarai()
 {
    node *temp;
    temp = awal_ptr;
    if(temp == NULL)
       cout<<"List kosong"<<endl;
    else
    {
       cout<<endl<<endl;
       while(temp != NULL)
       {
          cout<<"Nama : "<<temp->nama<<"  ";
          cout<<"Umur : "<<temp->umur<<"  ";
          cout<<"Tinggi : "<<temp->tinggi;
          if (temp == posisi) 
             cout<<"   << posisi simpul";
          cout<<endl;
          temp=temp->next; 

      }
      cout<<"Akhir list"<<endl;
    }
} 
void hapus_simpul_akhir()
 {
  node *temp1, *temp2;
  if (awal_ptr == NULL)
   cout << "List kosong!" << endl;
  else
  {
   temp1 = awal_ptr;
   if (temp1->next == NULL)
   {
    delete temp1;
    awal_ptr = NULL;
   }
   else
   {
   while (temp1->next != NULL)
    {
     temp2 = temp1;
     temp1 = temp1->next;
    }
    delete temp1;
    temp2->next = NULL;
   }
  }
 }
 void hapus_simpul_awal()
 {
  node *temp;
  temp = awal_ptr;
  awal_ptr = awal_ptr->next;
  delete temp;
 } 

void main() 
{
    awal_ptr=NULL;
    do
    {
      tampil_senarai();
      cout<<"Menu Pilihan"<<endl;
      cout<<"0. Keluar program"<<endl;
      cout<<"1. Tambah simpul akhir"<<endl;
      cout<<"2. Hapus simpul akhir"<<endl;
      cout<<"3. Hapus simpul awal"<<endl;
      cout<<"Pilihan >> ";cin>>pilih;
      switch(pilih)
       {
          case 1: tambah_simpul_akhir();break;
          case 2: hapus_simpul_akhir();break;
          case 3: hapus_simpul_awal();break;
       }
    }
  while(pilih !=0); 
}

Menambah Simpul di Depan Adalah menambahkan simpul baru yang dimasukkan diawal list. Proses penambahan simpul diawal list diilustrasikan sebagai berikut:

1. List masih kosong maka awal_ptr bernilai NULL (awal_ptr=NULL)
   
2. Masuk simpul baru, misalkan data A
   
3. Menambakan simpul diawal simpul A, misalkan simpul B Baru->next diisi dengan alamat dimana simpul data A berada, kemudian awal_ptr ditunjukkan ke simpul baru yang diciptakan.

Program :
 if(awal_ptr == NULL)
 {
  awal_ptr=baru;
  awal_ptr->
  next = NULL; 
} 
else
 {
  baru->
 next = awal_ptr;
 awal_ptr = baru; 
}  
Menambah Simpul di Tengah Proses penambahan di tengah berarti proses penyisipan data pada posisi tertentu. Oleh karena itu, posisi penyisipan sangat diperlukan. Ada beberapa kondisi yang harus diperhatikan ketika ingin melakukan penyisipandata, yaitu kondisi ketika linked list masih kosong, dan ketika linked list sudah mempunyai data. Proses penambahan data ketika linked list sudah mempunyai data. Ada 3 kondisi yang terjadi ketika akan melakukan proses penyisipan pada linked list yang sudah mempunyai data adalah :

1. Posisi penyisipan di luar dari jangkauan linked list (posisi kurang dari 1 atau melebihi banyak data yang ada di linked list). Pada proses ini, jika terjadi posisi penyisipan kurang dari 1 maka proses yang dilakukan adalah proses penambahan data di awal, dan jika posisi diluar (>) dari banyak data maka proses yang dilakukan adalah proses penambahan data di akhir.
2. Posisi penyisipan di dalam jangkauan linked list. Contoh kalau ingin menyisipkan data pada posisi ke-3 (posisi_sisip=3). 

Program :
 if(awal_ptr != NULL) 
 {
 cout<<"Akan disisip setelah Data Ke ? : ";
 cin>>posisi_sisip;
 bantu=awal_ptr;
 baru =new node;
 for(int i=1;i<posisi_sisip-1;i++) 
{
   if(bantu->next != NULL) 
      bantu=bantu->next; else break;
 }
 cout << "Masukkan Nama : ";
 cin >> baru->nama;
 cout << "Masukkan Umur : ";
 cin >> baru->umur; 
cout << "Masukkan tingggi : ";
 cin >> baru->tinggi; baru->
next=bantu->next;
 bantu->next=baru; 
} 
else
 {
  cout<<"Belum ada data !! silahkan isi data dulu...."; 
  getch(); 
 } 
}

Menghapus Simpul di Tengah Menghapus tengah sebuah simpul adalah menghilangkan simpul dari deret linked list. Misalkan kita akan menghapus simpul pada posisi 3

Program:
if(awal_ptr != NULL)
   {
     cout<<" Akan dihapus pada data ke : ";
     cin>>posisi_hapus;
     banyakdata=1;
     bantu=awal_ptr;
    while(bantu->next != NULL)
    {
       bantu=bantu->next;
       banyakdata++;
    }
   if((posisi_hapus<1)||(posisi_hapus>banyakdata))
   {
     cout<<"Belum ada data !! masukkan Data dula aja...\n";
    }
   else
   {
      bantu=awal_ptr;
      poshapus=1;
     while(poshapus<(posisi_hapus-1))
     {
       bantu=bantu->next;
       poshapus++;
     }
   hapus=bantu->next;
   bantu->
   next=hapus->next;
   delete hapus;
   }
}
else
cout<<"Data Masih kosong, tidak bisa hapus data dari tengah! ";
getch();
}

Program lengkap:

#include <iostream.h> 
#include <conio.h> 
struct node 
{
  char nama[20];
  int umur;
  float tinggi;
  node *next; 
}; 


node *awal_ptr = NULL;
  node *posisi;         //digunakan untuk membaca sepanjang list 
  int option = 0; 

void tambah_awal_list()
{
  node *baru;
  baru = new node;
  cout << "Masukkan Nama     : ";
  cin >> baru->nama;
  cout << "Masukkan Umur     : ";
  cin >> baru->umur;
  cout << "Masukkan tingggi  : ";
  cin >> baru->tinggi;
  baru->next = NULL;
  if(awal_ptr == NULL)
  {
    awal_ptr=baru;
    awal_ptr->next = NULL;
  }
  else
  {
    baru->next = awal_ptr;
    awal_ptr = baru;
  }
} 

void menambah_node_di_akhir()
  {
  node *temp, *temp2;   // Temporary pointers 
  // menciptakan node baru 
  temp = new node; 
  cout << "Masukkan Nama     : "; 
  cin >> temp->nama;  cout << "Masukkan Umur     : ";
  cin >>   temp->umur;  cout << "Masukkan tingggi  : ";
  cin >> temp->tinggi;  temp->next = NULL; 

// Set up link pada node
  if (awal_ptr == NULL)
  {
    awal_ptr = temp;
    posisi = awal_ptr;
  }
  else
  {
    temp2 = awal_ptr;
    // node tidak NULL – list tidak kosong
    while (temp2->next != NULL)
    {
      temp2 = temp2->next; 
      // Memindahkan pada next link dalam rantai
    }
  temp2->next = temp;
  }
} 

void display_list()
{
  node *temp;
  temp = awal_ptr;
  cout << endl;
  if (temp == NULL)
    cout << "List kosong!" << endl;
  else
  {
    while (temp != NULL)
    {  // Menampilkan detail data
     cout << "nama : " << temp->nama << "  ";
     cout << "umur : " << temp->umur << "  ";
     cout << "tinggi : " << temp->tinggi;
     if (temp == posisi)
        cout << "     <<<< posisi node";
     cout << endl;
     temp = temp->next; 
    }
    cout << "Akhir list!" << endl;
  }
} 

void hapus_awal_node()
{
  node *temp;
  temp = awal_ptr;
  awal_ptr = awal_ptr->next;
  delete temp;
} 

void hapus_akhir_node()
{
  node *temp1, *temp2;
  if (awal_ptr == NULL)
    cout << "List kosong!" << endl;
  else
  {
    temp1 = awal_ptr;
    if (temp1->next == NULL)
    {
      delete temp1;
      awal_ptr = NULL;
    }
    else 
    {
      while (temp1->next != NULL)
      {
        temp2 = temp1;
        temp1 = temp1->next;
      }
      delete temp1;
      temp2->next = NULL;
    }

   }
} 

void pindah_posisi_sebelumnya()
{
  if (posisi->next == NULL)
  cout << "Kamu berada pada akhir list." << endl;
  else
  posisi = posisi->next; 
} 

void pindah_posisi_berikutnya()
{
  if (posisi == awal_ptr)
    cout << "Kamu berada pada awal list" << endl;
  else
  {
    node *previous;     // deklarasi pointer
    previous = awal_ptr; 
    while (previous->next != posisi) 
    { 
      previous = previous->next;
    }
    posisi = previous;
  }
}

void tambah_tengah_list()
{
  node *baru, *bantu;
  int posisi_sisip;
  if(awal_ptr != NULL)
  {
    cout<<"Akan disisip setelah Data Ke ? : ";
    cin>>posisi_sisip;
    bantu=awal_ptr;
    baru =new node;
    for(int i=1;i<posisi_sisip-1;i++) {
      if(bantu->next != NULL)
        bantu=bantu->next;
      else
        break; 
    }
  cout << "Masukkan Nama     : ";
  cin >> baru->nama;
  cout << "Masukkan Umur     : ";
  cin >> baru->umur;
  cout << "Masukkan tingggi  : ";
  cin >> baru->tinggi;
  baru->next=bantu->next;
  bantu->next=baru;
  }
  else
  {
    cout<<"Belum ada data !! silahkan isi data dulu....";
    getch();
  } 
} 
void Hapus_tengah_list()
{
  int banyakdata,posisi_hapus,poshapus;
  node *hapus, *bantu;
  if(awal_ptr != NULL)
  {
    cout<<" Akan dihapus pada data ke : ";
    cin>>posisi_hapus;
    banyakdata=1;
    bantu=awal_ptr;
    while(bantu->next != NULL)
    {
      bantu=bantu->next;
      banyakdata++;
    }
    if((posisi_hapus<1)||(posisi_hapus>banyakdata))
    {
      cout<<"Belum ada data !! masukkan Data dula aja...\n";
    }
    else
    {
      bantu=awal_ptr;
      poshapus=1;
      while(poshapus<(posisi_hapus-1))
      {
        bantu=bantu->next;
        poshapus++;
      }
      hapus=bantu->next;
      bantu->next=hapus->next;
      delete hapus;
    }
 }
 else 
    cout<<"Data Masih kosong, tidak bisa hapus data dari tengah! ";
 getch();
}
 

int main()
{
  awal_ptr = NULL;
  do
  {
    clrscr();
    display_list();
    cout << endl;
    cout << "MENU PILIHAN : " << endl;
    cout << "0. Keluar program." << endl;
    cout << "1. Tambah awal list." << endl;
    cout << "2. Tambah akhir list." << endl;
    cout << "3. Tambah tengah list."<< endl;
    cout << "4. Hapus awal list." << endl;
    cout << "5. Hapus akhir list." << endl;
    cout << "6. Hapus tengah list." << endl;
    cout << "7. Pindah posisi pointer ke berikutnya." << endl;
    cout << "8. Pindah posisi pointer ke sebelumnya." << endl;
    cout << endl << " Pilihan >> ";
    cin >> option; 

switch (option)
  {
  case 1 : tambah_awal_list(); 
    break;
  case 2 : menambah_node_di_akhir();
    break;
  case 3 : tambah_tengah_list();
    break;
  case 4 : hapus_awal_node();
    break;
  case 5 : hapus_akhir_node();
    break;
  case 6 : Hapus_tengah_list();
    break;
  case 7 : pindah_posisi_sebelumnya();
    break;
  case 8 : pindah_posisi_berikutnya();
  }
 }  
while (option != 0); 
}