ADT Dinamis : Singly Linked List & Soubly Linked List

Konsep Dasar List (Senarai)

3

Konsep Dasar List (Senarai)

° Dari konsepnya, list dapat didefinisikan sebagai urutan

dinamis (dynamic ordering) dari :

L = (l1, l2, ….., ln)

Di mana l1 adalah elemen yang ke-i pada List.

Penggunaan kata dinamis memberi tekanan bahwa elemen-elemen dalam List nilainya dan jumlahnya dapat berubah-ubah.

4

Konsep Dasar List (Senarai)

L = (l1, l2, ….., ln)

• Elemen yang pertama pada list disebut head List

• Elemen yang terakhir dirujuk sebagai ekor (tail) List

• Jumlah elemen ditulis sebagai | L | yang juga dirujuk sebagai

panjang list

• Maka list kosong direpresentasikan sebagai (), memiliki panjang

().

• Sehingga list di atas memiliki |L| = n

• Jika semua elemen bertipa sama homogen, berbeda

heterogen

5

Konsep Dasar List (Senarai)

L = ((3), (4, 2, 5), (12, 7, (8, 4), 1), 0)

• ADT List di atas memiliki 4 elemen

• Elemen 1 : bilangan bulat bernilai 3

• Elemen 2 : list dengan elemen bilangan bulat (4,2,5)

• Elemen 3 : bilangan bulat 12,7, list (8,4), dan 0

• Elemen 4 : 0

6

Struktur Alokasi Memori Komputer RAM

Memori Tersisa

Heap yang bergerak naik ke memori

Memori yang ditempati data (DataSegment)

Memori yang ditempati program (CodeSegment)

Memori untuk program residen

Sistem Operasi

Free Ptr

HeapPtr

HeapOrg

Dseg

CSeg

• Heap : bagian memori

yang belum dialokasikan

atau belum digunakan oleh

sistem operasi

• Program residen : berisi

program-program residen

(program yang menetap

dalam memori misal

antivirus, driver, mouse,

dsb)Umumnya, List akan disimpan dalam bagian memori sebagai Heap

7

Terapan List

° Ada berbagai terapan List, di antaranya : • Singly-Linked List

- List berkait tunggal

• Doubly-Linked List- List berkait ganda

° Beberapa fungsi dalam terapan List : • Insert() / add()• Remove()

8

Singly-Linked List

9

Permasalahan penerapan linked-list pada Java

° Seperti telah diketahui, ADT berbasis node menyimpan

data dalam bentuk simpul (node) pada suatu List

° Kita dapat membayangkan :

• Node adalah elemen yang memiliki satu atau lebih

pointer

• Pointer digunakan untuk menunjukkan ke elemen

lainnya

° Masalah : Java tidak mengenal terminologi pointer

10

Solusi

° Karena tidak mengenal pointer perlakukan objek

sebagai pointer

° Sehingga di Java, struktur node memiliki elemen data

yang merujuk ke node lain

° 2 macam node :

• Parent node

• Child node

11

Class Java untuk Struktur Data Singly-Linked List

° Untuk implementasi Singly-Linked List, setidaknya kita

perlu 2 struktur class :

• Class untuk satu child-node

- Dlm matkul ini diberi nama : onenodeoneptr

• Class untuk menghubungkan tiap child node

- Dlm matkul ini diberi nama : linkedonenodeondeptr

12

Metoda pada class onenodeoneptr

° Berisi metode-metode get dan set terhadap nilai-nilai pada node

° Nilai yang ada pada node yaitu : • Data

- Metoda untuk set : setDatanode() - Metoda untuk get : getDatanode()

• 1 Pointer ke node lain- Metoda untuk set : setPointerkenodeberikut()- Metoda untuk get : getPointerkenodeberikut()

13

Variabel pada onenodeoneptr

14

Konstruktor onenodeoneptr

15

Metoda set pada onenodeoneptr

16

Metoda get pada onenodeoneptr

17

Mengubah nilai data ke bentuk String pada onenodeoneptr

18

Metoda pada class linkedonenodeoneptr

° Mengecek node kosong ato tidak apaKosong()

° Menentukan banyaknya node banyaknyaNode()

° Menambah node baru di awal tambahdiawal()

° Menghapus node di awal hapusdiawal()

° Menambah node di akhir tambahdiakhir()

° Menghapus node di akhir hapusdiakhir()

° Ambil nilai di node ambilNilai()

19

Variable pada linkedonenodeoneptr

20

Konstruktor pada linkedonenodeoneptr

21

apaKosong() & banyaknyaNode()

22

tambahdiawal()

23

hapusdiawal()

24

tambahdiakhir()

25

hapusdiakhir()

26

ambilNilai()

27

Pengujian linkedonenodeoneptr (1)

28

Pengujian linkedonenodeoneptr (1)

29

Doubly-Linked List

MINGGU DEPAN