LINKED LIST
Altien Jonathan Rindengan, S.Si, M.Kom
Pendahuluan
Dalam suatu linear list kita dapat melakukan operasi penyisipan atau penghapusan atas elemen-elemennya pada sembarang posisi. Misalkan ada 1500 item yang merupakan elemen dari suatu linear list. Jika elemen ke-56 akan kita keluarkan, maka elemen ke-1 s/d elemen ke-55 tidak akan berubah posisinya pada linear list tersebut. Tetapi elemen ke-57 akan menjadi elemen ke-56, elemen ke-58 akan menjadi elemen ke-57 dst. Selanjutnya, jika kita sisipkan satu elemen pada posisi setelah elemen ke-41, maka elemen ke-42 s/d elemen ke-1500 akan berubah posisinya.
Pendahuluan ….
Untuk menyatakan keadaan diatas diperlukan suatu konsep yang berbeda dengan konsep sekuensial sebelumnya. Linked list merupakan suatu cara non-sekuensial yang digunakan untuk merepresentasikan suatu data.
Pendahuluan ….
Apabila setiap kali anda ingin menambahkan data selalu dengan menggunakan variabel pointer yang baru, anda akan membutuhkan banyak sekali variabel pointer(penunjuk). Oleh karena itu ada baiknya jika anda hanya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan metode yang kita sebut Linked List. Jika diterjemahkan, maka berarti suatu daftar isi yang saling berhubungan.
Pendahuluan ….
Dalam pembuatan Single Linked List dapat menggunakan 2 Metode : LIFO
( Last In First Out ), aplikasinya : Stack (Tumpukan) FIFO ( First In First Out ), aplikasinya : Queue (Antrian)
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.
Definisi ….
Berikut ini sebuah contoh linked list yang terdiri atas 4 node : start
info
next
info
next
info
next
info
next null
node ke-1
node ke-2
node ke-3
node ke-4
Pada node ke-4 field NEXT-nya berisi NULL, artinya node ke-4 tsb. adalah node terakhir.
Definisi ….
Kerugian dengan representasi suatu data dengan linked list ini, yaitu : Diperlukan ruang tambahan untuk menyatakan/tempat field pointer. Diperlukan waktu yang lebih banyak untuk mencari suatu node dalam linked list.
Keuntungannya adalah : Jenis data yang berbeda dapat di-link. Operasi REMOVE/DELETE atau INSERT hanya dilakukan dengan mengubah pointer-nya saja.
Operasi Dasar 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 : Test apakah sama dengan NULL. Test untuk kesamaan dengan variabel pointer lain. Menetapkan sama dengan NULL. Menetapkan menuju ke node lain.
Operasi Dasar Linked List ….
Notasi yang didefinisikan sehubungan dengan operasi diatas adalah : NODE(P),
artinya node yang ditunjuk oleh pointer P. INFO(P), artinya nilai INFO dari node yang ditunjuk pointer P. NEXT(P), artinya hubungan (link) selanjutnya dari node yang ditunjuk oleh pointer P.
Operasi Dasar Linked List ….
info start
info
next
A
B node ke-2
node ke-1
P
next info
next
C node ke-3 info
next
D
null
node ke-4
NODE(P) = node yang ditunjuk oleh P yaitu node pertama. INFO(P) = A NEXT(P) = node ke-dua INFO(NEXT(NEXT(P))) = C
Insert (LIFO)
LIFO (last in first out) adalah suatu metode pembuatan Linked List dimana data yang masuk paling akhir adalah data yang keluar paling awal. Input data di awal list
Hal ini dapat dianalogikan dengan menumpukan barang pada kehidupan sehari‐hari.
Insert LIFO ….
Pembuatan simpul pada suatu linked list disebut dengan istilah INSERT. Jika linked list dibuat dengan Metode FIFO maka penambahan/insert simpul dilakukan di BELAKANG.
Insert LIFO ….
Procedure Insert Istilah
INSERT berarti menambahkan sebuah simpul baru ke dalam suatu linked list. Berikut adalah deklarasi tipe data dan variabel yang dapat digunakan sebagai deklarasi awal dan procedure InsertFirst.
Insert LIFO …. program linklist_insert; uses crt;
Type SLL=^data;
data=record info:integer;
next:SLL; end; list=SLL; node=SLL; var L:list; sum,ElmIn:Integer;
jawab:char;
Tipe data pointer-record
Insert LIFO ….
procedure CreateList (Var L:List); begin L:=nil; end;
Insert LIFO …. Procedure InsertFirst (Var L:List; elm:integer); var
P:Node;
begin New(P); P^.info:=Elm;
if L = nil then Begin
L:=P; P^.next:=Nil;
end else
begin P^.next:=L; L:=P; end; end;
Procedure Tampil (Var L:List); Var P:Node; Begin clrscr; if L<> Nil then begin
P:=L; write (P^.info);
write (' '); P:=P^.next;
while P<>nil do begin write (p^.info); write (' '); p:=P^.next; end; end;
writeln; end;
LIFO ….
Insert LIFO …. label ulang; begin
{PROGRAM UTAMA}
createlist(L); ulang:
clrscr; tampil(L);
writeln; write('Masukkan elemen linked list = ');
readln (ElmIn); InsertFirst(L,ElmIn); tampil(L); writeln; write('Apakah akan menginput ulang Y/N) ?');readln(jawab);
if (jawab='y') or (jawab='Y') then goto ulang; readln;
end.
Insert (FIFO)
FIFO adalah suatu metode pembuatan Linked List dimana data yang masuk paling awal adalah data yang keluar paling awal. Input data di akhir list
Insert LIFO ….
Procedure InsertFirst (Var L:List; elm:integer); var
P:Node;
begin New(P); P^.info:=Elm; if L = nil then Begin
L:=P; P^.next:=Nil;
end else
begin P^.next:=L; L:=P; end; end;
Procedure InsertLast (Var L:list;elm:integer); Var Pt,P : Node; begin new(P); P^.info:=elm; if L=Nil then
begin L:=P;
P^.next:=nil; end
else begin Pt:=L; while (Pt^.next<>Nil) do Pt:=Pt^.next; P^.next:=Nil; Pt^.next:=P; end;
end;
Insert LIFO ….
Insert FIFO ….
Remove/Delete procedure DeleteFirst(var L:List); var P : Node; begin if (L<>Nil) then begin if L^.next = nil then begin P:=L; dispose(P); L:=nil; end else begin P:=L; L:=L^.next; P^.next:=Nil; dispose(P); end; end; end;
procedure DeleteLast(var L:List); var Prec,Pt : Node; begin if (L<>Nil) then begin Pt:=L; Prec:=Nil; while (Pt^.next<>Nil) do begin Prec:=Pt; Pt:=Pt^.next; end; if (Prec=Nil) then begin dispose(pt); L:=nil; end else begin Prec^.next:=Nil; dispose(Pt); end; end; end;
Remove/Delete ….
Program Lengkap Program SingleLinkList; uses CRT; Type SLL=^data; data=record info:integer; next:SLL; end; List=SLL; Node=SLL; var L:list; pilih:char; sum,ElmIn:Integer; Procedure CreateList (Var L:List); begin L:=nil; end;
Procedure InsertFirst (Var L:List; elm:integer); var P:Node; begin New(P); P^.info:=Elm; if L = nil then Begin L:=P; P^.next:=Nil; end else begin P^.next:=L; L:=P; end; end;
Procedure InsertLast (Var L:list;elm:integer); var Pt,P : Node; begin new(P); P^.info:=elm; if (L=Nil) then begin L:=P; P^.next:=nil; end else begin Pt:=L; while (Pt^.next<>Nil) do Pt:=Pt^.next; P^.next:=Nil; Pt^.next:=P; end; end;
procedure DeleteFirst(var L:List); var P : Node; begin if (L<>Nil) then begin if L^.next = nil then begin P:=L; dispose(P); L:=nil; end else begin P:=L; L:=L^.next; P^.next:=Nil; dispose(P); end; end; end;
procedure DeleteLast(var L:List); var Prec,Pt : Node; begin
if (L<>Nil) then begin Pt:=L; Prec:=Nil; while (Pt^.next<>Nil) do begin Prec:=Pt; Pt:=Pt^.next; end; if (Prec=Nil) then begin dispose(pt); L:=nil; end else begin Prec^.next:=Nil; dispose(Pt); end; end; end;
Procedure penjumlahan(var L:List; var sum: integer); var pt: node; begin Sum:=0; Pt:= L; Sum:=Sum+Pt^.info; while Pt^.next<>nil do begin Pt:=Pt^.next; Sum:=Sum+Pt^.info; end; writeln; write ('Hasil penjumlahan elemen single link list adalah ',sum,''); writeln; end;
Procedure Tampil (Var L:List); Var P:Node; Begin clrscr; if L<> Nil then begin P:=L; write (P^.info); write (' '); P:=P^.next; while P<>nil do begin write (p^.info); write (' '); p:=P^.next; end; end; writeln; end;
label ulang; begin createlist(L); ulang: clrscr; tampil(L); writeln; writeln; writeln ('========= Program Single Linked List ======='); writeln; writeln('1. Insert First'); writeln('2. Insert Last'); writeln('3. Delete Fisrt'); writeln('4. Delete Last'); writeln('5. Penjumlahan'); writeln('0. Exit'); write('Pilih = '); readln(pilih);
case pilih of '1' : begin write('Masukkan Elemen Single Linked List = '); Readln (ElmIn); InsertFirst(L,ElmIn); tampil(L); end; '2' : begin write('Masukkan Elemen Single Linked List = '); Readln (ElmIn); insertlast(L,ElmIn); tampil(L); end; '3' : begin deletefirst(L); tampil(L); end; '4' : begin deletelast(L); tampil(L); end;
'5' : begin penjumlahan(L, sum); end; '0':exit; end; writeln; writeln ('Tekan Enter Untuk Mengulang Program'); readln; goto ulang; end.
