Misalkan kita mempunyai sebuah class dasar berisi field data tunggal:
```python
class ListNode:
def __init__(self, data):
self.data = data
```
Kta dapat membuat beberapa instance dari class ini dan menyimpan suatu nilai integer tertentu ke masing-masing instance:
```python=
a = ListNode(11)
b = ListNode(52)
c = ListNode(18)
```
Hasil dari pembuatan tiga variabel di atas diilustrasikan pada gambar berikut:
Sekarang, misalkan kita menambahkan field data kedua pada class `ListNode`:
```python
class ListNode:
def __init__(self, data):
self.data = data
self.next = None
```
Tiga object dari contoh sebelumnya sekarang mempunyai field data kedua yang diinisialisasi dengan referensi null. Ini diilustrasikan pada gambar berikut:
Karena field `next` dapat berisi sebuah rerferensi ke object tipe apapun, kita dapat menugaskannya dengan sebuah referensi ke object `ListNode` yang lain. Sebagai contoh, misalkan kita menugaskan `b` ke field `next` dari object `a`:
```
a.next = b
```
yang menghasilkan terhubungnya object `a` ke object `b`, seperti ditunjukkan gambar berikut:
Dan selanjutnya kita dapat menghubungkan object `b` ke `c`:
```
b.next = c
```
Penghubungan object `a` ke object `b` dan object `b` ke object `c` menghasilkan rantai dari object-object seperti diilustrasikan gambar berikut:
Kita dapat menghilangkan referensi ekternal `b` dan `c` dengan menugaskan `None` ke masing-masing:
```
b = None
c = None
```
Ini akan menghasilkan rantai object-object seperti ditunjukkan gambar berikut:
Hasil ini adalah struktur linked list. Dua object yang sebelumnya ditunjuk oleh `b` dan `c` tetap dapat diakses melalui `a`. Sebagai contoh, misalkan kita ingin mencetak nilai-nilai dari ketiga object tersebut. Kita dapat mengakses dua object lainnya melalui field `next` dari object pertama:
```
print(a.data)
print(a.next.data)
print(a.next.next.data)
```
## Singly Linked List
Singly linked list adalah linked list yang setiap nodenya berisi field link tunggal dan memungkinkan pelintasan dari node pertama sampai dengan node terakhir.
Terdapat sejumlah operasi-operasi yang umumnya dilakukan terhadap singly linked list, yang akan kita bahas pada bagian ini. Untuk mengilustrasikan implementasi dari operasi-operasi ini kode kita mengasumsikan adanya sebuah referensi head dan menggunakan class `ListNode` dari pembahasan sebelumnya. Field data dari class `ListNode` akan diakses secara langsung oleh class yang mengimplementasi linked list.
### Mengunjungi Setiap Node (Traversing)
Pada contoh sebelumnya, kita mengakses node kedua dan node ketiga dari contoh list kita dengan menggunakan notasi dot ke variabel referensi `a`. Ini mungkin cukup untuk list dengan sedikit node, tetapi teknik ini tidak praktis untuk list yang besar. Oleh karena itu, kita menggunakan referensi eksternal temporer untuk melintasi list dengan menggerakkan referensi ke setiap node dimulai dari node pertama.
Seperti halnya pada array ataupun list, proses traversing sangat umum dilakukan terhadap linked list. Proses traversing mengunjugi semua node dari linked list satu per satu dimulai dari node head sampai dengan node tail.
Proses mulai dengan menugaskan referensi eksternal `curNode` untuk menuding node pertama dari list, seperti diilustrasikan oleh gambar berikut:
Setelah memasuki loop, nilai yang disimpan dalam node pertama dicetak dengan mengakses field data dari node tersebut melalui referensi ekternal. Setelah selesai, referensi eksternal dimajukan ke node berikutnya dengan menugaskan referensi eksternal ke nilai dari field next dari node yang saat ini diakses. Iterasi loop berlanjut ke setiap node dalam list sampai semua node dilintasi. Proses traversal berhenti ketika `curNode` menuding `None`.
Implementasi dari traversal linked list harus menyertakan kondisi dimana list kosong. Namun karena list kosong tidak mempunyai satupun node sehingga `curNode` akan menunjuk ke `None` sebelum loop mulai dan menyebabkan loop tidak dieksekusi, maka algoritma di atas sudah menyertakan kondisi list kosong ini.
Berikut adalah kode dari proses traversal linked list:
```python
curNode = head
while curNode is not None:
print curNode.data
curNode = curNode.next
```
### Mencari Sebuah Node
Pencarian linear dapat dilakukan pada linked list. Implementasi pencarian sebuah node mirip dengan operasi traversal. Perbedaan satu-satunya adalah kondisi dari loop berhenti ketika node yang dicari ditemukan.
```python
def unorderedSearch(head, target):
curNode = head
while curNode is not None and curNode.data != target:
curNode = curNode.next
return curNode is not None
```
Perhatikan urutan dua kondisi dalam loop `while`. Penting untuk kita menguji apakah `curNode` menunjuk ke `None` sebelum menguji isi dari node. Jika node yang dicari tidak ditemukan, `curNode` akan menunjuk ke `None` (null) ketika akhir dari list dicapai. Jika kita mencoba mengeveluasi field `data` dari referensi null, sebuah eksepsi akan di-raise, yang menyebabkan error run-time.
Implementasi dari operasi pencarian linked list juga harus menyertakan kondisi
### Menghapus Node
Data dari linked list dapat dihapus dengan memutus *link* dari node yang menyimpan data tersebut. Misalkan kita mempunyai linked list seperti pada gambar berikut:
Kita ingin menghapus node yagn berisi data 18. Kita dapat melakukannya dengan langkah-langkah berikut:
1. Lakukan pencarian ke node yang berisi data dan posisikan sebuah variabel referensi eksternal untuk menunjuk ke node tersebut.
2. Setelah menemukan node yang dicari, node tersebut harus diputus. Kita dapat memutus node tersebut dengan dua langkah:
a. mengatur field link dari node sebelum node yang ingin diputus ke node setelah node yang ingin diputus.
b. mengnull-kan field link dari node yang diputus dengan menugaskannya ke `None`
#### Kasus Menghapus Node Pertama
Kita juga harus memperhatikan kasus khusus ketika data yang dihapus berada di node pertama. Pada kasus penghapusan node pertama, tidak ada node sebelumnya yang harus disambung ulang, namun referensi head harus diubah untuk menunjuk ke node berikutnya. Ini diilustrasikan oleh gambar berikut:
#### Kode untuk Menghapus Node
Di dalam kode yang menghapus node dari singly linked list. Referensi ekternal `curNode` diinisilasisasi ke node pertama dalam list, sama speerti yang kita lakukan pada operasi traversal dan pencarian. Referensi eksternal `prevNode` kita inisialisasi ke `None` karena tidak ada node sebelum node pertama.
```python
curNode = head
prevNode = None
```
Loop digunakan untuk menggerakkan `curNode` melintasi ke setiap node sampai dengan node yang ingin dihapus ditemukan atau `curNode` mencapai node terakhir. Untuk melakukan ini, kita dapat menggunakan loop `while` dengan kondisi `curNode` tidak `None` dan field data dari `curNode` tidak sama dengan data yang ingin dihapus. Data yang tidak ingin dihapus kita namakan `target`.
Saat referensi `curNOde` bergerak ke setiap list, referensi `prevNode` berada di satu node sebelum `curNode`.
```python
while curNode is not None and curNode.data != target:
```
***Menghapus Node dari List***
```python=
def hapus(self, data):
prevNode = None
curNode = self._head
# Cari data dengan melintasi node dari node pertama
# curNOde menunjuk ke node yang sedang dilintasi dan
# prevNode menunjuk ke node sebelum node yang sedang dilintasi
while curNode is not None and curNode.data != target:
prevNode = curNode
curNode = curNode.next
# Jika data ditemukan
if curNode is not None:
# Jika data yang ditemukan berada di head
# Pindahkan refernsi head ke node berikutnya (node kedua)
if curNode is head:
head = curNode.next
else:
prevNode.next = curNode.next
```
## df
Linked list adalah struktur yang bersifat generik. Linked list dapat digunakan untuk mengimplementasikan ADT-ADT. Kita akan membahas penggunaan linked list untuk mengimplementasikan ADT Bag yang sebelumnya diimplementasikan menggunakan list.
Untuk mengilustrasikan penggunaan ADT Stack yang akan kita buat, kita akan menerpakannya untuk menyeleasikan permasalahn membalik urutan nilai-nilai integer dari suatu daftar nilai-nilai integer. Nilai-nilai integer ini kita dapatkan dari input pengguna sampai dengan nilai negatif dimasukkan, yang menandakan akhir dari input. Nilai-nilai tersebut kemudian dicetak dalam urutan terbalik dari urutan yang diinput pengguna. Kita dapat saja menggunakan list untuk menyelesaikan persoalan ini, namun stack lebih ideal karena nilai-nilai dapat di-push ke stack saat nilai tersebut di-input pengguna dan di-pop satu per satu untuk dicetak dalam urutan terbalik.
Kode berikut adalah solusi dari persoalan ini:
```python
PROMPT = "Masukkan nilai integer (nilai negatif untuk mengakhiri): "
myStack = Stack()
nilai = int(input(PROMPT))
while nilai >= 0:
myStack.push(nilai)
nilai = int(input(PROMPT))
while not myStack.isEmpty():
nilai = myStack.pop()
print(nilai)
```
Misalkan pengguna memasukkan nilai-nilai berikut, satu persatu:
```
7 13 45 19 28 -1
```
Ketika loop `while` yang meminta input pengguna berakhir, isi dari stack akan seperti pada gamabr berikut:
Perhatikan nilai terakhir berada pada bagian paling atas (top) dan nilai yang pertama dimasukkan berada di bagian paling bawah (base). Jika kita meng-pop nilai-nilai dari stack, nilai-nilai tersebut akan dihapus dalam urutan terbalik dari urutan pertama kali nilai tersebut di-push ke stack, sehingga menghasilkan urutan terbalik.
#### Method `__str__`
Implementasi method `__str__` yang mengembalikan string ketika object `LinkedList` di-print adalah sebagai berikut:
```python
def __str__(self):
strHasil = ''
curNode = self._head
while curNode is not None:
strHasil += f'{curNode.data}'
if curNode.next is not None:
strHasil += ' -> '
curNode = curNode.next
return strHasil
```
Tabel berikut mencontohkan penggunaan operasi-operasi ADT Array:
// tulis ulang tabel
| Operasi | Keterangan |
|--------- |------------|
| `arr = Array(5)` | Membuat array dengan ukuran lima elemen dan menugaskan referensi array tersebut ke variabel `arr` |
| `len(arr)` | Mengembalikan panjang array yang direferensikan `arr` |
| `arr[2]` | Mengembalikan nilai elemen dengan indeks 2 |
| `arr[3] = 11` | Menetapkan nilai elemen indeks 3 dengan nilai 11 |
| `array.clear(10)` | Membersihkan elemen-elemen array `arr` dengan menetapkan setiap nilai elemennya dengan 10.
| `for elm in arr:`| Meng-traverse atau mengiterasi setiap elemen dalam array `arr` |
<!--
Pondasi dari ilmu komputer didasarkan pada studi algortima. Algoritma adalah urutan instruksi langkah per langkah yang jelas dan presisi untuk menyelesaikan sebuah persoalan dalam waktu yang terbatas. Algoritma diimplementasikan dengan menerjemahkan instruksi langkah per langkah ke program komputer yang dapat dieksekusi oleh komputer. Proses menerjemahan ini disebut dengan pemrograman komputer atau singkatnya pemrograman. Program kopmuter dikonstruksi menggunakan bahasa pemrograman yang pantas untuk persoalan. Walaupun pemrograman adalah bagian penting dari ilmu komputer, ilmu komputer bukanlah ilmu yang mempelajari pemrograman. Ilmu kopmuter juga bukan mengenai mempelajari bahasa pemrograman tertentu. Namun, pemrograman dan bahasa pemrograman adalah alat yang digunakan oleh ilmuwan komuter untuk memecahkan persoalan.
-->
### Tipe Data
Data direpresentasikan dalam komputer sebagai barisan digit-digit biner. Barisan-barisan digit biner ini dapat terlihat sama namun mempunyai arti berbeda karena komputer dapat menyimpan dan memanipulasi tipe-tipe data berbeda. Sebagai contoh, barisan biner `0100110011001011010111011011100` dapat berarti sebuah string karakter, bilangan bulat, atau bilangan riil. Tipe data yang kita tentukan dalam program yang memberitahukan komputer bagaimana menerjemahkan barisan biner tersebut.
Bahasa pemrograman umumnya menyediakan sejumlah tipe-tipe data sebagai bagian dari bahasa itu sendiri. Tipe-tipe data ini disebut sebagai tipe-tipe data primitif. Tipe data primitif umumnya dibagi menjadi dua kategori: sederhana dan kompleks. Tipe data sederhana terdiri dari nilai-nilai dalam bentuk paling dasar dan tidak dapat dipecah menjadi bagian-bagian yang lebih kecil. Tipe integer dan tipe riil adalah contoh dari tipe data sederhana. Tipe data kompleks dikonstruksi dari lebih dari satu tipe data sederhana atau tipe data kompleks lainnya. Dalam Python, object, string, list, dan dictionary, yang dapat berisi lebih dari satu nilai, adalah contoh dari tipe data kompleks. Tipe primitif yang disediakan oleh bahasa pemrograman tidak cukup untuk menyelesaikan persoalan besar yang kompleks. Sehingga, sebagian besar bahasa pemrograman memungkinkan untuk mengkonstruksi tipe-tipe data tambahan, yang disebut sebagai **tipe data user-defined** (didefinisikan pengguna). Disebut dengan tipe data user-defined karena tipe-tipe data ini didefinisikan oleh programmer dan bukan oleh bahasa itu sendiri.
Gambar berikut mengilustrasikan pengklasifikasian tipe-tipe data dalam Python:
// ganti gambar
Tabel berikut mencontohkan penggunaan operasi-operasi pada ADT Bag:
| Operasi | Contoh Statement | Keterangan |
|---------|------------------|------------|
| `Bag()` | `myBag = Bag()` | Membuat instance Bag kosong. |
| `add(nilai)` | `myBag.add(23)` | Menambahkan nilai 23 ke bag. |
| `remove(nilai)` | `myBag.remove(45)` | Menghapus nilai 45 dari bag. |
| `1en()` | `len(myBag)` | Mendapatkan banyaknya nilai-nilai yang terdapat dalam bag. |
| `contains(nilai)` | `nilai in myBag` | Mencari `nilai` dalam bag. |
| `iterator` | `for nilai in myBag:` | Mengiterasi nilai-nilai dalam bag.
```python
from array2d import Array2D
# Implementasi ADT Matriks
class Matriks:
# ... Implementasi Method-method
Sign in with Wallet
Connect another wallet