LINKED LIST
Dalam pemakaian sehari - hari istilah linked list (senarai berantai) adalah kumpulan linear sebuah data contoh senarai berantai adalah data yang berisi daftar belanjaan, yang berupa barang pertama, kedua,, ketiga dan seterusnya, untuk hari berikutnya maka daftar terdebut bisa berubah sesuai barang yang harus dibeli lagi atau barang yang tidak perlu dibeli lagi. Daftar belanjaan semula bisa ditambah 3 barang lain dan menghapus dua barang (dgn mencoret) yang tidak perlu dibeli lagi.
Setiap simpul dalam suatu linked list terbagi menjasi 2 bagian yaitu :
1. Medan Informasi
Berisi informasi yang akan disimpan dan diolah
2 Medan Penyambung
Berisi alamat berikutnya. Bernilai 0, jika link tersebut tidak menunjuk ke data (Simpul)
lainya. Penunjuk ini disebut penunjuk nol.
Linked list juga mengandung sebuah variabel penunjuk list, yamg biasanya diberi nama START (AWAL) yang berisi alamat dari simpul pertama dalam list.


BENTUK NODE SINGLE LINKLED LIST NON CIRCULAR

Single : field pointer-nya hanya satu arah, pada akhir not pointer-nya menunjuk NULL
Linked List : Node - node tersebut saling terhubung satu sama lain
setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. Mode terakhir akan menunjuk NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.


SINGLE LINKED LIST NON CIRCULAR MENGGUNAKAN HEAD


Dibutuhkan satu buah variabel pointer : head yang akan selaku menunjuk pada node pertama
Deklarasi Pointer Penunjuk Head Single Linked List sebagai berikut :

TNode*head

Menambah Node Di Depan
Penambahan node baru akan dikaitan di node paling depan, namun pada daat pertama kali (data masih kosong), maka penambahan data dilakukan dengan cara : node head ditunjukan ke node baru tersebut
Prinsipnya adalah mengkaitkan node baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap sekaku menjadi data terdepan.

Menambah Node Di Belakang
Penambahan dilakukan di belakang, namin pada saat pertama kali, node langsung ditunjuk oleh head, membutuhkan pointer bantu untuk mengetahui node terbelakang kemudian dikaitkan dengan node baru, perlu digunakan perulangan.

Menghapus Node Di Depan
Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penggunaan suatu pointer lain (hapus) yang digunakan untuk menunjuk node yang akan dihapus, barulah kemusian menghapus pointer menggunakan perintah delete. Sebelum data terdepan terhapus, terlebih dahulu head harus menunhuk ke alamat berikutnya agar list tidak putus, jika head masih NULL berarti data masih kosong.

Menghapus Node Di Belakang
Membutuhkan pointer bantu dan hapus. Pointer hapus digunakan untuk menunjuk node yang akan dihapus, Pointer bantu untuk menunjuk node sebelum node yang akan dihapus yang akan menjadi node yang terakhir. Pointer bantu digunakan untuk menunjuk ke nilai NULL selalu bergerak sampai sebelum node yang akan dihapus kemudian pointer hapus diletakan setelah pointer bantu. Selanjutnya pointer hapus akan menunjuk ke NULL.

SINGLE LINKED LIST NON CIRCULAR MENGGUNAKAN HEAS DAN TAIL

Dibutuhkan dua variabel pointer head dan tail. Head selalu menunjuk ke node pertama, sedangkan tail selalu menunjuk ke node terakhir
Kelebihan dari single liked list dengan heag dan tail adalah pada penambahan data di belakang, hanya dibutuhkan tail yang mengikat node baru saja tanpa harus menggunakan perulangan pointer bantu.

