Struktur Data Linier

Salah satu bentuk struktur data yang berisi kumpulan data yang tersusun secara sekuensial,saling bersambung,dan dinamis.Secara lain linked list adalah node(simpul) yang dihubungkan secara linier dengan bantuan pointer. pointer bersifat dinamis,variabel akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan dapatdirelokasikan kembali

Setiap ingin menambahkan data, Anda selalu menggunakan variabel pointer yang baru, akibatnyaAnda akan membutuhkan banyak sekali pointer. Oleh karena itu, ada baiknya jika Anda hanyamenggunakan satu variabel pointer saja untuk menyimpan banyak data dengan metode yang kitasebut Linked List. Linked list adalah sekumpulan elemen bertipe sama, yang mempunyaiketerurutan tertentu, yang setiap elemennya terdiri dari dua bagian. Linked list digambarkansebagai berikut : 

 

sebuah list linier dikenali :

•   elemen pertamanya, biasanya melalui alamat elemen pertama yang disebut : First

•  alamat elemen berikutnya (suksesor), jika kita mengetahui alamat sebuah elemen, yangdapat diakses melalui informasi NEXT. NEXT mungkin ada secara eksplisit (seperti contohdi atas), atau secara implisit yaitu lewat kalkulasi atau fungsi suksesor

•  setiap elemen mempunyai alamat, yaitu tempat elemen disimpan dapat diacu. Untukmengacu sebuah elemen, alamat harus terdefinisi. Dengan alamat tersebut informasi yangtersimpan pada elemen list dapat diakses.   

list linier paling sederhana digambarkan dengan ilustrasi sebagai berikut :

 

      1. Single Linked List

Single Linked List adalah sebuah linked list yang menggunakan sebuah variable pointer saja untuk menyimpan banyak data dengan menggunakan metode linked list,suatu daftar isi yang saling berhubungan.

                  a)   Single Linked List Circular

Single Linked List Circular 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 terkahir akan menujuk ke node terdepanya.

                  b)   Single Linked List Non Circular

Single Linked List Non Circular adalah Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.

    2.   Double Linked List

Double Linked List adalah file pointernya terdiri dari dua buah dan dua arah,yaitu next dan prev.

                  a)   Double Linked List Non Circular

Double Linked List Non Circular adalah linked list dengan menggunakan pointer,dimana setiap node memiliki 3 field,yaitu pointer yang menunjuk pointer next,1 pointer yang menunjuk prev,serta sebuah fiel yang berisi data untuk node tersebut.

                  b)   Double Linked List Circular

Double linked list circular hampir sama dengan non circular namun disini pointer next dan prev-nya menunjuk ke dirinya sendiri secara circular.

PENAMBAHAN DATA

a)      Tambah di depan:penambahan node baru akan dikaitkan di node paling depan,namun pada saat pertama kali(data masih kosong),maka penambahn data dilakukan pada headnya.

b)      Tambah di belakang: Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya. Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, namun tidak diperlukan loop karena untuk mengetahui node terbelakang hanya perlu menunjuk pada head®prev saja. Kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.

c)      Sisip Tengah: Proses penambahan di tengah berarti proses penyisipan data pada posisi tertentu

PENGHAPUSAN DATA

a)      Hapus Data Depan adalah menghapus data yang berada di node pertama.Menghapus data pertama tidak boleh dilakukan jika node sedang ditunjuk oleh pointer,sehingga harus menggunakan pointer lain untuk menunjukan node  yang akan dihapus.

b)      Hapus Data Belakang adalah menghapus data yang berada di node terakhir.Untuk menghapus data di belakang di butuhkan 2 pointer tambahan yaitu pointer bantu dan pointer hapus.Pointer hapus menunjuk node yang akan dihapus sedangkan poniter bantu untuk menunjukan node sebelum node yang dihapus yang kemudian akan menjadi node terkhir.

c)      Hapus data tengah adalah menghapus data yang berada diantara dua node.

TUMPUKAN(STACK)

Tumpukan (stack) adalah sekumpulan data yang organisasi atau strukturnya berupa tumpukan. Elemen-elemen baru atau biasa disebut simpul (node) dapat diletakkan maupun diambil dari sebuah tumpukan hanya dari bagian akhir (atas). Oleh sebab itu, maka tumpukan mengacu pada struktur LIFO (Last In First Out), yaitu elemen yang terakhir masuk adalah yang awal dapat dikeluarkan. Kadang juga disebut struktur FILO (First In Last Out).

STRUCT 

Struct adalah sekumpulan variabel yang masing masing dapat berbeda tipe, dan dikelompokkan ke dalam satu nama. Struct ini sering digunakan untuk mendefinisikan suatu rekord data yang disimpan di dalam file. Struct mirip representasi sebuah object beserta propertiesnya.

CLASS

Class adalah tempat meniyimpannya algoritma agar  lebih mudah digunakan di program  lain.Di dalam class ada yang di maksud dengan private dan public.Private adalah variabel/method hanya dapat diakses oleh kelas itu sendiri.Public adalah variabel/method dapat diakses oleh semua kelas.

QUEUE(ANTRIAN)

Struktur Data Antrean (Queue) adalah suatu bentuk khusus dari List Linier dengan operasi penyisipan (Insertion) hanya diperbolehkan pada salah satu sisi, yang disebut sisi Belakang (Rear) dan operasi penghapusan (Deletion) hanya diperbolehkan pada sisi lainnya yang disebut sisi Depan (Front) dari List..Prinsip Antrean : FIFO (First In First Out). Ada 4 operasi dasar yang dapat dilakukan pada Struktur Data Antrean, yaitu :

