list linier

44
1 4. Linked List (List 4. Linked List (List Linier) Linier) 4.1. Definisi 4.1. Definisi List linier adalah List linier adalah sekumpulan sekumpulan elemen elemen bertype sama, yang bertype sama, yang mempunyai keterurutan tertentu, mempunyai keterurutan tertentu, yang setiap elemennya terdiri yang setiap elemennya terdiri dari 2 bagian : dari 2 bagian : Type Elmtlist = Type Elmtlist = record record < Info : InfoType, < Info : InfoType, Next : address > Next : address >

Upload: radenajengcemutch

Post on 24-Jun-2015

673 views

Category:

Documents


1 download

TRANSCRIPT

Page 1: List Linier

1

4. Linked List (List 4. Linked List (List Linier)Linier)

4.1. Definisi4.1. DefinisiList linier adalah List linier adalah sekumpulan sekumpulan

elemen elemen bertype sama, yang bertype sama, yang mempunyai keterurutan mempunyai keterurutan tertentu, yang setiap elemennya tertentu, yang setiap elemennya terdiri dari 2 bagian :terdiri dari 2 bagian :

Type Elmtlist = Type Elmtlist = recordrecord < Info : InfoType, < Info : InfoType, Next : address > Next : address >

Page 2: List Linier

2

Dengan Info Type adalah sebuah type Dengan Info Type adalah sebuah type terdefenisi yang menyimpan terdefenisi yang menyimpan informasi sebuah elemen list ; Next informasi sebuah elemen list ; Next adalah address dari elemen adalah address dari elemen berikutnya ( suksesor ).berikutnya ( suksesor ).

Dengan demikian, jika didefinisikan Dengan demikian, jika didefinisikan First First adalah alamt elemen pertama adalah alamt elemen pertama list, maka list, maka elemen berikutnya dapat elemen berikutnya dapat diakses secara diakses secara suksesif dari elemen suksesif dari elemen pertama tersebut pertama tersebut

Page 3: List Linier

3

Jadi, sebuah list linier dikenali :Jadi, sebuah list linier dikenali : elemen pertamanya, elemen pertamanya, biasanya melalui biasanya melalui

alamat elemen pertama yang disebutalamat elemen pertama yang disebut : : FirstFirst

alamatalamat elemen berikutnya elemen berikutnya ( suksesor ), ( suksesor ), jika kita mengetahui alamat sebuah jika kita mengetahui alamat sebuah elemen , yang dapat diakses melalui field elemen , yang dapat diakses melalui field NEXTNEXT

setiap elemen mempunyai alamatsetiap elemen mempunyai alamat, , yaitu tempat elemen disimpan dapat yaitu tempat elemen disimpan dapat diacu.Untuk mengacu sebuah elemen , diacu.Untuk mengacu sebuah elemen , alamat harus terdefenisi . Dengan alamat alamat harus terdefenisi . Dengan alamat tersebut Informasi yang tersimpan pada tersebut Informasi yang tersimpan pada elemen list dapat diakses . elemen list dapat diakses .

elemen terakhirnya. elemen terakhirnya. Ada berbagai cara Ada berbagai cara untuk mengenali elemen akhir untuk mengenali elemen akhir

Page 4: List Linier

4

Jika L adalah list , dan P adalah address Jika L adalah list , dan P adalah address ::

Alamat elemen pertama list L dapat Alamat elemen pertama list L dapat diacu diacu

dengan notasi :dengan notasi :

First (L)First (L)

Elemen yang diacu oleh P dapat Elemen yang diacu oleh P dapat dikonsultasi dikonsultasi

informasinya dengan notasi :informasinya dengan notasi :

Info(P)Info(P)

Next(P)Next(P)

Page 5: List Linier

5

Beberapa definisi :Beberapa definisi :1. List L adalah List kosong , jika 1. List L adalah List kosong , jika First First

(L) = Nil(L) = Nil

2. Elemen terakhir dikenali, dengan 2. Elemen terakhir dikenali, dengan salah satu cara adalah karena salah satu cara adalah karena Next(Last) =NilNext(Last) =Nil

Nil adalah pengganti Null, dalam bahasa Nil adalah pengganti Null, dalam bahasa C perubahan ini dituliskan denganC perubahan ini dituliskan dengan

#define Nil Null#define Nil Null

Page 6: List Linier

6

Bagian Deklarasi dari algoritma pada List Linier :Bagian Deklarasi dari algoritma pada List Linier :DeklarasiDeklarasi

typetype InfoType = … {Sebuah type terdefinisi} InfoType = … {Sebuah type terdefinisi}typetype Address Address pointerpointer toto ElmtL ElmtLtypetype ElmtL = ElmtL = recordrecord

<Info : InfoType,<Info : InfoType,Next : Address >Next : Address >

