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 :

CS2014-List Linear/RIE 3

Definisi List Linear

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.

CS2014-List Linear/RIE 4

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.

2CS2014-List Linear/RIE 5

Definisi List Linear

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.

CS2014-List Linear/RIE 6

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}

CS2014-List Linear/RIE 7

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

z CreateEmpty : L {membentuk list linier kosong}

CS2014-List Linear/RIE 8

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

CS2014-List Linear/RIE 11

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

CS2014-List Linear/RIE 12

4CS2014-List Linear/RIE 13 CS2014-List Linear/RIE 14

CS2014-List Linear/RIE 15

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

CS2014-List Linear/RIE 16

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

5CS2014-List Linear/RIE 17 CS2014-List Linear/RIE 18

CS2014-List Linear/RIE 19

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

boolean true jika elemen ditemukan

CS2014-List Linear/RIE 20

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

6CS2014-List Linear/RIE 21

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

CS2014-List Linear/RIE 22

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