Fondasi · Pelajaran 3 dari 10
Linked list
10 menit baca · BelajarCode
Linked list terdiri dari simpul (node). Setiap simpul menyimpan sebuah nilai dan referensi ke simpul berikutnya. Simpul-simpul tidak harus berdampingan di memori.
1class Simpul:2 def __init__(self, nilai, berikut=None):3 self.nilai = nilai4 self.berikut = berikut567class LinkedList:8 def __init__(self):9 self.kepala = None10 self.panjang = 01112 def tambah_depan(self, nilai):13 self.kepala = Simpul(nilai, self.kepala)14 self.panjang += 11516 def tambah_belakang(self, nilai):17 baru = Simpul(nilai)18 if self.kepala is None:19 self.kepala = baru20 else:21 sekarang = self.kepala22 while sekarang.berikut is not None:23 sekarang = sekarang.berikut24 sekarang.berikut = baru25 self.panjang += 12627 def cari(self, nilai):28 sekarang = self.kepala29 posisi = 030 while sekarang is not None:31 if sekarang.nilai == nilai:32 return posisi33 sekarang = sekarang.berikut34 posisi += 135 return -13637 def hapus(self, nilai):38 if self.kepala is None:39 return False40 if self.kepala.nilai == nilai:41 self.kepala = self.kepala.berikut42 self.panjang -= 143 return True44 sekarang = self.kepala45 while sekarang.berikut is not None:46 if sekarang.berikut.nilai == nilai:47 sekarang.berikut = sekarang.berikut.berikut48 self.panjang -= 149 return True50 sekarang = sekarang.berikut51 return False5253 def __str__(self):54 bagian = []55 sekarang = self.kepala56 while sekarang is not None:57 bagian.append(str(sekarang.nilai))58 sekarang = sekarang.berikut59 return " -> ".join(bagian) + " -> None"606162daftar = LinkedList()63for x in [20, 30, 40]:64 daftar.tambah_belakang(x)65daftar.tambah_depan(10)66print(daftar, "| panjang", daftar.panjang)67print("Posisi 30:", daftar.cari(30))68daftar.hapus(30)69daftar.hapus(10)70print(daftar, "| panjang", daftar.panjang)10 -> 20 -> 30 -> 40 -> None | panjang 4 Posisi 30: 2 20 -> 40 -> None | panjang 2
Kelebihan dan kekurangan
| Operasi | Array dinamis | Linked list |
|---|---|---|
| Akses elemen ke-i | O(1) | O(n), harus berjalan dari kepala |
| Tambah di depan | O(n), semua digeser | O(1) |
| Tambah di belakang | O(1) teramortisasi | O(n), atau O(1) jika menyimpan ekor |
| Hapus simpul yang sudah ditemukan | O(n) karena menggeser | O(1), cukup memindah referensi |
| Memori tambahan | Kapasitas cadangan | Satu referensi per simpul |
Dalam praktik, array dinamis sering lebih cepat karena datanya berdampingan di memori dan ramah cache prosesor. Linked list unggul ketika banyak penambahan dan penghapusan di tengah pada posisi yang sudah diketahui.
Linked list ganda
Doubly linked list menyimpan referensi ke simpul sebelumnya dan sesudahnya. Struktur ini memudahkan penelusuran mundur dan penghapusan simpul tanpa harus mencari pendahulunya. collections.deque di Python dibangun dengan prinsip serupa.
Cek pemahaman
Kenapa menambah di depan linked list selalu O(1)?
Latihan
Membalik linked list
Tulis fungsi balik(daftar) yang membalik urutan simpul linked list di tempat, dengan mengubah arah referensi. Uji dengan list 1 -> 2 -> 3 -> 4.
Pembahasan
1class Simpul:2 def __init__(self, nilai, berikut=None):3 self.nilai = nilai4 self.berikut = berikut567def tampilkan(kepala):8 bagian = []9 while kepala is not None:10 bagian.append(str(kepala.nilai))11 kepala = kepala.berikut12 return " -> ".join(bagian)131415def balik(kepala):16 sebelum = None17 sekarang = kepala18 while sekarang is not None:19 berikut = sekarang.berikut20 sekarang.berikut = sebelum21 sebelum = sekarang22 sekarang = berikut23 return sebelum242526kepala = Simpul(1, Simpul(2, Simpul(3, Simpul(4))))27print(tampilkan(kepala))28kepala = balik(kepala)29print(tampilkan(kepala))1 -> 2 -> 3 -> 4 4 -> 3 -> 2 -> 1
Tiga referensi (sebelum, sekarang, berikut) bergerak maju bersama. Setiap simpul dibalik arahnya satu kali, jadi O(n) waktu dan O(1) memori tambahan.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.