typetype List = List = recordrecord <First : Address > <First : Address >atau dapat juga atau dapat juga typetype List = Address List = Address

{Deklarasi Nama Peubah}{Deklarasi Nama Peubah}L : ListL : ListP : AddressP : Address

Page 7: List Linier

7

{Deklarasi Nama Peubah}{Deklarasi Nama Peubah}

L : ListL : List

P : AddressP : Address

{Maka penulisan {Maka penulisan First (L) menjadi First (L) menjadi (L) (L)

Next (P) menjadi Next (P) menjadi (P)->Next (P)->Next

Info (P) menjadi Info (P) menjadi (P)->Info(P)->Info

Null menjadi Nil }Null menjadi Nil }

Page 8: List Linier

8

II. Skema II. Skema traversaltraversal untuk list untuk list linierlinierList terdiri dari sekumpulan List terdiri dari sekumpulan elemen. Seringkali diperlukan elemen. Seringkali diperlukan untuk memproses setiap elemen untuk memproses setiap elemen list dengan cara yang sama. Karena list dengan cara yang sama. Karena itu salah primitif operasi konsultasi itu salah primitif operasi konsultasi dasar pada struktur list adalah dasar pada struktur list adalah traversal, yaitu “mengunjungi” traversal, yaitu “mengunjungi” setiap elemen list untuk diproses. setiap elemen list untuk diproses.

Page 9: List Linier

9

Karena Urutan akses adalah Karena Urutan akses adalah dari elemen pertama dari elemen pertama sampai dengan elemen sampai dengan elemen terakhir, terakhir, maka traversal maka traversal list secara natural list secara natural dilakukan dari elemen dilakukan dari elemen pertama, suksesornya, dan pertama, suksesornya, dan seterusnya sampai dengan seterusnya sampai dengan elemen terakhir. elemen terakhir.

Page 10: List Linier

10

Skema traversal yang dipakai adalah Skema traversal yang dipakai adalah Sbb :Sbb :

Procedure Procedure SKEMAListTransversal1SKEMAListTransversal1(( Input Input L : L : List ) List )

{K. Awal : List L terdefinisi , mungkin kosong }{K. Awal : List L terdefinisi , mungkin kosong }

{K. Akhir : semua elemen list L dikunjungi dan {K. Akhir : semua elemen list L dikunjungi dan telah telah diproses } diproses }

{Proses : Traversal sebuah list linier. Dengan {Proses : Traversal sebuah list linier. Dengan MARK, MARK, tanpa tanpa pemrosesan khusus pemrosesan khusus pada list kosong}pada list kosong}

DeklarasiDeklarasi

Page 11: List Linier

11

DeklarasiDeklarasiP : addressP : address { address untuk traversal , { address untuk traversal , type type terdefenisi }terdefenisi }

DeskripsiDeskripsi Inisialisasi Inisialisasi P ← First ( L )P ← First ( L ) { First { First

Element } Element } While While ( P ≠Nil ) ( P ≠Nil ) dodo Proses ( P )Proses ( P )

P ← Next ( P )P ← Next ( P ) { Next { Next element }element }

endwhileendwhile TerminasiTerminasi

Page 12: List Linier

12

ProcedureProcedureSKEMAListTransversal SKEMAListTransversal 2( 2( Input Input L : L : List ) List )

{ K. Awal : List L terdefenisi , mungkin { K. Awal : List L terdefenisi , mungkin kosong } kosong }

{ K. Akhir : semua elemen list L { K. Akhir : semua elemen list L “dikunjungan “ “dikunjungan “ dan telah dan telah diproses }diproses }

{ Proses : Transversal sebuah list linier { Proses : Transversal sebuah list linier yang yang diidentifikasi oleh diidentifikasi oleh elemen pertama L , elemen pertama L , Dengan Dengan MARK dan MARK dan pemrosesan pemrosesan khusus pada list kosong }khusus pada list kosong }

DeklarasiDeklarasi

Page 13: List Linier

13

DeklarasiDeklarasiP : addressP : address {address untuk {address untuk traversal , type traversal , type terdefenisi }terdefenisi }

DeskripsiDeskripsi

IfIf ( (First ( L ) = Nil) First ( L ) = Nil) then then

Write Write ( ‘List kosong ‘ )( ‘List kosong ‘ )

elseelse

Page 14: List Linier

14

Insialisasi Insialisasi

P ←P ← First ( L )First ( L ) { First { First Element }Element }

RepeatRepeat

Proses ( P )Proses ( P )

P ← Next ( P )P ← Next ( P ) { Next { Next element }element }

untiluntil P=Nil P=Nil

TerminasiTerminasi

Page 15: List Linier

15

