sd bab 8a (senarai)

SENARAI BERANTAI

KONSEP SENARAI

Konsep logika senarai dapat diilustrasikan seperti sebuah kereta api

Badan keretaLokomotif

Kait Penghubung Gerbong

Gambar Rangkaian Kereta Api

KONSEP SENARAI

Senarai digunakan untuk menyimpan sekumpulan data yang bertipe sama (tipe dasar atau tipe terstruktur).

Senarai disebut juga dengan senarai berkait (Linked List).

Sebuah senarai mempunyai dua bagian: Bagian pertama adalah kepala (head). Bagian kedua dari senarai adalah badan

senarai

DEFINISI SENARAI

Konsep senarai berasal dari bidang matematika

Senarai dinyatakan sebagai runtunan elemen yang dipisahkan dengan tanda koma, yaitu:

a1, a2, a3, …, ai, …, an-1

Banyaknya elemen dalam senarai adalah n dan disebut dengan panjang senarai.

Setiap elemen dalam senarai mempunyai predesesor dan suksesor

DEFINISI SENARAI

Elemen pada badan senarai terdiri dari dua bagian yaitu bagian informasi atau data dan bagian alamat.

Info mewakili informasi Next mewakili alamat suksesor.

Gambar (a) Gambaran Logika elemen senarai, (b) Alamat Nil

NOTASI

Dalam pembahasan algoritmik menggunakan notasi khusus sebagai berikut: Kepala(S), menyatakan alamat elemen

pertama senarai S Info(P), menyatakan field Info dari elemen

yang alamatnya P Next(P), menyatakan field Next dari

elemen yang alamatnya P

PENGGAMBARAN SENARAI

Gambar (a) Senarai dengan 1 elemen, (b) Senarai elemen bertipe integer(c) Senarai elemen bertipe terstruktur

PENDEKLARASIAN SENARAI

Contoh:

Deklarasi

Type TipeInfo : integer Type ElmSenarai : record <Info : TipeInfo,

Next : Alamat>

Type Senarai : ElmSenarai

Deklarasi

Type DataInt : record <Bil : integer, Next : Alamat> Type DataMhs : record < NIM : integer, Nama : string,

IPK : real, Next : Alamat>

PREDESESOR DAN SUKSESOR

Suksesor sebuah elemen dapat langsung diketahui dari alamat di dalam field yang menyimpan alamat predesesor yaitu field next-nya.

Predesesor sebuah elemen tidak dapat langsung diketahui, sebab tidak ada field yang berisi alamat elemen sebelumya

Senarai adalah struktur data dinamis.

PENELUSURAN SENARAI

Dua skema penelusuran senarai: pertama melakukan aksi khusus apabila senarai kosong, sedangkan skema yang kedua tidak.procedure Penelusuran1(input S : Senarai)

Deklarasi P : Alamat

Deskripsi if Kepala(S) = Nil then { Senarai Kosong } write(“Senarai Kosong’) else inisialisasi P Kepala(S){ alamat elemen pertama } repeat Proses(P) { proses elemen yang alamatnya P } P Next(P){ ambil alamat elemen berikutnya } until P = Nil Terminasi endif

OPERASI-OPERASI DASAR PADA SENARAI

Operasi dasar berdasarkan fungsinya, yaitu:

1. Membuat senarai (Create)2. Memeriksa Status (State)3. Penghapusan (Remove)4. Penambahan elemen baru (add)5. Penyisipan (Insertion)6. Mengambil/mengedit informasi elemen

(Retrieval/Modification)7. Iterasi (Iteration)8. Pencarian (Searching)

MEMBUAT SENARAI KOSONG (CREATE)

procedure ListCreate(output S : Senarai)

Deklarasi P : Alamat

Deskripsi Kepala(S) Nil

MEMERIKSA STATUS (STATE)

procedure ListEmpty(input S : Senarai) boolean

Deklarasi P : Alamat

Deskripsi return Kepala(S) Nil

PENGHAPUSAN (REMOVE)

Terdapat beberapa operasi penghapusan yaitu:1. Penghapusan elemen di Kepala Senarai

Kemungkinan 1: Jumlah elemen senarai lebih dari satuKemungkinan 2: Senarai hanya terdiri dari satu

elemen

2. Penghapusan elemen di Akhir Senarai3. Penghapusan elemen di Tengah Senarai4. Penghapusan elemen Berdasarkan indeks

Posisi Tertentu

PENGHAPUSAN (REMOVE)

procedure ListRemoveInside(input/output PredP : Alamat)

Deklarasi P : Alamat

