linked list atau senatai berantai adalah kunpulan liniar sejumlah data
Post on 11-Jun-2015
2.298 Views
Preview:
TRANSCRIPT
LINKED LIST
Linked list atau senatai berantai adalah kunpulan liniar sejumlah data , atau kumpulan
komponen yang disusun secara berurutan pointer. Masing-masing komponen
dinamakan dengan simpul (node). Simpul dalam suatu Linked list terbagi menjadi dua
bagian yaitu medan informasi yang berisi informasi yang akan disimpan dan diolah,
dan medan penyambung (Link field) yang berisi simpul berikutnya. Ada sejumlah
operasi yang bisa kita lakukan pada sebuah Linked list yaitu membaca isi link,
menambah simpul, menghapus simpul dan mencari informasi pada Linked list .
1. Menambah simpul
Operasi menambah simpul bisa dipecah berdasarkan posisi simpul dabu yang akan
di sisipkan, yaitu simpul baru selalu diletakkan sebagai simpul pertama, dan simpul
baru menyisip diantara kedua simpul yang sudah ada. Berikut contohnya :
type Simpul = ^Data ;
Data = record
Info : char ;
Berikut : Simpul ;
end ;
var Element : char ;
Awal, Akhir, Baru : Simpul ;
2. Menambah di Belakang
Operasi penambahan simpul pada Linked list adalah penambahan suatu Linked list.
Simpul-simpul abru yang ditambahkan selalu menjadi sipmpul terakhir.
Prosedur yang bisa dipanggil dengan memanggil prosedur :
TAMBAH_BELAKANG (Awal, Akhir, Elemen);
Program selengkapnya adalah :
procedure TAMBAH_BELAKANG (var Awal, Akhir : Simpul ;
Elemen : char ) ;
var Baru : Simpul ;
1Edwin Wirencius - 52007012 – Struktur Data - Senerai
begin
new (Baru) ; Baru^.Info :=Elemen;
if Awal = nil then
Awal := Baru
else
Akhir^.Berikut := Baru;
Akhir := Baru;
Akhir^.Berikut := nil
end ;
Senarai Berantai Biasa (Tambah diakhir)
3. Menambah didepan
Operasi penambahan simpul baru akan selalu diletakkan diawal link. Prosedur
untuk menambah simpul bisa dipanggil dengan menggunakan :
TAMBAH_DEPAN (Awal, Akhir, Elemen);
Program selengkapnya adalah :
procedure TAMBAH_DEPAN (var Awal, Akhir : Simpul ;
Elemen : char ) ;
var Baru : Simpul ;
begin
new (Baru) ; Baru^.Info :=Elemen;
if Awal = nil then
Akhir := Baru
else
Baru^.Berikut := Awal;
2Edwin Wirencius - 52007012 – Struktur Data - Senerai
Awal := Baru;
end ;
Senarai Berantai Biasa (Tambah depan)
4. menambah ditengah
Untuk menembah ditengan linked list memerlukan memerlukan bantuan pointer
misalnya bantu, perhatikan contoh program berikut ;
procedure TAMBAH_TENGAH(var Awal, Akhir : Simpul ;
Elemen : char ) ;
var Baru, Bantu : Simpul ;
begin
new (Baru) ; Baru^.Info :=Elemen;
if Awal = nil then
begin
Awal := Baru;
Akhir := Baru;
end;
else
begin
Bantu := Awal;
while Elemen > Baru^.Berikut^.Info do
Bantu := Bantu^.Berikut;
Baru^.Berikut := Bantu^.Berikut;
Bantu^.Berikut := Baru;
end;
3Edwin Wirencius - 52007012 – Struktur Data - Senerai
end ;
Senarai Berantai Biasa (Tambah ditengah)
5. Menghapus Simpul
Operaasi kedua yang akan dijelaskan adalah operasi menghapus simpul. Dalam
menghapus simpul ada suatu hal yang perlu diperhatikan, yaitu bahwa simpul yang bias
dihapus adalah simpul yang berada sesudah simpul yang ditunjukan oleh suatu pointer,
kecuali untuk simpul pertama. Dengan demikian kita tidak bias menghapus simpul yang
ditunjuk oleh suatu pointer atau simpul sebelumnya.
6. Menghapus simpul pertama
Untuk menghapus simpul pertama, maka pointer bantu kita dibuat sama dengan
pointer awal. Kemudian pointer awal kita pindah kesimpul yang ditunjuk oleh pointer
pada simpul yang ditunjuk oleh pointer Bantu. Selanjutnya, simpul yng ditunjuk oleh
pointer Bantu kita dispose.
7. Menghapus simpul ditengah atau terakhir.
Untuk menghapus simpul yang berada di tengah senarai berantai, pertama kali
kita letakan pointer Bantu pada simpul di sebelah kiri simpul yang akan dihapus. Simpul
yang akan dihapus kita tunjuk dengan pointer lain. Kemudian, pointer pada simpul yang
ditunjuk oleh Bantu kita tunjukan pada simpul yang ditunju oleh pointer pada simpul
yang akan dihapus. Selanjutnya simpul yang ditunjuk oleh pointer hapus kita dispose.
4Edwin Wirencius - 52007012 – Struktur Data - Senerai
8. Senarai berantai berkepala
Suatu saat kita perlu meletakan sebuah simpul sebagai simpul pertama dari
sebuah senarai berantai untuk maksud-maksud tertentu. Simpul ini tidak berisi
informasi seperti halnya simpul-simpul lain dalam senarai berantai, tapi keberadaannya
sangat diperlukanuntuk lebih mempercepat proses eksekusi. Simpul yang demikian
disebut dengan simpul kepala (Header Lode) sehingga senarai berantai disebut senarai
berantai berkepala (Headed Linked-List)
Senarai Berantai Berkepala
9. Senarai berantai sebagai tumpukan.
Operasi penambahan simpul baru diawal suatu senarai berantai, sehingga
simpul baru adalah sebagai simpul pertama (harap dibedakan antara simpul kepala dan
simpul pertama), serupa dengan operasi mempush (memasukan elemen kedalam
suatu tumpukan. Dalam kedua kasus ini, elemen baru yang ditambahkan adalah satu-
satunya elemen dalam kumpulan elemen yang bisa segera dimasuk. Tumpukan hanya
bisa dimasuk lewat elemen pertama yang menempati posisi teratas dalam tumpukan,
dan senarai berantai hanya bisa dimasuk lewat pointer yang menuju ke elemen
pertama. Demikian juga halnya dengan operasi POP (menghapus elemen dari suatu
tumpukan). Dalam kedua kasus ini hanya elemen pertama yang bisa dimasuk
(dihapus), dan elemen berikutnya menjasi elemen baru yang bisa segera dimasuk
setelah elemen sebelumnya di POP.
Dengan demikian kita bisa menyejikan tumpukan dengan cara lain, yaitu dengan
senarai berantai linear. Elemen pertama dalam senarai berantai diperlakukan sebagai
elemen teratas dari tumpukan. Dengan mengacu pada prosedur PUSH dan POP kita
5Edwin Wirencius - 52007012 – Struktur Data - Senerai
bisa menyusun prosedur PUSH dan POP yang baru dengan mengingat bahwa kita
ingin menyajikan tumpukan menggunakan senarai berantai.
Senarai Berantai Sbg TumpukanPUSH (Menambah didepan)
atau
10. Single linked list
Apabila setiap kali anda ingin menambahkan data selalu dengan menggunakan
variabel pointer yang baru, anda akan membutuhkan banyak sekali variabel pointer
(penunjuk). Jika anda hanya menggunakan satu variabel pointer saja untuk menyimpan
banyak data dengan metoda yang kita sebut linked list. Jika diterjemahkan, maka
berarti suatu daftar isi yang saling berhubungan.
Dalam pembuatan single linked list dapat menggunakan dua metoda:
a. LIFO (Last In First Out) aplikasinya : Stack (Tumpukan)
Adalah suatu metoda pembuatan linked list dimana data yang masuk paling akhir
adalah data yang keluar paling awal.
b. FIFO (First In First Out) aplikasinya : Queue (Antrian)
Adala suatu metoda pembuatan linked list dimana data yang masuk paling
awal adalah data yang keluar paling awal juga.
Senarai Berantai BerputarInisialisasi
6Edwin Wirencius - 52007012 – Struktur Data - Senerai
Tambah belakang
MULTIPLE LINKED LIST
Multiple linked list merupakan senarai berantai yang memiliki link atau pointer lebih dari
satu. Untuk multiple linked list yang memiliki dua link biasanya disebut sebagai doubly
linked list (senarai berantai ganda). Senarai berantai ganda memiliki dua buah pointer
yang biasanya masing-masing menunjuk ke simpul sebelumnya dan ke simpul
sesudahnya. Jika dideklarasikan dalam deklarasi program maka menjadi sebagai
berikut.
Type Simpul = ^Data;
Data = record
Info : real;
Kanan : simpul; {menunjuk ke simpul sesudahnya}
Kiri : simpul; {menunjuk ke simpul sebelumnya}
End;
Matriks jarang adalah matriks yang elemen tak nolnya sangat sedikit jika dibandingkan
dengan elemen nolnya. Matriks ini mungkin terdiri dari ratusan baris dan kolom atau
bahkan ribuan, tetapi jumlah elemen tak nolnya hanya sekian persen dari seluruh
elemen yang ada pada matriks tersebut. Contoh matriks jarang adalah sebagai berikut.
A =
Dalam pembuatan program untuk menyimpan matriks jarang, yang akan disimpan
hanya elemen tak nolnya saja supaya lebih menghemat. Ada beberapa cara untuk
menyimpan matriks jarang, yaitu dengan array atau menggunakan senarai berantai.
Kedua cara tersebut menggunakan teknik penyimpanan berurutan atau memberikan
7Edwin Wirencius - 52007012 – Struktur Data - Senerai
nomor tertentu pada setiap elemen tak nolnya, dimulai dari elemen tak nol pertama
yang diberi nomor 1, elemen tak nol kedua diberi nomor 2 dan seterusnya. Cara
pemberian nomornya berdasarkan baris, sehingga vektor baris mencatat nomor elemen
tak nolnya. Vektor kolom dan Nilai masing-masing menyimpan nomor kolom dan nilai
elemen tak nolnya. Untuk baris yang semua elemennya bernilai nol, maka dalam vektor
baris dicatat sebagai 0.
Baris Kolom Nilai
1 1 4 2
2 3 8 3
3 0 1 5
4 4 2 1
5 5 10 7
6 6 3 -2
7 0 4 -5
8 8 9 8
9 10 10 -1
10 11 8 4
11 13 6 -17
7 9
Gambar di atas merupakan contoh penyimpanan berurutan untuk matriks jarang pada
gambar 2. dari gambar 3 dapat dilihat bahwa vektor yang dibutuhkan 3 buah, yaitu
vektor Baris, vektor Kolom dan vektor Nilai. Vektor Baris ukurannya selalu sama yaitu
N+1 dimana N adalah banyaknya baris, sedangkan vektor kolom dan nilai ukurannya
gayut terhadap banyaknya elemen tak nolnya. Untuk mengetahui jumlah elemen tak nol
pada suatu baris ke I dapat ditentukan dengan persamaan :
Ni = Baris[I+1] – Baris[I]
Contoh jumlah elemen tak nol baris ke 8 adalah :
8Edwin Wirencius - 52007012 – Struktur Data - Senerai
Ni = Baris[9] – Baris[8] = 10 -8 = 2
Penjelasan di atas digunakan untuk struktur data dengan array. Jika ingin
menggunakan senarai berantai, maka dapat digunakan senarai berantai, maka dapat
digunakan senarai berantai banyak berkepala berputar, dimana deklarasi struktur
datanya adalah sebagai berikut :
Type Matriks = ^Elemen;
Elemen = record
Baris : integer; {nomor baris}
Kolom : integer; {nomor kolom}
Nilai : real; {nilai elemen tak nol}
Kanan : Matriks; {menunjuk ke kolom berikutnya}
Bawah : Matriks; {menunjuk ke Baris berikutnya}
End;
Tabel = array[1..2] of matriks;
baris kolom nilai
bawah kanan
Gambar di atas merupakan cara penyimpanan matriks jarang pada gambar 5. untuk
mempermudah penambahan elemen baru, maka setiap baris dan kolomnya memiliki
simpul kepala. Keseluruhan senarai juga memiliki simpul kepala yang ditunjukkan oleh
pointer M, yang memiliki Baris=0, Kolom=0 dan Nilai=0. Simpul kepala dari kolom
pertama ditunjuk oleh M6.Kanan dan simpul kepala dari baris pertama ditunjuk oleh
M6.Bawah. Simpul kepala dari suatu baris selalu berisi Kolom=0 dan Nilai=0, sedang-
kan simpul kepala dari suatu kolom selalu berisi Baris=0 dan Nilai=0.
Prosedur di bawah ini digunakan untuk membuat simpul baru.
Procedure Buat_Simpul(Var Baru:Matriks;B,K:integer;N:real);
Begin
New(Baru);
With Baru^ do
9Edwin Wirencius - 52007012 – Struktur Data - Senerai
Begin
Baris := B;
Kolom := K;
Nilai := N;
Kanan := nil;
Bawah := nil;
End;
End;
Prosedur di bawah ini digunakan untuk mencek apakah nomor baris tertentu sudah
ada. Jika sudah akan ditunjuk oleh pointer Nb.
Procedure Ada_Baris(Var Nb:Matriks;Ada:Boolean;Awal:Matriks;B:integer);
Begin
Ada := False;
Nb := Awal^.Bawah;
Repeat
If Nb^.baris = B then {Nomor baris ketemu}
Ada := True
Else {belum ketemu}
Nb := Nb^.bawah;
Until Ada or (Nb = Awal) or (Nb^.baris > B)
End;
Prosedur di bawah ini digunakan untuk mencek apakah nomor kolom tertentu sudah
ada. Jika sudah akan ditunjuk oleh pointer Nk.
Procedure Ada_Kolom(Var Nk:Matriks;Ada:Boolean;Awal:Matriks;K:integer);
Begin
Ada := False;
Nk := Awal^.kanan;
Repeat
10Edwin Wirencius - 52007012 – Struktur Data - Senerai
If Nk^.kolom = K then {Nomor kolom ketemu}
Ada := True
Else {belum ketemu}
Nk := Nk^.kanan;
Until Ada or (Nk = Awal) or (Nk^.kolom > K)
End;
Prosedur di bawah ini digunakan untuk menyisipkan elemen baru sesuai dengan
posisinya.
Procedure Sisip_Elemen(Var Awal:Matriks;B,K:integer;N:real);
Var Baru,Sb,Sk,N_baris,N_kolom,Bb : Matriks;
Ada : Boolean;
Begin
Buat_Simpul(Baru,B,K,N);
{Menset Nomor Baris}
Ada_Baris(N_baris,Ada,Awal,B);
If not (Ada) then
{Ini adalah baris baru}
{menentukan letak simpul kepala}
{untuk nomor baris}
Begin
Buat_Simpul(Sb,B,0,0);
{membentuk senarai berputar}
Sb^.kanan := Sb;
Sb^.bawah := Sb;
Bb := Awal;
While (Bb^.bawah^.barisAwal) do
Bb := Bb^.bawah;
If Bb^.bawah = Awal then
Sb^.bawah := Awal
Else
11Edwin Wirencius - 52007012 – Struktur Data - Senerai
Sb^.bawah := Bb^.bawah;
Bb^.bawah := Sb;
N_baris := Sb;
End;
{Mentest nomor kolom}
Ada_kolom(N_kolom,Ada,Awal,K);
If not (Ada) then
{Ini adalah kolom baru menentukan}
{letak simpul kepala untuk nomor kolom}
Begin
Buat_Simpul(Sk,0,K,0);
{membentuk senarai berputar}
Sk^.kanan := Sk;
Sk^.bawah := Sk;
Bb := Awal;
While (Bb^.kanan^.kolomAwal) do
Bb := Bb^.kanan;
If Bb^.kanan = Awal then
Sk^.kanan := Awal
Else
Sk^.kanan := Bb^.kanan;
Bb^.kanan := Sk;
N_kolom := Sk;
End;
{Menentukan letak elemen baru pada posisinya yang tepat}
{Mencari lokasi baris}
Sb := N_baris;
While (Sb^.kanan^.kolom0) do
Sb := Sb^.kanan;
12Edwin Wirencius - 52007012 – Struktur Data - Senerai
If Sb^.kanan^.kolom = 0 then
Baru^.kanan := N_baris
Else
Baru^.kanan := Sb^.kanan;
Sb^.kanan := Baru;
{Mencari lokasi kolom}
Sk := N_kolom;
While (Sk^.bawah^.baris0) do
Sk := Sk^.bawah;
If Sk^.bawah^.baris = 0 then
Baru^.bawah := N_kolom
Else
Baru^.bawah := Sk^.bawah;
Sk^.bawah := Baru;
End;
Senarai Berantai Ganda
Menambah didepan
Menambah ditengah
13Edwin Wirencius - 52007012 – Struktur Data - Senerai
Menambah dibelakang
Senarai Berantai Ganda Berputar
Inisialisasi
Tambah SimpulC>D
Hapus Simpul
A ≠ B
B = BBantu kembali ke Kepala
14Edwin Wirencius - 52007012 – Struktur Data - Senerai
top related