III. Skema Sequential Search untuk III. Skema Sequential Search untuk list list linier linier Selain traversal, proses pencarian suatu Selain traversal, proses pencarian suatu elemen elemen list list adalah primitif yang sering kali adalah primitif yang sering kali didefinisikan pada didefinisikan pada struktur list. Pencarian struktur list. Pencarian dapat berdasarkan nilai, atau dapat berdasarkan nilai, atau berdasarkan berdasarkan alamat. alamat.

III.1. Search suatu Nilai, output adalah III.1. Search suatu Nilai, output adalah addressaddressSearch ini sering dipakai untuk mengenali Search ini sering dipakai untuk mengenali suatu suatu elemen list berdasarkan nilai elemen list berdasarkan nilai informasi yang informasi yang disimpan pada elemen yang disimpan pada elemen yang dicari. Biasanya dicari. Biasanya dengan alamat yang dengan alamat yang ditemukan, akan dilakukan ditemukan, akan dilakukan suatu proses suatu proses terhadap elemen list tersebut. terhadap elemen list tersebut.

Page 16: List Linier

16

Procedure Procedure SKEMAList SKEMAListSearchSearch1 ( 1 ( InputInput L : List, L : List, X : InfoType, X : InfoType, OutputOutput P : address, P : address, Found: Found: Boolean Boolean ))

{ K. Awal : List linier L sudah terdefinisi dan { K. Awal : List linier L sudah terdefinisi dan siap siap dikonsultasi, X terdefenisi }dikonsultasi, X terdefenisi }

{ K.Akhir : P : address pada pencarian { K.Akhir : P : address pada pencarian beurutan, beurutan, dimana X dimana X diketemukan, P = Nil jika diketemukan, P = Nil jika tidak tidak ketemu, Found berharga true jika ketemu, Found berharga true jika

harga X yang dicari ketemu, false jika harga X yang dicari ketemu, false jika tidak } tidak }

Page 17: List Linier

17

{Proses : Sequential Search harga X {Proses : Sequential Search harga X pada sebuah pada sebuah list linier L, Semua list linier L, Semua elemen diperiksa elemen diperiksa dengan intruksi yang sama, versi dengan intruksi yang sama, versi dengan dengan Boolean} Boolean}

DeklarasiDeklarasi

DeskripsiDeskripsi

Page 18: List Linier

18

P ← First ( L )P ← First ( L )Found ← Found ← falsefalseWhileWhile ( P ≠ Nil ) ( P ≠ Nil ) andand ( ( notnot found ) found ) dodo

ifif X = Info (P) X = Info (P) thenthenFound ←TrueFound ←True

else else P ← Next (P)P ← Next (P)

endifendifendwhileendwhile { P = Nil { P = Nil oror Found} Found}{Jika Found maka P adalah address {Jika Found maka P adalah address dimana dimana harga yang dicari harga yang dicari diketemukan}diketemukan}

Page 19: List Linier

19

III. 2. Search suatu Elemen yang III. 2. Search suatu Elemen yang beralamat tertentu beralamat tertentu

Procedure Procedure SKEMAList SKEMAList Search@Search@( ( InputInput L : List, L : List, P : P : address, Found: address, Found: Boolean Boolean ))

{K. Awal : List linier L sudah terdefinisi dan siap {K. Awal : List linier L sudah terdefinisi dan siap dikonsultasi, X terdefenisi } dikonsultasi, X terdefenisi }

{K.Akhir : Jika ada elemen list beralamat P, Found {K.Akhir : Jika ada elemen list beralamat P, Found berharga true, Jika tidak ada berharga true, Jika tidak ada

elemen list elemen list beralamat P, Found beralamat P, Found berharga false }berharga false }

{Proses : Sequential Search @ P pada sebuah list {Proses : Sequential Search @ P pada sebuah list linier L, linier L, Semua elemen diperiksa Semua elemen diperiksa dengan intruksi yang dengan intruksi yang sama } sama }

Page 20: List Linier

20

DeklarasiDeklarasiPt : addressPt : address

DeskripsiDeskripsiPt ← First ( L )Pt ← First ( L )Found ← Found ← falsefalseWhileWhile ( Pt ≠ Nil ) and ( ( Pt ≠ Nil ) and ( notnot found ) found ) dodo

ifif Pt = P Pt = P thenthen Found ← Found ← true true

else else Pt ← Next (Pt)Pt ← Next (Pt)

endifendifendwhileendwhile { Pt = Nil { Pt = Nil oror Found} Found}{ Jika Found maka P adalah elemen list}{ Jika Found maka P adalah elemen list}

Page 21: List Linier

21

IV. Definisi fungsional list linier IV. Definisi fungsional list linier dan dan algoritmanyaalgoritmanya

