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";
{
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
{
while(bantu!=NULL)
{
cout<<"nim : "<<bantu->nim;
cout<<" nama : "<<bantu->nama;
cout<<" umur : "<<bantu->umur<<endl;
bantu=bantu->next;
}
}
getch();
}
