Algoritma dan Pemrograman 2C

Linear List

      Suatu struktur yang merupakan terurut dari satuan data atau dari record

      Elemen yang terdapat dalam daftar disebut simbol/node

      Daftar disebut linear karena elemen nampak seperti baris, bahwa setiap simpul/ (kecuali simpul pertama dan terakhir) selalu memiliki elemen penerus langsung (suksesor) dan elemen pendahuluan langsung (predesor)

A = [a1,a2….aT]

Jika T=0, maka A

Dikatakan sebagai

“null list” (list hampa)

      Suatu elemen dapat dihapus (delete) dari sembarang posisi pada linear list

      Suatu elemen baru dapat dimasukkan (insertion) kedalam list dan dapat menepati sembarang posisi pada list tersebut

      Dapat berkurang atau bertambah setiap saat

      Contoh : file merupakan linear list yang elemen-elemennya berupa record

Stack

v  Bentuk khusus dari linier list

v  Operasi penyisipan dan penghapusan atas elemen-elemennya hanya dapat dilakukan pada satu sisi saja yaitu posisi akhir dari list, disebut puncak atau disebut sebagai “TOPS(S)”

v  Prinsip lifo (last in first out ) atau terakhir masuk pertama keluar

v  Setiap elemen tidak dapat dikeluarkan (POP) sebelum semua elemen diatasnya dikeluarkan

v  Misalnya diberikan stack S sebagai berikut

S = [s1,s2……sT] → maka Top(S) = sT

·         Untuk menunjukkan jumlah elemen suatu stack digunakan notasi NOEL(S)

Dari stack maka NOEL(S) = T

NOEL(S) menghasilkan nilai integer

Operasi pada stack

1. Create (stack)

2. Isempty (stack)

3. Push (elemen,stack)

4. POP

1.Create(S)

     Operator yang berfungsi untuk membuat sebuah stack kosong (hampa)

     Noel (create(S)) = 0 dan

     TOP (create (S)) = null/tidak terdefinisi

2. Isempty(S)

     Operator yang berfungsi untuk menentukan apakah suatu stack adalah stack kosong(hampa) atau tidak operasinya akan bernilai boolean

     Isempty(S) = true, jika S adalah stack

     Kosong atau noel(S) ≠ 0

     Catatan : isempty(create(S)) = true

3. Push(E,S)

•          Berfungsi untuk menambahkan suatu elemen kedalam stack notasi push (e,s). Artinya : menambahkan elemen E kedalam stack S

•          Elemen yang baru masuk ini akan menempati posisi top, jadi  top (push(E,S)) = E
•          Akibat dari operasi ini sejumlah elemen dalam stack akan bertambah artinya NOEL(S)

Menjadi lebih besar atau stack menjadi tidak kosong (Isempty(push(E,S))= false)

4.POP(S)

§  Operator ini berfungsi untuk mengeluarkan satu elemen dari dalam stack, notasinya POP(S)

§  Elemen yang keluar dari dalam stack adalah elemen yang berada pada posisi top

§  Akibat dari operasi ini jumlah elemen stack akan berkurang atau NOEL(S) berkurang 1 dan elemen pada posisi top akan bertambah

§  Operator ini tidak dapat digunakan pada stack kosong,artinya :

  POP(create(S)) = error condition dan

  POP(push(b,s)) = s

  Catatan : TOP(push(E,S)) = E

Sumber : catatan Kuliah