TUGAS SENARAI BERANTAI
(LINKED LIST)
1.PENGERTIAN
Senarai berantai atau kadang-kadang disebut dengan senarai bertaut atau daftar bertaut dalam ilmu komputer merupakan sebuah struktur data yang digunakan untuk menyimpan sejumlah objek data biasanya secara terurut sehingga memungkinkan penambahan, pengurangan, dan pencarian atas elemen data yang tersimpan dalam senarai dilakukan secara lebih efektif. Pada praktiknya sebuah struktur data memiliki elemen yang digunakan untuk saling menyimpan rujukan antara satu dengan lainnya sehingga membentuk sebuah senarai abstrak, tiap-tiap elemen yang terdapat pada senarai abstrak ini seringkali disebut sebagai node. karena mekanisme rujukan yang saling terkait inilah disebut sebagai senarai berantai.
2.JENIS JENIS
>Senarai tunggal
Bila struktur data sebuah node hanya memiliki satu tautan atas node berikutnya dalam sebuah senarai, maka senarai tersebut dinamakan sebagai senarai tunggal.
>Senarai ganda
Berbeda halnya dengan senarai tunggal, pada senarai ganda, struktur data atas tiap-tiap node memiliki rujukan pada node sebelum dan berikutnya. Sebagian algoritme membutuhkan taut ganda, contohnya sorting dan reverse traversing.
>Senarai sirkuler
Pada dua jenis senarai sebelumnya, node terakhir dalam senarai tersebut merujuk pada null yang artinya akhir dari sebuah senarai, begitu pula null sebagai rujukan node sebelumnya pada node pertama bila senarai yang dimaksudkan adalah senarai ganda. Pada senarai sirkuler, informasi rujukan pada node terakhir akan merujuk pada node pertama, dan rujukan pada node pertama akan merujuk pada node terakhir bila yang digunakan sebagai dasar implementasi adalah senarai ganda.
3.JENIS OPERASI
3.Operasi-Operasi yang ada pada Linked List :
– InsertIstilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
– IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
– Find First
Fungsi ini mencari elemen pertama dari linked list
– Find NextFungsi ini mencari elemen sesudah elemen yang ditunjuk now
– Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
– Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.
– Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalahelemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
– Delete HeadFungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
– 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.
5. CONTOH PROGRAM
contoh program Double Linked List
struct node
typedef struct node node;
node *pHead = NULL;
node *alokasiNodeBaru()
#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)
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()
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)
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()
void hapusAwal()
{
node *pHapus;
pHapus=pHead;
pHead=pHead->next;
pHead->prev=NULL;
free(pHapus);
}
void hapusTengah()
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()
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;
}