Secara fungsional, pada sebuah Secara fungsional, pada sebuah list linier list linier biasanya dilakukan biasanya dilakukan pembuatan, penambahan pembuatan, penambahan atau atau penghapusan elemen yang dapat penghapusan elemen yang dapat ditulis ditulis sebagai berkut :sebagai berkut :

Jika diberikan L, L1 dan L2 adalah Jika diberikan L, L1 dan L2 adalah list linier list linier dengan elemen ElmtList, dengan elemen ElmtList, maka operasi yang maka operasi yang dapat dilakukan : dapat dilakukan :

ListEmpty, CreateList, ListEmpty, CreateList, Insert, Insert, Delete, Concat dan Delete, Concat dan UpdateListUpdateList

Page 22: List Linier

22

IV. 1. Pengetesan List KosongIV. 1. Pengetesan List KosongPemeriksaan apakah sebuah list kosong Pemeriksaan apakah sebuah list kosong

sangat sangat penting, karena Keadaan penting, karena Keadaan Awal dan Keadaan Awal dan Keadaan Akhir beberapa Akhir beberapa prosedur harus didefinisikan prosedur harus didefinisikan berdasarkan keadaan list. Operasi berdasarkan keadaan list. Operasi pada list pada list kosong sering kali kosong sering kali membutuhkan membutuhkan penanganan khusus penanganan khusus Realisasi algoritmik dari Realisasi algoritmik dari definisi definisi fungsional ini adalah sebuah fungsi fungsional ini adalah sebuah fungsi

sebagai berikut. sebagai berikut.

Page 23: List Linier

23

FunctionFunction IsEmptyList (L : List ) → IsEmptyList (L : List ) → booleanboolean

{ Test apakah sebuah list L { Test apakah sebuah list L kosong, Mengirimkan kosong, Mengirimkan true true jika jika list kosong, list kosong, falsefalse jika tidak jika tidak kosong}kosong}

DeklarasiDeklarasi

DeskripsiDeskripsi

returnreturn(First (L) = Nil)(First (L) = Nil)

Page 24: List Linier

24

IV.2 Pembuatan sebuah IV.2 Pembuatan sebuah elemen pada elemen pada list list linierlinier

Pembuatan sebuah list berarti Pembuatan sebuah list berarti membuat membuat sebuat list KOSONG, sebuat list KOSONG, yang selanjutnya yang selanjutnya siap diproses siap diproses (ditambah elemennya, (ditambah elemennya, dsb). dsb). Realisasi algoritmik dari defenisi Realisasi algoritmik dari defenisi

funfsional ini adalah sebuah funfsional ini adalah sebuah prosedur prosedur sebagai berikut.sebagai berikut.

Page 25: List Linier

25

Procedure Procedure CreateListCreateList( ( OutputOutput L : L : List )List )

{K. Awal : Sembarang }{K. Awal : Sembarang }

K. Akhir : terbentuk list L yang K. Akhir : terbentuk list L yang kosong : First (L) kosong : First (L) diinisialisasi dengan NIL )diinisialisasi dengan NIL )

Proses : Membuat list kosong}Proses : Membuat list kosong}

DeklarasiDeklarasi

DeskripsiDeskripsi First (L) ← Nil First (L) ← Nil

Page 26: List Linier

26

IV. 3 Penyisipan sebuah IV. 3 Penyisipan sebuah elemen elemen pada list pada list linierlinier

Fungsi insert (penyisipan) harus Fungsi insert (penyisipan) harus dijabarkan lebih rinci, karena dapat dijabarkan lebih rinci, karena dapat menjadi penyisipan sebagai elemen menjadi penyisipan sebagai elemen pertama, setelah sebuah address P atau pertama, setelah sebuah address P atau penyisipan menjadi elemen terakhir atau penyisipan menjadi elemen terakhir atau bahkan menjadi elemen ditengahbahkan menjadi elemen ditengah

Penyisipan sebuah elemen dapat dilakukan Penyisipan sebuah elemen dapat dilakukan terhadap sebuah elemen yang sudah terhadap sebuah elemen yang sudah dialokasi (diketahui address-nya ), atau dialokasi (diketahui address-nya ), atau sebuah elemen yang hanya diketahui sebuah elemen yang hanya diketahui nilai Info-nya (berarti belum dialokasi).nilai Info-nya (berarti belum dialokasi).

Page 27: List Linier

27

IV. 2.1. INSERT-First (Address)IV. 2.1. INSERT-First (Address)Menambahkan sebuah elemen yang Menambahkan sebuah elemen yang

diketahui diketahui alamatnya sebagai elemen alamatnya sebagai elemen pertama list.pertama list.

Procedure Procedure InsertFirst (InsertFirst (Input/Output Input/Output L:List, L:List, Input Input P: address)P: address)