Menghapus Node Di Depan (Dengan Head dan Tail)
Penghapusan node tidak boleh dilakukan jika keadaan node sadang ditunjuk oleh pointer, maka harus dilakukan penunjukan terlebih dahulu dengan pointer hapus pada head, kemudian dilakukan pergeseran head ke node berikutnya sehingga data setelah head menjadi head baru, kemudian menghapus pointer hapus dengan menggunakan perintak delete. Jika tail masih NULL maka berarti list masih kosong.

Menghapus Node Di Belakang(Dengan Head Dan Tail)
Penghapusan tidak boleh dilakukan jika keasaan node dedang ditunjuk oleh pointer, maka harus dilakukan penunjukan terlebih dahulu dengan mengginakan variabel hapus pada tail. JIka Tail masih NULL maka berarti list masih kosong. Dibutuhkan pointer bantu untuk membantu pergeseran dari head ke node berikutnya dampai debelim tail, sehingga tail dapat ditunjukan ke bantu, dan bantu tersebut akan nenjadi tail yang baru. Setelah itu hapus pointer hapus dengan menggunakan menggunakn perintah delete.

Contoh program single linked list (Non circular)
A .Tambah list belakang
tambah list



#include <iostream.h>
#include <conio.h>


typedef struct TNode {
int data;
TNode *next;
};
TNode *head;
void init(){
head=NULL;
}
int IsEmpty(){
if(head==NULL)
return 1;
else
return 0;
}
void insertdepan(int n){
TNode *baru;
baru=new TNode;
baru->data=n;
baru->next=NULL;
if(IsEmpty()==1){
head=baru;
head->next=NULL;
}
else {
baru->next=head;
head=baru;
}
cout<<"Data Terisi";
}
void insertbelakang(int n){
TNode *baru,*bantu;
baru=new TNode;
baru->data=n;
baru->next=NULL;
if(IsEmpty()==1){
head=baru;
head->next=NULL;
}
else {
bantu=head;
while(bantu->next!=NULL){
bantu=bantu->next;
}
bantu->next=baru;
}
cout<<"Data Terisi";
}
void tampil(){
TNode *bantu;
bantu=head;
if(IsEmpty()==0){
while(bantu!=NULL){
cout<<bantu->data<<endl;
bantu=bantu->next;
}
}
else
cout<<"Masih Kosong"<<endl;
}
void hapusdepan(){
TNode *hapus;
int d;
if(IsEmpty()==0){
if(head!=NULL){
hapus=head;
d=hapus->data;
head=hapus->next;
delete hapus;
}
cout<<d<<" Terhapus"<<endl;
}
else
cout<<"Masih Kosong"<<endl;
}
main(){
int pil;
do{
clrscr();
int n;
cout<<"1.Insert Depan"<<endl;
cout<<"2.Insert Belakang"<<endl;
cout<<"3.Display"<<endl;
cout<<"4.Delete"<<endl;
cout<<"5.Exit"<<endl;
cout<<"Masukan Pilihan Anda :";pil=getch();


switch(pil){
case 1: clrscr();
cout<<"Masukan data :";cin>>n;
IsEmpty();
insertdepan(n);
break;
case 2: clrscr();
cout<<"Masukan data :";cin>>n;
IsEmpty();
insertbelakang(n);
break;
case 3: clrscr();
IsEmpty();
tampil();
break;
case 4: clrscr();
IsEmpty();
hapusdepan();
break;
}
getch();
}while(pil!=5);
return 0;
}


B. Hapus lingked list


#include"constream.h"
#include"stdio.h"
#include"stdlib.h"
#include"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         : Yuda ramdani";
 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();
}


Gambar display hapus list di jalankan.



Pilih no 1 untuk mengisi list.


Sesudah pilih no 1 lalu isi nrp dan nama.
sesudah beres tekan enter untuk melanjutkan program yang lainnya .
pilih no.2 untuk meng sisip_list.


dan masukan nrp dan nama untuk di sisipkan terlabih dahulu.
lalu teka enter untuk melakukan program selanjutnya.
pilih no.3 untuk menampilkan yang telah disisipkan tadi.


