linked list.doc
TRANSCRIPT
LINKED LIST
DEFINISI.Linked list (one way list) adalah suatu kumpulan elemen data (yang disebut sebagai node) dimana urutannya ditentukan oleh suatu pointer.
Setiap elemen (node) dari suatu linked list terdiri atas dua bagian, yaitu :
- INFO, berisi informasi tentang elemen data yang bersangkutan.
- NEXT(link field/next pointer field), berisi alamat dari elemen (node) selanjutnya
yang dituju.
Berikut ini sebuah contoh linked list yang terdiri atas 4 node :
Pada node ke-4 field NEXT-nya berisi NULL, artinya node ke-4 tsb. adalah node terakhir.
Node-node dalam linked list tidak harus selalu digambarkan paralel seperti pada gambar diatas. Linked list pada contoh diatas dapat pula digambarkan seperti berikut ini :
CATATAN :
- Ada dua hal yang menjadi kerugian dengan representasi suatu data dengan linked list ini,
yaitu :
1. Diperlukan ruang tambahan untuk menyatakan/tempat field pointer.
2. Diperlukan waktu yang lebih banyak untuk mencari suatu node dalam linked list.
- Sedangkan keuntungannya adalah :
1. Jenis data yang berbeda dapat di-link.
2. Operasi REMOVE atau INSERT hanya dilakukan dengan mengubah pointer-nya saja.
OPERASI DASAR PADA LINKED LIST.Ada beberapa aturan yang didefinisikan pada operasi didalam linked list, yaitu :
-Jika P adalah suatu variabel pointer, maka nilainya adalah alamat atau lokasi dari variabel lain yang dituju.
-Operasi yang didefinisikan pada suatu variabel pointer adalah :
1. Test apakah sama dengan NULL.
2. Test untuk kesamaan dengan variabel pointer lain.
3. Menetapkan sama dengan NULL.
4. Menetapkan menuju ke node lain.
Notasi yang didefinisikan sehubungan dengan operasi diatas adalah :
1. NODE(P), artinya node yang ditunjuk oleh pointer P.
2. INFO(P), artinya nilai INFO dari node yang ditunjuk pointer P.
3. NEXT(P), artinya hubungan (link) selanjutnya dari node yang ditunjuk oleh
pointer P.
Sebagai contoh, perhatikan linked list dibawah ini :
NODE(P) = node yang ditunjuk oleh P yaitu node pertama.
INFO(P) = A
NEXT(P) = node ke-dua
INFO(NEXT(NEXT(P))) = C
MENGHAPUS SUATU NODE DARI LINKED LIST (REMOVE).
Untuk menghapus node dalam linked list digunakan procedure FREENODE.
Jika Q adalah suatu variabel pointer, maka FREENODE(Q) akan menyebabkan node yang ditunjuk oleh variabel pointer Q dihapus dari linked list.
Perhatikan linked list berikut :
langkah ke-1 :
Q := Next(P)
langkah ke-2 :
Next(P) := Next(Q)
langkah ke-3 :
Freenode(Q)
procedure Freenode(Q)
(a)Next(Q) := Avail
(b)Info(Q) := Null
(c)Avail := Q
MENYISIPKAN SUATU NODE KE DALAM LINKED LIST
Untuk menyisipkan node dalam linked list digunakan procedure GETNODE.
Jika NEW adalah suatu variabel pointer, maka GETNODE(NEW) akan menyebabkan node yang ditunjuk oleh variabel pointer NEW disisipkan ke dalam linked list.
procedure Getnode(NEW)
if Avail = Null
then out-of-free-space
(a)elsebegin
Getnode := Avail;
(b)
Avail := Next(Avail);
(c)
Next(Getnode) : = Null;
end;
Algoritma menyisipkan sebuah Node :
(a)Getnode(NEW);
(b)Info(NEW) := Name;
(c)Q := Next(P)
(d)Next(P) := NEW
(e)Next(NEW) := Q
Logika Linked List pada Array
(a)Jika tidak menggunakan logika linked list
(pada umumnya dalam meng-input data digunalan cara sequential)
AwalInsert EDelete CInsert F
1A1A1A1A
2C2C22
33E3E3E
4444F
Insert G
Delete E(overflow)
1A1A
22
33
4F4F
(b)Jika menggunakan logika Linked List
Keadaan awal
Insert E
Delete C
InfoNextInfoNextInfoNext
1A21A21A3
2C02C324
343E03E0
404040
Insert F
Delete E
Insert GInfoNextInfoNextInfoNext
1A31A21A2
2F02F02F3
3E2343G0
40404
Mendefinisikan Linked List dalam Pascal
Typenodeptr = ^ nodetype;
nametype = packed array [1..10] of char;
nodetype = record
info : nametype;
next : nodeptr;
end;
Varp : nodeptr;
node : nodetype;
* Catatan :
P ^. Info: Info dari node yang ditunjuk oleh pointer P
P^. Next: Next dari node yang ditunjuk oleh pointer P
P := nil
: pointer P berisi nilai Null
New(P)
: fungsi Getnode dalam Pascal
dispose(P): procedure Freenode dalam Pascal
Menghapus sebuah Node dalam Pascal
procedure removaf(p:nodeptr, var out:nametype);
varq : nodeptr;
begin
if (p^.Next = nil)
thenUNDERFLOW-CONDITION
elsebegin
q := p^.Next;
p^.Next := q^.Next;
out := q^.Info;
dispose(q);
end;
end;
Menyisipkan sebuah Node dalam Pascal
procedure inseraf(p:nodeptr, in:nametype);
var q : nodeptr;
begin
New(q);
q^.Info := in;
q^.Next := p^.Next;
p^.Next := q;
end;
Penyisipan pada akhir dari suatu Linked List (Linked List Antrean) dalam Pascal
Procedure Inserend(first : nodeptr, in :nametype);
Varnewnode, q : nodeptr;
Begin
New(newnode);
newnode^.Info := in;
newnode^.Next := nil;
q := first;
do while (q^.next nil)
q := q^.Next;
q^.Next := newnode;
End;
Jika sebuah Linked List digunakan untuk menggambarkan suatu antrean, dalam hal ini pointer dapat langsung menunjuk ke rear/akhir dari antrean untuk menghindari pengulangan melalui semua node untuk menemukan node terakhir.
procedure inserend(in : nametype, var rear : nodeptr);
varnewnode : nodeptr;
begin
New(newnode);
newnode^.Info := in;
newnode^.Next := nil;
rear^.Next := newnode;
rear := newnode;
end;
Circular Linked List
Head Nodes
Circular Linked List dengan Head Node
Circular Linked List dengan Head Node kosong
Algoritma penyisipan node yang berisi variabel Name pada head dalam Linked List
(a)Ambil node baru pada free storage kemudian node tersebut ditunjuk oleh pointer NEW
(b)Isikan Info dengan Name pada node baru tsb.
(c)Next dari node baru tsb. menunjuk ke node yang ditunjuk oleh pointer Head
(d)Pindahkan pointer Head menunjuk ke node yang baru.
Menghapus Node KhususProcedure removp(head : nodeptr, var p:nodeptr, out : nametype);
Varprior, this : nodeptr;
flag : 0..2;
Begin
prior := head;
this := head^.next;
flag := 1;
While flag = 1
do begin
if (this = head)
then flag := 2;
if (this = p)
then flag := 0
else begin
prior := this;
this := this^.next;
end;
end;
if (flag > 0)
then Node yang ditunjuk oleh pointer p tidak ada dalam List
else begin
prior^.next := p^.next;
out := p^.info;
dispose(p)
end;
End;
Doubly Linked List
Tiap node memiliki pointer yang menunjuk ke node sesudahnya dan pointer yang menunjuk
ke node sebelumnya.
Node Sesudahnya : Next(Node)
Node sebelumnya : Prior(Node)
Next(Prior(P)) = P dan P = Prior(next(P))
Double Linked List Kosong :
prior head next
Prior(Head) = Head
Next(Head) = Head
Dalam Pascal :
Type nodeptr = ^ nodetype
nodetype = record
prior : nodeptr;
info : nametype;
next : nodeptr
end;
Procedure menghapus sebuah node pada Double Linked List(a)Set pointer P
(b)Ubah pointer pada node Next predecessor P ke node Successor P
(c)Ubah pointer pada node dari prior Successor P ke node Predeccssor P
(d)bebaskan node yang ditunjuk pointer P
Dalam Pascal :
Procedure Removp(var p:nodeptr, out : nametype);
Varpred, succ : nodeptr;
Begin
pred := p^.prior;
succ := p^.next;
pred^.next := succ;
succ^.prior := pred;
out := p^.info;
dispose(p)
End;Penyisipan sebuah Node pada Doubly Linked List(a)Ambil sebuah node baru dan isikan datanya
(b)Set pointer dari Next node baru menunjuk ke Successor P dan pointer Proirnya ke P
(c)Ubah pointer Next P menunjuk ke node baru
(d)Ubah pointer Prior dari Successor P menunjuk ke node baru
Contoh Aplikasi Linked ListPolynomial
anxn + an-1 xn-1 + ... + a2 x2 + a1 x + a0Typenodeptr = ^nodetype;
nodetype = record
exp : integer;
coef : integer;
next : nodeptr;
end;
143 x4 + 201 x2 + 14 x + 2
a4 = 143a3 = 0
a2 = 201a1 = 14
a0 = 2
TREE
Merupakan salah satu bentuk struktur data tidak linearyang 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.
Beberapa jenis Tree yang memiliki sifat khusus :
1)Binary TreeBinary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.
Jenis-jenis Binary Tree :
a)Full Binary Tree
Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.
b)Complete Binary Tree
Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
c)Skewed Binary Tree
akni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.
Implementasi Binary TreeBinary Tree dapat diimplemntasikan dalam Pascal dengan menggunakan double Linked List. Untuk nodenya, bisa dideklarasikan sbb :
Type Tree= ^node;
Node=recordIsi: TipeData;
Left,Right : Tree;
end;
Contoh ilustrasi Tree yang disusun dengan double linked list :
(Ket: LC=Left Child; RC=Right Child)Operasi-operasi pada Binary Tree :
vCreate: Membentuk binary tree baru yang masih kosong.
vClear: Mengosongkan binary tree yang sudah ada.
vEmpty: Function untuk memeriksa apakah binary tree masih kosong.
vInsert: Memasukkan sebuah node ke dalam tree.Adatiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.
vFind: Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)
vUpdate: Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)
vRetrieve: Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)
vDeleteSub: Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.
vCharacteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2++jmlNodeLvln*n]/Size)
vTraverse: Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree.Adatiga cara traverse : Pre Order, In Order, dan Post Order.
Langkah-Langkahnya Traverse :
PreOrder: Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.
InOrder: Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.
PostOrder: Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi.
Untuk lebih jelasnya perhatikan contoh operasi-operasi pada Binary Tree berikut ini :
2)Binary search TreeAdalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya. Binary seach tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree. Contoh binary search tree umum :
Pada dasarnya operasi dalam binary search tree sama dengan Binary tree biasa, kecuali pada operasi insert, update, dan delete.1.Insert: Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat. (Lokasi tidak ditentukan oleh user sendiri).
2.Update: Seperti pada Binary Tree biasa, namun disini uapte akan berpengaruh pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada tree dengan melakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.3.Delete: Seperti halnya update, delete dalamBinary Search Tree juga turut mempengaruhi struktur dari tree tersebut.
(Keadaan awal merupakan lanjutan gambar sebelumnya)
Pada operasi di samping, delete dilakukan terhadap Node dengan 2 child. Maka untuk menggantikannya, diambil node paling kiri dari Right SubTree yaitu 13.