Kamis, 03 Maret 2011

LINKED LIST

Konsep dasar struktur data dinamis adalah alokasi memori yang dilakukan
secara dinamis. Pada konsep ini, terdapat suatu struktur yang disebut dengan
struktur referensi diri (self-referential structure), mempunyai anggota pointer
yang menunjuk ke struktur yang sama dengan dirinya sendiri.
Struktur data dinamis sederhana dapat dibagi menjadi empat jenis, yaitu :
1. Linked list
2. Stack
3. Queue
4. Binary tree
Definisi ini dapat dituliskan secara sederhana dengan struktur :
struct node {
int info;
struct node *nextPtr;
}
Struktur ini mempunyai dua anggota, yaitu bilangan bulat info dan pointer
nextPtr. Variabel pointer nextPtr ini menunjuk ke struktur bertipe struct node,
yang sama dengan deklarasi induknya.
Untuk membuat dan menangani struktur data dinamis dibutuhkan alokasi
memori dinamis agar tersedia ruang bagi node-node yang ada. Fungsi malloc,
free, dan operator sizeof banyak digunakan dalam alokasi memori dinamis ini.
Contoh :
typedef struct node NODE;
typedef NODE *NODEPTR;
NODEPTR newPtr = malloc (sizeof (NODE));
newPtr -> info = 15;
newPtr -> nextPtr = NULL;
Fungsi free digunakan untuk menghapus memori yang telah digunakan untuk
node yang ditunjuk oleh pointer tertentu. Jadi free (newPtr); akan menghapus
memori tempat node yang ditunjuk oleh newPtr.
DEFINISI LINKED LIST
Linked list adalah suatu cara untuk menyimpan data dengan struktur sehingga
dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data
yang diperlukan. Program akan berisi suatu struct atau definisi kelas yang berisi
variabel yang memegang informasi yang ada didalamnya, dan mempunyai suatu
pointer yang menunjuk ke suatu struct sesuai dengan tipe datanya.
Struktur dinamis ini mempunyai beberapa keuntungan dibanding struktur array
yang bersifat statis. Struktur ini lebih dinamis, karena banyaknya elemen
dengan mudah ditambah atau dikurangi, berbeda dengan array yang ukurannya
bersifat tetap.
Manipulasi setiap elemen seperti menyisipkan, menghapus, maupun menambah
dapat dilakukan dengan lebih mudah.
Modul 6 Struktur Data (Arie) - 2
Contoh :
//Program:link1.cpp
#include
#include
#include
typedef struct nod {
int data;
struct nod *next;
} NOD, *NODPTR;
void CiptaSenarai(NODPTR *s)
{
*s = NULL;
}
NODPTR NodBaru(int m)
{
NODPTR n;
n = (NODPTR) malloc(sizeof(NOD));
if(n != NULL) {
n -> data = m;
n -> next = NULL;
}
return n;
}
void SisipSenarai (NODPTR *s, NODPTR t, NODPTR p)
{
if (p==NULL) {
t -> next = *s;
*s = t;
}
else {
t -> next = p -> next;
p ->next = t;
}
}
void CetakSenarai (NODPTR s)
{
NODPTR ps;
for (ps = s; ps != NULL; ps = ps -> next)
printf("%d -->", ps -> data);
printf("NULL\n");
}
int main ()
{
NODPTR pel;
NODPTR n;
CiptaSenarai(&pel);
n = NodBaru(55);
SisipSenarai(&pel, n, NULL);
Modul 6 Struktur Data (Arie) - 3
n= NodBaru(75);
SisipSenarai(&pel, n, NULL);
CetakSenarai(pel);
return 0;
}
Bila program dijalankan maka :
75->55->NULL
TEKNIK DALAM LINKED LIST
Pengulangan Linked List
Secara umum pengulangan ini dikenal sebagai while loop. Kepala pointer (head
pointer) dikopikan dalam variabel lokal current yang kemudian dilakukan
perulangan dalam linked list. Hasil akhir dalam linked list dengan
current!=NULL. Pointer lanjut dengan current=current->next.
Contoh :
// Return the number of nodes in a list (while-loop version)
int Length(struct node * head) {
int count = 0;
struct node* current = head;
while (current != NULL) {
count++;
current=current->next;
}
return (count);
}
Mengubah Pointer Dengan Referensi Pointer
Banyak fungsi pada linked list perlu untuk merubah pointer kepala. Pointer ke
pointer disebut dengan “reference pointer”.
Langkah utamanya dalam teknik ini adalah :
• Merancang fungsi untuk mengambil pointer ke pointer kepala. Untuk
melewati pointer ke “value of interest” yang dibutuhkan untuk diubah.
Untuk mengubah struct node*, lewati struct node**.
• Gunakan ‘&’ dalam panggilan untuk menghitung dan melewati pointer ke
value of interest.
• Gunakan ‘*’ pada parameter dalam fungsi pemanggil untuk mengakses
dan mengubah value of interest.
Contoh :
void ChangeToNull (struct node** headRef)
*headRef=NULL;
void ChangeCaller() {
struct node* head1;
struct node* head2;
ChangeToNull (&head1);
ChangeToNull (&head2);
}
Modul 6 Struktur Data (Arie) - 4
Fungsi sederhana tersebut akan membuat pointer kepala ke NULL dengan
menggunakan parameter reference. Gambar berikut menunjukkan bagaimana
pointer headRef dalam ChangeToNull menunjuk ke head1 pada Change Caller.
ChangeCaller()
head1
ChangeToNull(&head1)
headRef
Pointer headRef dalam ChangeToNull menunjuk ke head1
Membuat Kepala Senarai Dengan Perintah Push()
Cara termudah untuk membuat sebuah senarai dengan menambah node pada
“akhir kepala” adalah dengan push().
Contoh :
struct node* AddAtHead() {
struct node* head = NULL;
int i;
for ( i=1; i<6; i++) {
push (&head, i);
}
// head == { 5, 4, 3, 2, 1 };
return (head);
}
Dalam membuat tambahan node pada akhir senarai (list) dengan menggunakan
perintah Push(), jika terjadi kesalahan maka urutan akan terbalik.
Membuat Ekor Pada Akhir Senarai
Menambah ekor pada senarai akan melibatkan penempatan node terakhir, dan
kemudian merubahnya .next field dari NULL untuk menunjuk node baru seperti
variabel tail dalam contoh yaitu menambah node 3 ke akhir daftar {1,2}
Stack Heap
head
tail
newNode
Membuat ekor pada akhir senarai
Untuk memasukkan atau menghapus node di dalam senarai, pointer akan
dibutuhkan ke node sebelum posisi, sehingga akan dapat mengubah .next field.
Agar dapat menambahkan node di akhir ekor pada data senarai {1, 2, 3, 4, 5},
dengan kesulitan node pertama pasti akan ditambah pada pointer kepala,
tetapi semua node yang lain dimasukkan sesudah node terakhir dengan
1 2
3
Modul 6 Struktur Data (Arie) - 5
menggunakan pointer ekor. Untuk menghubungkan dua hal tersebut adalah
dengan menggunakan dua fungsi yang berbeda pada setiap permasalahan.
Fungsi pertama adalah menambah node kepala, kemudian melakukan
perulangan yang terpisah yang menggunakan pointer ekor untuk menambah
semua node yang lain. Pointer ekor akan digunakan untuk menunjuk pada node
terakhir, dan masing-masing node baru ditambah dengan tail->next.
Contoh:
struct node* BuildWithSpecialCase () {
struct node* head = NULL;
struct node* tail;
int i;
push (&head, 1);
tail = head;
for (i=2; i<6; i++) {
push (&(tail->next), i);
tail = tail->next;
}
return (head);
}
Membuat Referansi Lokal
Dengan menggunakan “reference pointer” lokal, pointer akan selalu menunjuk
ke pointer terakhir dalam senarai.
Semua tambahan pada senarai dibuat dengan reference pointer. Reference
pointer tidak menunjuk ke pointer kepala, tetapi menunjuk ke .next field
didalam node terakhir dalam senarai.
Contoh :
struct node* BuildWithLocalRef() {
struct node* head = NULL;
struct node** lastPtrRef=&head;
int i;
for (i=2; i<6; i++) {
Push (lastPtrRef, i);
lastPtrRef=&((*lastPtrRef)->next);
}
return (head);
}
Cara kerja teknik ini adalah :
• Pada puncak putaran, lastPtrRef menunjuk pointer terakhir dalam
senarai. Pada permulaannya menunjuk ke pointer kepala itu sendiri.
Berikutnya menunjuk ke .next field di dalam node terakhir dalam
senarai.
• Push(lastPtrRef); menambah node baru pada pointer akhir. Node baru
menjadi node terakhir dalam senarai.
• lastPtrRef=&((*lastPtrRef)->next; lastPtrRef lanjut ke .next field dan
.next field sekarang menjadi pointer terakhir dalam senarai.
Modul 6 Struktur Data (Arie) - 6
Stack Heap
head
lastPtrRef
Membuat ekor pada akhir senarai
OPERASI DALAM LINKED LIST
Menambah Node Baru
Untuk menambahkan sebuah node di dalam senarai, perlu didefinisikan sebuah
kepala (head) dan ekor (tail). Pada awal senarai, posisi kepala dan ekor masih
menjadi satu. Setelah ada tambahan node yang baru, maka posisinya berubah.
Posisi kepala tetap pada awal senarai dan posisi ekor pada akhir senarai atau
node yang baru. Bila ada tambahan node, maka posisi ekor akan bergeser
sampai ke belakang dan akhir senarai ditunjukkan dengan NULL.
Contoh :
void SLList::AddANode()
{
Tail->Next = new List;
Tail=Tail->Next;
}
Penambahan Node
Sebelum Head
Tail
Langkah 1 Head New Node
Tail Next
Langkah 2 Head NULL
Tail
Menghapus Node
Contoh :
void SLList::DeleteANode(ListPtr corpse)
{
ListPtr temp;
if (corpse==Head) {
temp=Head;
Head=Head->Next;
delete temp;
}
1 2
Modul 6 Struktur Data (Arie) - 7
else if (corpse==Tail) {
temp=Tail;
Tail=Previous(Tail);
Tail->Next=NULL;
delete temp;
}
else {
temp=Previous(corpse);
temp->Next=corpse->Next;
delete corpse;
}
CurrentPtr=Head;
}
CONTOH LATIHAN :
Buatlah program untuk memasukkan beberapa data dalam sebuah senarai
(linked list), jika akan mengakhiri tekan n maka akan muncul semua node yang
masuk ke dalam linked list tersebut.
//Program:link2
#include
#include
#include
#include
typedef struct node {
int lkey;
char name[10];
struct node* next;
} TNODE;
TNODE *first, *last;
int LoadNode(TNODE *p);
void FreeNode(TNODE *p);
void PrintNode(TNODE *p);
void CreateList()
{
TNODE *p;
int n=sizeof(TNODE);
first=last=0;
for(;;)
{
if( (p=(TNODE*)malloc(n))==0 )
{
printf("\nmemori tidak cukup");
break;
}
if(LoadNode(p)!=1)
{
FreeNode(p);
break;
}
Modul 6 Struktur Data (Arie) - 8
p->next=0;
if (first==0)
first=last=p;
else {
last->next=p;
last=p;
}
}
}
int LoadNode(TNODE *p)
{
char opt;
printf("\nMasukkan node baru?");
opt=getche();
opt=toupper(opt);
if(opt!='N') {
puts("\nMasukkan data untuk node:");
printf("\nlkey:\t");
if (scanf("%d",&(p->lkey))!=1) return 0;
printf("\nname:\t");if (scanf("%s",p->name)!=1) return 0;
return 1;
}
else
return -1;
}
void FreeNode(TNODE *p) {
free(p);
}
void ViewAllList()
{
TNODE *p;
p=first;
while(p) {
PrintNode(p);
p=p->next;
}
}
TNODE* FindNode(int key)
{
TNODE *p;
p=first;
while(p) {
if(p->lkey == key) return p;
p=p->next;
}
return 0;
}
void PrintNode(TNODE *p)
{
if(p) printf("\n%d\t%s",p->lkey,p->name);
}
Modul 6 Struktur Data (Arie) - 9
TNODE* InsertBeforeFirst()
{
TNODE *p;
int n=sizeof(TNODE);
if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1))
{
if (first==0) {
p->next=0;
first=last=p;
}
else {
p->next=first;
first=p;
}
return p;
}
if(p==0)
printf("\nMemori tidak cukup");
else
FreeNode(p);
return 0;
}
TNODE* InsertBeforeKey(int key)
{
TNODE *p, *q, *q1;
int n=sizeof(TNODE);
q1=0;
q=first;
while(q) {
if(q->lkey == key) break;
q1=q;
q=q->next;
}
if(q==0) {
printf("\nTidak ada node yang mempunyai kunci atau senarai kosong");
return 0;
}
if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) {
if(q==first) {
p->next=first;
first=p;
}
else {
p->next=q;
q1->next=p;
}
return p;
}
if(p==0)
printf("\nMemori tidak cukup");
else
FreeNode(p);
return 0;
}
Modul 6 Struktur Data (Arie) - 10
TNODE* InsertAfterKey(int key)
{
TNODE *p, *q;
int n=sizeof(TNODE);
q=first;
while(q) {
if(q->lkey == key) break;
q=q->next;
}
if(q==0) {
printf("\nTidak ada node yang mempunyai kunci atau senarai kosong");
return 0;
}
if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1))
{
if(q==last) {
p->next=0;
last->next=p;
last=p;
}
else {
p->next=q->next;
q->next=p;
}
return p;
}
if(p==0)
printf("\nMemori tidak cukup");
else
FreeNode(p);
return 0;
}
TNODE* InsertAfterLast()
{
TNODE *p;
int n=sizeof(TNODE);
if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1))
{
p->next=0;
if (first==0)
first=last=p;
else {
last->next=p;
last=p;
}
return p;
}
if(p==0)
printf("\nMemori tidak cukup");
else
FreeNode(p);
return 0;
}
Modul 6 Struktur Data (Arie) - 11
void RemoveFirst()
{
TNODE *p;
if(first==0)
return;
if(first==last) {
FreeNode(first);
first=last=0;
return;
}
p=first;
first=first->next;
FreeNode(p);
}
void RemoveLast()
{
TNODE *p, *q;
if(first==0)
return;
if(first==last) {
FreeNode(first);
first=last=0;
return;
}
q=0;
p=first;
while(p!=last) {
q=p;
p=p->next;
}
p=last;
FreeNode(p);
q->next=0;
last=q;
}
void RemoveByKey(int key)
{
TNODE *p, *q;
if(first==0)
return;
q=0;
p=first;
while(p) {
if(p->lkey == key) break;
q=p;
p=p->next;
}
if(!p) {
printf("\nTidak ada node yang mempunyai kunci");
return;
}
Modul 6 Struktur Data (Arie) - 12
if(first==last) {
FreeNode(first);
first=last=0;
return;
}
if(p==first) {
first=first->next;
FreeNode(p);
return;
}
if(p==last) {
q->next=0;
last=q;
FreeNode(p);
return;
}
q->next=p->next;
FreeNode(p);
}
void DeleteList()
{
TNODE *p;
p=first;
while(p) {
first=first->next;
FreeNode(p);
p=first;
}
last=0;
}
void main()
{
CreateList();
ViewAllList();
InsertAfterLast();
ViewAllList();
RemoveFirst();
ViewAllList();
InsertAfterKey(1);
ViewAllList();
RemoveByKey(1);
ViewAllList();
DeleteList();
ViewAllList();
}

1 komentar: