list linier

1CS2014-List Linear/RIE 1

CS2014-Algoritma & StrukturData

List Linear

CS2014-List Linear/RIE 2

Definisi List Linear

z List linier adalah sekumpulan elemen bertipe sama yang mempunyai keterurutan tertentu.

z Setiap elemennya terdiri dari 2 bagian yaitu:type ElmtList :



z Setiap elemennya terdiri dari 2 bagian yaitu:type ElmtList :

dengan :infotype : tipe terdefinisi yang menyimpan bagian datanext : address elemen berikutnya (suksesor)

z Elemen satu dengan yang lain yang berurutan, salingterhubung melalui addressnya.


Definisi List LinearPada suatu list linear dikenali :z alamat elemen pertamanya, (First)z alamat elemen berikutnya (NEXT)z elemen terakhirnya. Ada berbagai cara untuk mengenali

elemen akhir.



Jika L adalah list dan P adalah address, maka :z Alamat elemen pertama list L dapat diacu dengan notasi:

First(L)z Elemen yang diacu oleh P dapat dikonsultasi

informasinya dengan notasi: Info(P)Next(P)

z List L adalah list kosong, jika First(L) = Nilz Elemen terakhir dikenali dengan salah satu cara karena

Next(Last)=Nil.


Fungsionalitas List Linear

Diberikan L, L1, dan L2 adalah list linier dengan ElmListz IsEmpty : L boolean {test apakah list kosong}z CreateEmpty : L {membentuk list linier kosong}z Insert: ElmList x L L {menyisipkan sebuah elemen ke

dalam list}z Delete: L L x ElmList {menghapus sebuah elemen list}z Concat: L1 x L2 L {menyambung L1 dengan L2}z UpdateList: ElmList x L L {mengubah info sebuah

elemen list linier}


Realisasi fungsionalitas List Linearz IsEmpty : L boolean {test apakah list kosong}

z CreateEmpty : L {membentuk list linier kosong}


Realisasi fungsionalitas List Linearz Insert: ElmList x L L {menyisipkan sebuah elemen ke dalam list}

Terdapat 3 kasus insert : - insert sebagai elemen pertama- insert sebagai tengah- insert elemen terakhir

3CS2014-List Linear/RIE 9 CS2014-List Linear/RIE 10


z Delete: L L x ElmList {menghapus sebuah elemen list}Terdapat 3 kasus delete :

- delete terhadap elemen pertama- delete terhadap elemen tengah- delete terhadap elemen terakhir




z Concat: L1 x L2 L {menyambung L1 dengan L2}Concat artinya menggabungkan, dalam kasus ini akan digabungkanList L2 terhadap List L1, sehingga L2 akan menjadi suksesor L1


z UpdateList : ElmList x L L {mengubah info sebuah elemen list linier}

dilakukan dengan terlebih dahulu melakukan tracersal & searching terhadap list, jika elemen ditemukan baru dilakukan update.

z skema traversal pada list



z skema searching pada List Lversi 1 : keluaran berupa address elemen yang dicari dan nilai

boolean true jika elemen ditemukan


versi 2 : keluaran berupa address elemen yang dicari dan nilaiboolean true jika elemen ditemukan, dengan penanganankasus kosong


versi 3 : search berdasarkan alamat tertentu, keluaran berupanilai boolean true jika ditemukan


versi 4 : search berdasarkan kondisi tertentu, keluaran berupanilai boolean true jika ditemukan

list linier

Documents