Deskripsi P Next(PredP) Next(PredP) Next(Next(PredP)

procedure ListRemoveHead(input/output S : Senarai,output P : Alamat)

Deklarasi { tidak ada }

Deskripsi P Kepala(S) Kepala(S) Next(Kepala(S))

PENGHAPUSAN (REMOVE)procedure ListRemoveTail(input/output S : Senarai,

output P : Alamat)

Deklarasi PredAkhir, Akhir : Alamat

Deskripsi Akhir Kepala(S) PredAkhir Nil while Next(Akhir) ≠ Nil do Akhir Next(Akhir) endwhile

P Akhir if PredAkhir = Nil then Kepala(S) Nil else Next(PredAkhir) Nil endif

PENAMBAHAN ELEMEN BARU (ADD)

Penambahan elemen dapat dilakukan di:1. Menambah Elemen di Kepala

Kemungkinan 1: Senarai KosongKemungkinan 2: Senarai tidak kosong

2. Menambah Elemen di Akhir

PENAMBAHAN ELEMEN BARU (ADD)

procedure ListAddHead(input/output S : Senarai,input P : Alamat)

Deklarasi { tidak ada }

Deskripsi Next(P) Kepala(S) Kepala(S) P

PENAMBAHAN ELEMEN BARU (ADD)

procedure ListAddtail(input/output S : Senarai,input P : Alamat)

Deklarasi Akhir : Alamat

Deskripsi if Kepala(S) = Nil then Kepala(S) P else Akhir Kepala(S) while Next(Akhir) ≠ Nil Akhir Next(Akhir) endwhile

Next(Akhir) P endif

PENYISIPAN ELEMEN (INSERTION)

Penyisipan di tengah senarai berarti menambahkan sebuah elemen yang alamatnya sesudah elemen lain yang alamatnya PredP.procedure ListInsert(input P : Alamat,

input PredP : Alamat)

Deklarasi { tidak ada }

Deskripsi Next(P) Next(PredP) Next(PredP) P

MENGAMBIL/MENGEDIT INFORMASI ELEMEN (RETRIEVAL/MODIFICATION)

Pengambilan informasi elemen (info) kadang-kadang diperlukan untuk proses lebih lanjut.

Pengambilan informasi dapat dilakukan terhadap elemen pada Kepala, elemen terakhir dan elemen pada indeks posisi tertentu.

MENGAMBIL INFORMASI ELEMEN

procedure ListGetHead(input S : Senarai, output E : TipeInfo)

Deklarasi P : Alamat

Deskripsi P Kepala(S) E Info(P)

procedure ListGetTail(input S : Senarai, output E : TipeInfo)

Deklarasi P : Alamat

Deskripsi P Kepala(S) repeat P Next(P) until Next(P) = Nil E Info(P)

MENGEDIT INFORMASI ELEMEN

procedure ListSet(input S : Senarai,input E : TipeInfo,input P : Alamat)

Deklarasi { tidak ada }

Deskripsi Info(P) E

ITERASI (ITERATION)

Kelompok operasi pada iterasi ini berguna untuk penelusuran senarai berkait secara beruntun.

Meliputi operasi untuk mendapatkan alamat elemen pertama (Kepala), alamat elemen terakhir (Ekor) dan alamat elemen suksesor sebuah elemen.

ITERASI (ITERATION)function ListHeadAddress(input S : Senarai) Alamat

Deklarasi P : Alamat

Deskripsi return Kepala(S)

function ListHeadAddress(input S : Senarai) Alamat

Deklarasi P : Alamat

Deskripsi return Next(P)

ITERASI (ITERATION)

Menentukan Alamat Elemen Terakhirfunction ListTailAddress(input S : Senarai) Alamat

Deklarasi P : Alamat

Deskripsi if Kepala(S) = Nil then return Nil else Akhir Kepala(S) while Next(Akhir) ≠ Nil do Akhir Next(Akhir) endwhile

return Akhir endif

PENCARIAN (SEARCHING)

Pencarian adalah proses yang mendasar dalam pengolahan data.

Dalam senarai, pencarian elemen dilakukan misalnya bila harga elemen hendak diubah, atau bila elemen baru hendak disisipkan atau sebuah elemen akan dihapus

Pencarian elemen di dalam senarai dapat dilakukan berdasarkan: Pencarian berdasarkan nilai Pencarian berdasarkan alamat.

PENCARIAN (SEARCHING)

Pencarian Berdasarkan Nilaiprocedure ListFind(input S : Senarai, input X : TipeInfo,

output ketemu : boolean, output : Alamat)

Deklarasi { tidak ada }

Deskripsi P Kepala(S) { pencarian dimulai dari elemen pertama } ketemu false while (P ≠ Nil) and (not ketemu) do if Info(P) = X then ketemu true else P Next(P) endif endwhile { P = Nil or not ketemu }

PENCARIAN (SEARCHING)

Pencarian Berdasarkan Alamatprocedure ListFindAddress(input S : Senarai, input P : Alamat,

output ketemu : boolean)

Deklarasi PS : Alamat

Deskripsi PS Kepala(S) { pencarian dimulai dari elemen pertama } ketemu false while (PS ≠ Nil) and (not ketemu) do if PS = P then ketemu true else PS Next(PS) endif endwhile { PS = Nil or not ketemu }

OPERASI TERHADAP DUA SENARAI

Menyambung Dua Buah Senarai (Concat)procedure ListConcat(input S1, S2 : Senarai, output S3 : Senarai)

Deklarasi Akhir1 : Alamat

Deskripsi Kepala(S3) Nil if Kepala(S1) = Nil then Kepala(S3) Kepala(S2) else Kepala(S3) Kepala(S1) Akhir1 Kepala(S1) while Next(Akhir1) ≠ Nil do Akhir1 Next(Akhir1) endwhile

Next(Akhir1) Kepala(S2) endif

OPERASI TERHADAP DUA SENARAI

Membandingkan Dua Buah Senaraifunction ListSama(input S1, S2 : Senarai) boolean

Deklarasi P1, P2 : Alamat podo : boolean

Deskripsi podo true P1 Kepala(S1) P2 Kepala(S2) while (P1 ≠ Nil) and (P2 ≠ Nil) and (podo) do if Info(P1) = Info(P2) then { pemeriksa elemen berikutnya } P1 Next(P1) P2 Next(P2) else podo false endif endwhile return podo