sesudah menekan  no.3 maka muncul seperti gambar diatas ini lalu enter untuk memulai selanjutnya pilih no.4 untuk menghapus data yang ingin dihapus misalnya
data ke 2 dengan nrp 6311255 nama ramdani


maka data dengan nrp 6311255 akan ter hapus . dan tekan enter
lalu pilih no.5 untuk meng hapus data semuanya.

Sesudah terhapus semuanya lalu tekan enter untuk keluardan pilih no.6 untuk clouse/keluar

5.TREE


Merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :
a) Prodecessor : node yang berada diatas node tertentu.
b) Successor : node yang berada di bawah node tertentu.
c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
e) Parent : predecssor satu level di atas suatu node.
f) Child : successor satu level di bawah suatu node.
g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.
h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
i) Size : banyaknya node dalam suatu tree.
j) Height : banyaknya tingkatan/level dalam suatu tree.
k) Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
l) Leaf : node-node dalam tree yang tak memiliki seccessor.
m) Degree : banyaknya child yang dimiliki suatu node.


CONTOH POHON BINARY

Dan ini contoh program dari c++

#include "iostream.h"
#include  "string.h"
#include "conio.h"


struct simpulpohon
{
  simpulpohon *induk;
  simpulpohon *kiri;
  simpulpohon *kanan;
  char data;
};

class pohonbiner
{
  private:
  simpulpohon *akar;

  int tambah(simpulpohon *orangtua, simpulpohon *baru);
  void tampil(simpulpohon *simpul);

  public:
  pohonbiner();
  int tambah(char data);
  void tampil();
};

void main()
{
  clrscr();
  char data[] = "yudaramdani";

  pohonbiner pohon;

  for (int i = 0; i < strlen(data); i++)
  pohon.tambah(data[i]);

  cout<<"Data ke Pohon Biner : "<<endl;
  for (int x = 0; x < strlen(data); x++)
   cout<<data[x];

  cout<<endl;
  cout<<endl;
  cout<<"Hasil Pohon Biner :"<<endl;
  pohon.tampil();
  getch();
}

pohonbiner::pohonbiner()
{
  akar = NULL;
}

int pohonbiner::tambah(char data)
{
  simpulpohon *simpul;

  simpul= new simpulpohon;

  simpul->kiri = NULL;
  simpul->kanan = NULL;
  simpul->induk = NULL;
  simpul->data = data;

  if (akar == NULL)
  {
    akar = simpul;
    return(1);
  }
  else
     return(tambah(akar,simpul));
}

int pohonbiner::tambah(simpulpohon *orangtua, simpulpohon *baru)
{
  if (baru->data ==orangtua->data)
   {
    delete baru;
    return(0);
   }

  else if (baru->data < orangtua->data)
   {
    if (!orangtua->kiri)
     {
      orangtua->kiri = baru;
      baru->induk = orangtua;
     }
    else
      return(tambah(orangtua->kiri,baru));
   }

  else
   {
     if (!orangtua->kanan)
     {
       orangtua->kanan = baru;
       baru->induk = orangtua;
     }
     else
       return(tambah(orangtua->kanan,baru));
    }
  return(1);
}


void pohonbiner::tampil()
{
  tampil(akar);
  cout<<endl;
}

void pohonbiner::tampil(simpulpohon *simpul)
{
  if (simpul)
  {
     if (simpul->kiri) tampil(simpul->kiri);

     cout<<simpul->data;

     if (simpul->kanan) tampil(simpul->kanan);
  }
}

Gambar display tree di jalankan


setelah dijalan kan maka akan muncul gambar seperti diatas dari 
data pohon binary :yudaramdani
maka hasil binarynya menjadi : adimnruy
karna klo huruf yang sama akan menjadi triss/destroit
dan hasil nya akan menjadi beurutan dan sesuai nama yang terkecil