{K. Awal : List L {K. Awal : List L mungkin kosong mungkin kosong {K. Akhir : P adalah elemen pertama list L}{K. Akhir : P adalah elemen pertama list L}{Proses : Insert sebuah elemen beralamat {Proses : Insert sebuah elemen beralamat

P sebagai P sebagai elemen pertama list linier L elemen pertama list linier L yang mungkin kosong} yang mungkin kosong}

DeklarasiDeklarasiDeskripsiDeskripsi Next (P)Next (P) ← ← First (L)First (L) First (L) ← PFirst (L) ← P

Page 28: List Linier

28

IV.2.2 INSERT-First (Nilai)IV.2.2 INSERT-First (Nilai)Menambahkan sebuah elemen yang diketahui nilainya sebagai elemen Menambahkan sebuah elemen yang diketahui nilainya sebagai elemen

pertama list.pertama list.

ProcedureProcedure InsFirst InsFirst ((Input/outputInput/output L :ListL :List, , InputInput E : E : infotype )infotype )

{ K. Awal : List L{ K. Awal : List L mungkin kosong mungkin kosong } }{ K. Akhir : Sebuah elemen dialokasikan dan menjadi elemen { K. Akhir : Sebuah elemen dialokasikan dan menjadi elemen

pertama list L, jika alokasi berhasil. Jika alokasi pertama list L, jika alokasi berhasil. Jika alokasi gagal gagal list tetap seperti semula } list tetap seperti semula }

{ Proses : Insert sebuah elemen sebagai elemen pertama { Proses : Insert sebuah elemen sebagai elemen pertama list} list}

DeklarasiDeklarasiP : addressP : address

DeskripsiDeskripsi Alokasi (P)Alokasi (P) IfIf P ≠ Nil P ≠ Nil thenthen

Info (P) ← EInfo (P) ← ENext (P) ← First (L) Next (P) ← First (L) First (L) ← P First (L) ← P

endifendif

Page 29: List Linier

29

IV.2.2. INSERT-AFTER IV.2.2. INSERT-AFTER Menyisihkan sebuah elemen beralamat P sebagai Menyisihkan sebuah elemen beralamat P sebagai

suksesor dari sebuah elemen list linier yang suksesor dari sebuah elemen list linier yang beralamat Precberalamat Prec

Procedure Procedure InsertAfter InsertAfter ( ( Input Input P, Prec: P, Prec: address )address )

{K. Awal : Prec adalah elemen list, prec ≠ Nil, P {K. Awal : Prec adalah elemen list, prec ≠ Nil, P sudah sudah dialokasikan, P ≠ Nil, Next (P) = dialokasikan, P ≠ Nil, Next (P) = NilNil

K. Akhir : P menjadi suksesor Prec K. Akhir : P menjadi suksesor Prec Proses : Insert sebuah elemen beralamat P Proses : Insert sebuah elemen beralamat P

pada List pada List linier L} linier L}DeklarasiDeklarasiDeskripsiDeskripsi

Next (P) ← Next (Prec) Next (P) ← Next (Prec) Next (Prec) ← PNext (Prec) ← P

Page 30: List Linier

30

IV. 2.3. INSERT – LastIV. 2.3. INSERT – Last

Menyisipkan sebuah elemen beralamat P Menyisipkan sebuah elemen beralamat P sebagai elemen terakhir sebuah list linier. sebagai elemen terakhir sebuah list linier. Ada dua kemungkinan list kosong atau tidak Ada dua kemungkinan list kosong atau tidak kosongkosong

ProcedurProcedur InsertLast@InsertLast@((Input/OutputInput/Output L: List, L: List, InputInput P : P : address) address)

{K. Awal : List L mungkin kosong, P sudah {K. Awal : List L mungkin kosong, P sudah dialokasi, dialokasi, P ≠ Nil, Next (P) = Nil P ≠ Nil, Next (P) = Nil

K. Akhir : P adalah elemen terakhir list LK. Akhir : P adalah elemen terakhir list L

Proses : Insert sebuah elemen beralamat P sbg Proses : Insert sebuah elemen beralamat P sbg elemen elemen terakhir dari list linier L yg terakhir dari list linier L yg mungkin kosong }mungkin kosong }

Page 31: List Linier

31

DeklarasiDeklarasiLast : address Last : address { address untuk traversal} { address untuk traversal}

DeskripsiDeskripsiIfIf (First (L) = Nil) (First (L) = Nil) thenthen { insert sebagai { insert sebagai elemen pertama}elemen pertama}

InsertFirst(L, P)InsertFirst(L, P)ElseElse{ Traversal list sampai address terakhir}{ Traversal list sampai address terakhir}

Last ← First (L)Last ← First (L)WhileWhile (Next (Last ) ≠ Nil ) (Next (Last ) ≠ Nil ) dodo

Last ← Next (Last )Last ← Next (Last )endwhileendwhile {Next ( Last) = Nil, Last adalah {Next ( Last) = Nil, Last adalah

elemen terakhir; elemen terakhir; insert P after last } insert P after last }InsertAfter (P, Last)InsertAfter (P, Last)

endifendif

Page 32: List Linier

32

ProcedureProcedure InsertLast InsertLast((Input/output Input/output L :List, L :List, InputInput E : E : InfotypeInfotype))

{ K. Awal : List L mungkin kosong, P sudah dialokasi, { K. Awal : List L mungkin kosong, P sudah dialokasi, P ≠ Nil, Next(P)=Nil P ≠ Nil, Next(P)=Nil

K. Akhir : P adalah elemen terakhir list L K. Akhir : P adalah elemen terakhir list L Proses : Insert sebuah elemen beralamat P sebagai Proses : Insert sebuah elemen beralamat P sebagai

elemen terakhir dari list linier L elemen terakhir dari list linier L yang mungkin kosong }yang mungkin kosong }

DeklarasiDeklarasi Last : address Last : address { address untuk traversal }{ address untuk traversal }

DeskripsiDeskripsi Alokasi (P) Alokasi (P) If If (P ≠ Nil) (P ≠ Nil) then then

Info(P) ←EInfo(P) ←EInsertLast@(L,P) InsertLast@(L,P)

endifendif

Page 33: List Linier

33

IV.3. Penghapusan sebuah elemen IV.3. Penghapusan sebuah elemen pada list pada list linierlinier

Penghapusan harus dijabarkan lebih Penghapusan harus dijabarkan lebih rinci, Karena rinci, Karena penghapusan elemen penghapusan elemen dapat merupakan dapat merupakan pertama, setelah pertama, setelah sebuah address P atau sebuah address P atau penghapusan elemen terakhir. penghapusan elemen terakhir. Perbedaan ini Perbedaan ini melehirkan 3 operasi melehirkan 3 operasi dasar penghapusan dasar penghapusan elemen list yang elemen list yang diturunkan dari definisi diturunkan dari definisi fungsional fungsional inimenjadi realisasi algoritma.inimenjadi realisasi algoritma.

Operasi penghapusan dapat Operasi penghapusan dapat mengakibatkan list mengakibatkan list kosong, jika list kosong, jika list semula hanya terdiri dari satu semula hanya terdiri dari satu elemen.elemen.

Page 34: List Linier

34

IV.3.1. DELETFirst : menghapus elemen pertama IV.3.1. DELETFirst : menghapus elemen pertama list linierlist linier

a. Elemen yang dihapus dicatat alamatnyaa. Elemen yang dihapus dicatat alamatnyaProcedureProcedure DeleteFirst@ ( DeleteFirst@ (Input/OutputInput/Output L : List, L : List, OutputOutput

P : address)P : address){K. Awal : List L tidak kosong, minimal 1 elemen {K. Awal : List L tidak kosong, minimal 1 elemen

pertama pasti ada } pertama pasti ada }{K. Akhir : menghapus elemen pertama L{K. Akhir : menghapus elemen pertama L

P adalah @ elemen pertama L sebelum P adalah @ elemen pertama L sebelum penghapusan, L yang baru adalah Next penghapusan, L yang baru adalah Next

(L)(L)DeklarasiDeklarasiDeskripsiDeskripsi

P ← First (L) P ← First (L) First (L) ← Next( First (L)) First (L) ← Next( First (L)) Next(P) ← NilNext(P) ← Nil

Page 35: List Linier

35

ProcedureProcedure DeleteFirst ( DeleteFirst (Input/OutputInput/Output L : List, L : List, OutputOutput E : E : InfoType) InfoType)

{K. Awal : List L tidak kosong, minimal 1 {K. Awal : List L tidak kosong, minimal 1 elemen elemen pertama pasti ada } pertama pasti ada }

{K. Akhir : menghapus elemen pertama L{K. Akhir : menghapus elemen pertama L E adalah Nilai elemen pertama L E adalah Nilai elemen pertama L

sebelum sebelum penghapusan, L yang baru penghapusan, L yang baru adalah Next (L)adalah Next (L)

DeklarasiDeklarasiDeskripsiDeskripsi

P ← First (L) P ← First (L) E ← Info (P)E ← Info (P)First (L) ← Next ( First (L) ) First (L) ← Next ( First (L) ) Next(P) ← NilNext(P) ← NilDealokasi (P)Dealokasi (P)

Page 36: List Linier

36

IV. 3.2. Delete After :IV. 3.2. Delete After :Penghapusan suksesor sebuah elemen :Penghapusan suksesor sebuah elemen :Procedure Procedure DeleteAfter DeleteAfter ( ( InputInput Prec : adrress, Prec : adrress,

OutpuOutput t P : address )P : address ){ K. Awal : List { K. Awal : List tidak kosong,tidak kosong, Prec adalah elemen Prec adalah elemen

list , list , Next (Prec) ≠ Nil } Prec ≠elemen Next (Prec) ≠ Nil } Prec ≠elemen terakhirterakhir

K. Akhir : Menghapus suksesor Prec, P adalah @ K. Akhir : Menghapus suksesor Prec, P adalah @ suksesor Prec sebelum suksesor Prec sebelum

penghapusan, Next penghapusan, Next (Prec) yang baru adalah suksesor dari (Prec) yang baru adalah suksesor dari

suksesor Prec sebelum penghapusan }suksesor Prec sebelum penghapusan }DeklarasiDeklarasiDeskripsiDeskripsi P ← Next (Prec)P ← Next (Prec)

Next (Prec) ← Next (Next (Prec))Next (Prec) ← Next (Next (Prec)) Next(P) ← NilNext(P) ← Nil

Page 37: List Linier

37

Dengan primitip ini, maka penghapusan sebuah Dengan primitip ini, maka penghapusan sebuah beralamat P dapat dilakukan dengan : mencari beralamat P dapat dilakukan dengan : mencari predesesor dari P, yaitu alamat Prec memakai predesesor dari P, yaitu alamat Prec memakai DeleteAfter (Prec)DeleteAfter (Prec)

Procedure Procedure DeleteP DeleteP ( ( Input/OutputInput/Output L ; List, L ; List, OutputOutput P : P : address )address )

{ K. Awal : List L { K. Awal : List L tidak kosong , tidak kosong , P adalah P adalah elemen list L K. Akhir : Menghapus P dari list, elemen list L K. Akhir : Menghapus P dari list, P mungkin elemen P mungkin elemen pertama, “tengah” pertama, “tengah” atau terakhir }atau terakhir }

DeklarasiDeklarasi Prec : address { alamat predesesor } Prec : address { alamat predesesor }

DeskripsiDeskripsi

Page 38: List Linier

38

{ Cari predesesor P }{ Cari predesesor P } if if (P = First (L) (P = First (L) thenthen {Delete list {Delete list dengan satu dengan satu elemen } elemen } DeleteFirst (L,P)DeleteFirst (L,P) elseelse

Prec ← First (L) Prec ← First (L) WhileWhile (Next(Prec) ≠ P ) (Next(Prec) ≠ P ) dodo Prec ← Next (Prec)Prec ← Next (Prec)endwhileendwhile { Next (Prec) = P , { Next (Prec) = P ,

hapus P }hapus P } DeleteAfter (Prec , P)DeleteAfter (Prec , P)

endifendif

Page 39: List Linier

39

IV. 3.3. DELETELast :IV. 3.3. DELETELast :Menghapus elemen terakhir list dapat Menghapus elemen terakhir list dapat

dilakukan jika alamat dari elemen sebelum dilakukan jika alamat dari elemen sebelum elemen terakhir diketahui. Persoalan elemen terakhir diketahui. Persoalan selanjutnya menjadi persoalan DeleteAfter, selanjutnya menjadi persoalan DeleteAfter, kalau last bukan satu- satunya elemen list kalau last bukan satu- satunya elemen list linier. Ada dua kasus, yaitu list menjadi linier. Ada dua kasus, yaitu list menjadi kosong atau tidak.kosong atau tidak.

ProcedureProcedure DeleteLastDeleteLast ( (Input Input L L : List, : List, Output Output P : P : address) address)

{K. Awal : List L tidak kosong, minimal {K. Awal : List L tidak kosong, minimal mengandung 1 mengandung 1 elemen elemen

K. Akhir : menghapus elemen terakhir dari K. Akhir : menghapus elemen terakhir dari list, list list, list mungkin menjadi kosong mungkin menjadi kosong

Proses : P adalah alamat elemen terakhir Proses : P adalah alamat elemen terakhir list sebelum list sebelum penghapusan } penghapusan }

Page 40: List Linier

40

DeklarasiDeklarasi

Last , preclast :Last , preclast :addressaddress { address untuk { address untuk traversal }traversal }

DeskripsiDeskripsi{Find last dan address sebelum last }{Find last dan address sebelum last }

Last ← First (L) Last ← First (L) Preclast ← Nil Preclast ← Nil { predesesor dari L tak terdefenisi }{ predesesor dari L tak terdefenisi }While While ( Next( Last ) ≠ Nil) ( Next( Last ) ≠ Nil) do do { Traversal list sampai @ { Traversal list sampai @ terakhir }terakhir }

Preclast ← Last Preclast ← Last Last ← Next(last)Last ← Next(last)

endwhileendwhile {Next( Last )=Nil, Last adalah elemen terakhir; {Next( Last )=Nil, Last adalah elemen terakhir; preclast = preclast =

sebelum last } sebelum last } P ← LastP ← LastIfIf (Preclast = Nil) (Preclast = Nil) then then { list dg 1 elemen, jadi kosong { list dg 1 elemen, jadi kosong }}

First(L) ← Nil First(L) ← Nil Else Else

Next ( Preclast )← Nil Next ( Preclast )← Nil endifendif

Page 41: List Linier

41

IV. 5. Konkatenasi dua buah list linierIV. 5. Konkatenasi dua buah list linierConcat adalah menggabungkan dua list. Dalam Concat adalah menggabungkan dua list. Dalam

contoh berikut list kedua disambungkan ke list contoh berikut list kedua disambungkan ke list pertama. Jadi Last (L1) menjadi predesesor First pertama. Jadi Last (L1) menjadi predesesor First (L2). Realisasi algoritma adalah sebuah prosedur (L2). Realisasi algoritma adalah sebuah prosedur sebagai berikut : sebagai berikut :

Procedure Procedure CONCAT CONCAT ((Input Input L1, L2 : List, L1, L2 : List, Output Output : : L3 : List L3 : List ))

{K. awal : L1 ≠ L2, L1 ≠ L3,dan L3 ≠ L2; L1, L2 {K. awal : L1 ≠ L2, L1 ≠ L3,dan L3 ≠ L2; L1, L2 mungkin kosong mungkin kosong

K. Akhir : L3 adalah hasil konkatenasi K. Akhir : L3 adalah hasil konkatenasi (menyambung) (menyambung) dua buah list linier, L2 dua buah list linier, L2 ditaruh dibelakang L1 }ditaruh dibelakang L1 }

Page 42: List Linier

42

DeklarasiDeklarasiLast1 : Last1 : address address { alamat elemen terakhir list { alamat elemen terakhir list pertama }pertama }

DeskripsiDeskripsi Cratelist (L3) Cratelist (L3) {inisialisasi list {inisialisasi list

hasil }hasil } IfIf Fist (L1) = Nil Fist (L1) = Nil thenthen First (L3) ← First (L2)First (L3) ← First (L2) ElseElse { Traversal list 1 sampai address terakhir, { Traversal list 1 sampai address terakhir,

Hubungkan last dengan Fisrt 2}Hubungkan last dengan Fisrt 2}First (L3) ← First (L1)First (L3) ← First (L1)Last1 ← First (L1) Last1 ← First (L1) While While ( Next (Last 1 ) ≠ Nil ) ( Next (Last 1 ) ≠ Nil ) dodo

Last1 ← Next (Last 1) Last1 ← Next (Last 1) endwhileendwhile

Next(Last1) ← First (L2)}Next(Last1) ← First (L2)} endifendif

Page 43: List Linier

43

Soal-Soal LatihanSoal-Soal Latihan

I. I. Apakah perbedaan struktur data list Apakah perbedaan struktur data list linier ditinjau dari sudut pandang linier ditinjau dari sudut pandang operasinya, jika dibandingkan dengan operasinya, jika dibandingkan dengan struktur data record dan array?struktur data record dan array?

II. Diketahui sebuah list linier dengan II. Diketahui sebuah list linier dengan elemen bertipe integer, buatlah :elemen bertipe integer, buatlah :1. Sebuah prosedur untuk 1. Sebuah prosedur untuk menghitung jumlah menghitung jumlah

elemen list yang genapelemen list yang genap2. Prosedur untuk menghitung rata-2. Prosedur untuk menghitung rata-rata rata elemen list yang ganjil elemen list yang ganjil

Page 44: List Linier

44

3. Prosedur untuk menghitung banyaknya 3. Prosedur untuk menghitung banyaknya elemen list yang positif (lebih besar dari elemen list yang positif (lebih besar dari nol)nol)4. Prosedur untuk mencetak elemen list yang 4. Prosedur untuk mencetak elemen list yang genapgenap5. Prosedur untuk mengubah dari satu list 5. Prosedur untuk mengubah dari satu list menjadi 2 buah list yang terdiri dari list menjadi 2 buah list yang terdiri dari list

dengan elemen genap dan list dengan elemen dengan elemen genap dan list dengan elemen ganjilganjilIII. Diketahui sebuah list dengan elemen bertype III. Diketahui sebuah list dengan elemen bertype integer terurut membesar, buatlah :integer terurut membesar, buatlah :

1. Fungsi untuk mengirimkan elemen pertama list1. Fungsi untuk mengirimkan elemen pertama list2. Fungsi untuk mencari elemen list yang minimum2. Fungsi untuk mencari elemen list yang minimum3. Fungsi untuk menghitung banyaknya elemen 3. Fungsi untuk menghitung banyaknya elemen yang yang

lebih besar dari 100lebih besar dari 100