LINKED LIST TUJUAN UMUM Memahami konsep linked list TUJUAN KHUSUS z
z
Mempelajari prasarat linked list, pointer, sruct to pointer Linked list Insert, delete
LINKED LIST Variabel bertipe data pointer adalah variabel yang isinya alamat (address) dari variabel lainnya. Contoh: int a, b; /* a dan b adalah variabel integer*/ int *pa, *pb; /* pa dan pb adalah variabel pointer*/ Saat ini isi dari pa dan pb belum ditentukan, dengan assigment berikut: pa = &a; pb = &b; Maka pa berisi alamat a dan pb berisi alamat b. Bial alamat a = 400 dan b = 402, maka pa berisi 400 dan pb berisi 402 400
a
400
pa
402
b
402
pb
Variabel a dan b dapa diisi secara tidak langsung (onderct assigment) memalui pa dan pb yaitu dengan : *pa = 30; *pb = 20 400
30
a
400
pa
402
20
b
402
pb
Lebih Jauh tentang Pointer Reference operator (&) int A; P = &A; P merupakan alamat dari variabel A. andy = 25; fred = andy ted = &andy;
Pertama kita memberikan nilai 25 pada variabel andy, dimana setiap variabel yang dideklarasikan selalu mempunyai alamat di memori dalam hal ini dimisalkan 1776. Kedua mengkopi isi dari variabel andy ke fred. Ketiga mengkopi ke ted reference atau alamat dari variabel andy.
Dereference operator (*) Pointer dapat digunakan untuk mengisi nilai dari variabel yang ditunjuk.
*ted = 75 & is the reference operator and can be read as "address of" * is the dereference operator and can be read as "value pointed by"
Variabel pointer dapat dibuat atau diciptakan secara dinamis, yaitu mengalokasikan suatu tempat di memori ketika program sedang berjalan . Dengan kemampuan seperti ini maka penggunaan variabel pointer tidak hanya sekedar indirect assigment seperti contoh di atas, melainkan dapat membuat suatu struktur data di mana banyak atau kurang sesuai dengan kebutukan. Struktur tersebut di antaranya adalah Linked List.
Struktur Linked List Setiap elemen terdiri dari data dan pointer, bagian data akan berisi informasi, bagian pointer akan berisi alamat yang akan mengaitkan satu elemen dengan elemen lainnya. DATA
POINTER
Elemen
Oleh karena itu diperlukan deklarasi untuk pointer: Head, Current dan Tail. Struct node *Head, * Tail, * Current; -
Pointer Head selalu menunjuk ke node awal Pointer Tail selalu menunjuk ke node akhir Pointer Current dapat bergerak dari node awal hingga node akhir
Pointer Current bergerak sesuai dengan arah anak panah. Node yang sedang ditunjuk oleh current disebut node aktif. Linked list dapat dibangun dengan cara: 1. Insert depan, node baru selalu berada di depan 2. Insert belakang, node baru selalu berada di belakang 3. Insert setelah posissi current pointer
// my first pointer #include
using namespace std; int main () { int firstvalue, secondvalue; int * mypointer; mypointer = &firstvalue; *mypointer = 10; mypointer = &secondvalue; *mypointer = 20; cout<<"firstvalue is "<
} // more pointers #include using namespace std; int main () { int firstvalue = 5, secondvalue = 15; int *p1, *p2; p1=&firstvalue; p2=&secondvalue; *p1= 10; *p2= *p1; p1 = p2; *p1 = 20; cout<<"firstvalue is"<
return 0; }
// more pointers #include using namespace std; int main () { int numbers[5]; int * p; p = numbers; *p = 10; p++; *p = 20; p = &numbers[2]; *p = 30; p = numbers + 3; *p = 40; p = numbers; *(p+4) = 50; for (int n=0; n<5; n++) cout << numbers[n] << ", "; return 0; } // pointer to functions #include using namespace std; int addition (int a, int b) { return (a+b); } int subtraction (int a, int b) { return (a-b); } int (*minus)(int,int) = subtraction; int operation (int x, int y, int (*functocall)(int,int)) { int g; g = (*functocall)(x,y); return (g);} int main () { int m,n; m = operation (7, 5, addition); n = operation (20, m, minus); cout <
INSERT DEPAN struct node{ char data; struct node *next; }; struct node *head, *current, *tail; void create( ) { head = current = NULL; } void insert_depan(char data) { Struct node *p;/*temporary node*/ p=(struct node*)malloc(sizeof(struct node)); p->data = data; p->next = head; head = current = p; } void main( ) { char c; create( ); do { cout <<“Input Data (A..Z):”; cin >> c; insert_depan(c); } while(c !=“.”); )
Proses Insert Depan Create( ); HEAD CURR
. NULL
. NULL
Insert(‘A’); p =(stuct node*)malloc(sizeof(struct node));
p->data=data p->data=data; p->next=head; head= current=p;
P
.
P
.
A
.
P
.
A
.
.
NULL
HEAD CURR
P
.
.
.
A
.
NULL
Insert(‘B’); p =(stuct node*)malloc(sizeof(struct node)); P
p->data=data
P
. .
. B
.
HEAD CURR
. p->next=head;
P
.
B
.
.
A
.
A
.
NULL
head = current = p HEAD CURR
P
.
.
.
B
.
NULL
INSERT BELAKANG struct node{ char data; struct node *next; }; struct node *head, *current, *tail; void create( ) { head = current = tail = NULL; } void insert_belakang(char data) { Struct node *p;/*temporary node*/ p=(struct node*)malloc(sizeof(struct node)); p->data = data; p->next = NULL; if (head == NULL) head = current= tail = p; else {tail->next = p; tail = p;}; } head = current = p; } void main( ) { char c; create( ); do { cout <<“Input Data (A..Z):”; cin >> c; insert_belakang(c); } while(c !=“.”);
}
Proses Insert Belakang Insert(‘A’); p =(stuct node*)malloc(sizeof(struct node));
p->data=data p->data=data; p->next=NULL;
P
.
P
.
A
.
P
.
A
.
.
NULL
if (head == NULL) head = current = tail = p; else {tail->next = p};tail = p;}; HEAD CURR
P
.
.
.
A
.
NULL
. Tail
Insert(‘B’); p =(stuct node*)malloc(sizeof(struct node));
p->data=data p->data=data; p->next=NULL;
P
.
P
.
B
.
P
.
B
.
.
NULL
if (head == NULL) head = current = tail = p; else {tail->next = p};tail = p;}; HEAD CURR
P
.
.
.
A
.
B
.
Tail
HEAD CURR
.
NULL
P
.
.
.
A
.
B .
. Tail
NULL
Operasi pada Linked List 1. Create( ) Menciptakakn linked list baru dalam keadaan kosong 2. Insert(elemen_type e) Menambahkan satu elemen ke dalama linked list di bagian depan *). 3. Empty( ) Memeriksa apakah linked list dalam keadaan kosong. 4. Retrieve(elemen_type *e) Membaca informasi dari node yang sedang ditunjuk oleh current pointer ke variabel e. 5. Update(elemen_type e) Mengubah informasi dari node yang sedang ditunjuk oleh currentpointer dengan data dari variabel e. 6. Find_First( ) Memindahkan current pointer node awal. 7. Find Next(fail) Memindahkan current pointer node berikutnya, bila node berikutnya adalah node terakhi, maka operasi ini tidak berfungsi. 8. Delete( ) Menghapus node yang ditunjuk oleh current pointer, kemudian current pointer direset ke posisi awal. 9. Clear( ) Menghapus seluruh node.
Implementasi operasi Delete void delete() { struct node *p; if (current == head) head =head ->next; else { p=head; while (p->next !=current) p=p->next; p=->current->next; }; Free(current); Current = head; }
PROSES DELETE 1.
Posisi Current = Head
HEAD CURR
.
.
A
.
Tail
. B
C
.
D
.
E
.
NULL
.
head = head->next; CURR
HEAD
.
.
A
.
.
B
.
C
D
.
.
E
Tail
.
NULL
free(current); CURR
HEAD
.
. .
.
B
.
C
D
.
.
E
current = head; HEAD CURR
.
.
B
.
. C
.
D
.
E
Tail
.
NULL
Tail
.
NULL
2. Posisi Current ≠ Head HEAD
CURR
.
.
A
B
.
C
.
D
.
Tail
. E
.
NULL
.
p =head; while (p->next != current) p = p->next; HEAD
P
P
P
CURR
.
.
.
.
.
A
.
B
C
.
.
Tail
.
D
.
E
.
.
Tail
NULL
p ->next = current->next; HEAD
P
CURR
.
.
.
A
B
.
C
.
D
.
E
.
NULL
.
free(current); HEAD
. A
.
B
.
P
CURR
.
.
C
.
. .
E
Tail
.
NULL
current = head; HEAD CURR
.
.
A
.
. B
.
C
.
E
Tail
.
NULL
Latihan: 1. Buat modul untuk melakukan operasi: Insert (after current), Find_First, Find_Next, Update, Retrieve, Delete, Empty, dan Clear.
Empty void empty() { if (head = NULL) ;return 0; return (1);} Find First Void findfirst() { current = head;} Find Next void findnext() { if (current->next !=NULL) current = current->next; } Retrieve void retrieve(e) { e = current->isi;} Update void update(e) { current->isi = e;} Delete Current void delete() int *x; { if (current != head) {x = head; while (x->next != current) {x= x->next; x->next =curent->next;} else head = head->next; free(current); current = head; }
Clear void clear(); { while (head !=NULL) {current = head; head = head ->next; free(current);}}
Double Linked List Struktur double linked list mempunyai bentuk umum: .
Next
Head
.
Current
.
Tail
.
.
.
.
.
.
NULL
.
.
.
.
.
.
Prev
Data NULL
Deklarasi untuk Node: struct node { int data; struct node *next; struct node *prev; }; Double linked list dapat dibangun dengan 2 cara: 1. Insert Before; node baru berada sebelum posisi current pointer 2. Insert After; node baru berada setelah posisi current pointer.
Implementasi Circular Double Linked list struct node { int data; struct node *next; struct node *prev; }; struct node *head, *current; int n; /*jumlah node*/ void create( ) {head = current = NULL; n=0;} void insert_after(int data) { struct node *p; /*temporary node*/ p =(struct node*)malloc(sizeof(struct node)); p->data=data; if(head==NULL) {head = p; p->next = p; p->prev=p;} else {current->next->prev = p; p->next =current->next; p->prev=current; current->next=p;} current=p; n++; }
void insert_before(int data) { if head == NULL) current =current->prev; insert_after(data); if (current->next == head) head = current; } void delete( ) {struct node *p; p=current; current->prev->next=current->next; current->next->prev=current->prev; current=current->next; if (n==1) head= NULL; elseif (head=p) head=current; n--;free(p);} void find_next( ); { current=current->next; } void find_prev( ) { current=current->prev; }