1. CREATE(Antrean)

2. ISEMPTY(Antrean)

3. INSERT(Elemen,Antrean)

4. REMOVE(Antrean)

Contoh Linked List

#include<constream.h>
#include<stdio.h>
#include<stdlib.h>
#includ<ctype.h>
#include<string.h>

struct siswa
{
 char nrp[8],nama[30];
};

struct simpul
{
 char nrp[8],nama[30];
 struct simpul *berikut;
};

struct simpul *awal=NULL,*akhir=NULL;
struct siswa mhs;

void tambah_list_belakang(struct siswa info);
void hapus_simpul(int info);
void hapus_data();
void isi_list();
void sisip_list(struct simpul *first,struct siswa info,char posisi[20]);
void sisip_isi_list();
void tampil_list();
void tampil_list2();
void hapus_semua();
void menu();

void main()
{
 clrscr();
 menu();
 getch();
}

void menu()
{
 int pil;
 clrscr();
 cout<<"\nProgrammer         : 1 TI 7";
 cout<<"\n\nPilih Transaksi  : ";
 cout<<"\n\t\t1. Isi List";
 cout<<"\n\t\t2. Sisip List";
 cout<<"\n\t\t3. Tampil List";
 cout<<"\n\t\t4. Hapus data";
 cout<<"\n\t\t5. hapus semua";
 cout<<"\n\t\t6. Keluar";
 cout<<"\n\nTentukan Pilihan : ";
 cin>>pil;

 switch(pil)
 {
  case 1 : isi_list();
           break;
  case 2 : clrscr();
           sisip_isi_list();
           break;
  case 3 : tampil_list();
           break;
  case 4 : hapus_data();
           break;
  case 5 : hapus_semua();
           break;
 case 6 : clrscr();
               cout<<"\nTerima Kasih";
               getch();
 }
}

void tambah_list_dibelakang(struct siswa info)
{
 struct simpul *baru;

 baru=new simpul;
 strcpy(baru->nrp,info.nrp);
 strcpy(baru->nama,info.nama);

 if (awal==NULL)
  {
   awal=baru;
  }
 else
  {
   akhir->berikut=baru;
  }
 akhir=baru;

 akhir ->berikut=NULL;
}

void isi_list()
{
 char jawab;
 do
 {
  clrscr();
  cout<<"\nNRP  : ";gets(mhs.nrp);
  cout<<"\nNama : ";gets(mhs.nama);

  tambah_list_dibelakang(mhs);
  cout<<"\n\nTambah data Y/T : ";
  cin>>jawab;
  }while(toupper(jawab)!='T');
  menu();
 }

 void hapus_simpul(char info[20])
{
 struct simpul *bantu,*hapus;

 if (awal==NULL) { cout<<"\n Data List Kosong ";}
 else
 {
   if (strcmp(awal->nrp,info)==0)
    {
     hapus=awal;
     awal=hapus->berikut;
     free(hapus);
    }
    else
    {
     bantu=awal;
     while ((strcmp(info,bantu->berikut->nrp)!=0) && (bantu->berikut!=NULL))
      {
       bantu=bantu->berikut;
      }
     hapus=bantu->berikut;
     if (hapus!=NULL)
      {
      if (hapus!=akhir) { bantu->berikut=hapus->berikut;}
      else
        {
         akhir=bantu;
         akhir->berikut=NULL;
        }
      free(hapus);
      }
    }
  }
}

void hapus_data()
{
 char cari[20];
 char jawab;

 clrscr();

 cout<<"\nada data yang akan dihapus Y/T : ";cin>>jawab;
 if (toupper(jawab)=='Y')
   {
    aku:
    cout<<"\nNRP yang akan dihapus : ";
    gets(cari);
    hapus_simpul(cari);
    cout<<"\nData menjadi : ";
    tampil_list();
    }
}

void tampil_list()
{
 struct simpul *baca;
 int i;

 baca=awal;
 i=1;
 clrscr();
 while(baca!=NULL)
 {
  cout<<"\nData Ke-:"<<i<<endl;
  cout<<"\nNRP  : "<<baca->nrp;
  cout<<"\nNama : "<<baca->nama;
  cout<<endl;
  i++;
  baca=baca->berikut;
 }
 getch();
 menu();
}

void hapus_semua()
{
 struct simpul *hapus;

 hapus=awal;
 while(hapus!=NULL)
 {
 awal=hapus->berikut;
 free(hapus);
 hapus=awal;
 }
 clrscr();
 cout<<"Semua Data Telah Terhapus !!!";
 getch();
 menu();
}

void sisip_list(struct simpul *first,struct siswa info,char posisi[20])
{
 struct simpul *bantu, *baru;

 baru= new simpul;
 strcpy(baru->nrp,info.nrp);
 strcpy(baru->nama,info.nama);

 bantu=first;

 do
 {
  if (strcmp(posisi,bantu->nrp)!=0)  {bantu=bantu->berikut;};
  }while(bantu!=NULL && strcmp(posisi,bantu->nrp)!=0);

  baru->berikut=bantu->berikut;
  bantu->berikut=baru;
}

void sisip_isi_list()
{
 char cari[20];
 struct siswa ganti;

 clrscr();
 cout<<"\nNRP  : ";gets(ganti.nrp);
 cout<<"\nNama : ";gets(ganti.nama);

 cout<<"\nDisisipkan Setelah NRP : ";gets(cari);
  sisip_list(awal,ganti,cari);
  getch();
 menu();
}




Ouput Tampilan Pertama (Menu)