Rangkuman buku Python Data Structures and Algorithms chapter 4
Lists and Pointer Structures
- memahami pointer dengan python
- memperlakukan konsep node
- menerapkan daftar tertaut tunggal, ganda, dan melingkar.
Anda pasti pernah melihat daftarnya dengan Python. Implementasi daftar
Python dirancang agar kuat dan untuk mencakup
beberapa kasus penggunaan yang berbeda. Konsep node sangat penting untuk dimasukkan. Kita akan membahas ini dalam bab ini, tetapi konsep ini akan muncul kembali dalam bentuk yang berbeda untuk sisa buku ini.
Dalam bab ini, kita akan berbicara sedikit tentang nasihat. Karena kekurangan waktu, Anda menghubungi agen dan menemukan kandidat. Jadi Anda mengambil rumah Anda dan membawanya ke penjual, yang mengambil alih rumah itu kepada siapa saja yang ingin membelinya. Sekarang bayangkan Anda memiliki beberapa fungsi Python yang bekerja dengan gambar.
Jadi Anda melewatkan data gambar resolusi tinggi
di antara fungsi Anda. Yang Anda
lakukan adalah menuliskan alamat rumah Anda pada sepotong besi tua dan memberikannya kepada agen. Ternyata, tidak ada bedanya di tanah Python. File gambar besar tetap berada di
satu tempat di memori.
Apa yang Anda lakukan adalah membuat variabel
yang menyimpan lokasi gambar-gambar ini dalam memori. Variabel ini kecil dan dapat dengan mudah dibagi di antara fungsi yang berbeda.
Hal ini membuat beberapa orang percaya bahwa pointer tidak digunakan dalam Python.
ARRAY
STRUKTUR PENUNJUK
Berlawanan dengan array, struktur penunjuk
adalah daftar item yang dapat disebarkan di memori. Ini karena setiap item
berisi satu atau lebih tautan ke item lain dalam struktur. Jika kita
berurusan dengan daftar tertaut, maka kita akan memiliki tautan ke item
berikutnya dalam struktur. Ada beberapa keuntungan dengan struktur
penunjuk.
Jika Anda memiliki daftar bilangan bulat, setiap
simpul akan menggunakan ruang dari bilangan bulat, serta bilangan bulat
tambahan untuk menyimpan penunjuk ke simpul berikutnya.
NODE
>>> a = "eggs"
>>> b = "ham"
Sekarang Anda memiliki tiga variabel,
masing-masing dengan nama unik, tipe, dan nilai. Apa yang tidak kita
miliki adalah cara untuk mengatakan dengan cara apa variabel-variabel tersebut
berhubungan satu sama lain. Node memungkinkan kita melakukan
ini. Node adalah wadah data, bersama dengan satu atau lebih tautan ke node
lain. Sebuah link ada;ah sebuah pointer.
Jenis node yang sederhana adalah node yang hanya
memiliki link ke node berikutnya.
String itu tidak benar-benar disimpan di node,
tetapi lebih merupakan penunjuk ke
string yang sebenarnya :
Jadi
kebutuhan penyimpanan untuk node sederhana ini adalah dua alamat memori. Data
atribut node adalah pointer ke string egg dan ham.
MENEMUKAN TITIK AKHIR
Kami telah membuat tiga node: satu berisi
telur, satu ham, dan satu lagi spam. Node telur menunjuk ke simpul ham,
yang pada gilirannya menunjuk ke simpul spam. Tapi apa yang ditunjuk oleh
node spam? Karena ini adalah elemen terakhir dalam daftar, kita perlu
memastikan anggota berikutnya memiliki nilai yang menjelaskan hal ini.
Jika
kita membuat elemen terakhir tidak menunjukkan apa-apa maka kita membuat fakta
ini jelas. Dengan python, kami akan melakukannya gunakan nilai khusus tidak ada
untuk tidak menunjukkan apa-apa:
Node
terakhir memiliki titik berikutnya yang mengarah ke tidak ada. Karena itu, ini
adalah simpul terakhir dalam rantai node.
NODE
Berikut
ini adalah implementasi node sederhana dari apa yang telas kita bahas sejauh
ini:
class
Node:
def
__init__(self, data=None):
self.data
= data
self.next
= None
Penunjuk
berikutnya diinisialisasi ke tidak ada, artinya kecuali anda mengubah nilai
next, node akan menjadi titik terakhir. Ini ide yang bagus, agar kita tidak
lupa akhiri daftar dengan benar. Anda dapat menambahkan hal-hal lain ke kelas
node sesuai keinginan anda. Pastikan anda tetap bergabung perhatikan perbedaan
antara node dan data. Jika node anda akan berisi data pelanggan, kemudian buat
kelas pelanggan dan letakkan semua data di sana.
Satu
hal yang mungkin anda lakukan adalah mengimplementasikan metode _str_ sehingga
memanggil metode _str_ dari objek yang terkandung di panggil ketika objek node
dilewatkan untuk di cetak:
def __str__(self):
return str(data)
JENIS NODE LAINNYA
Kami
mengasumsikan node yang memiliki pointer ke berikutnya. Ini mungkin jenis node
yang paling sederhana. Namun, tergantung pada kebutuhan kami, kami dapat
membuat beberapa jenis node lainnya.
Terkadang
kita ingin pergi dari A ke B, tetapi pada saat yang sama dari B ke A. dalam hal
itu, kita tambahkan penunjuk sebelumnya selain penunjuk berikutnya:
Seperti yang anda lihat dari gambar, kami membiarkan Seperti yang Anda lihat dari gambar, kami membiarkan node terakhir dan pertama menunjuk ke None, untuk Menunjukkan bahwa kami telah mencapai mereka membentuk batas titik akhir daftar kami. Node pertama penunjuk sebelumnya menunjuk ke Tidak ada karena tidak memiliki pendahulu, sama seperti item terakhir berikutnya pointer menunjuk ke None karena tidak ada node penerus.
Anda mungkin juga membuat ubin untuk game berbasis ubin. Dalam kasus seperti itu, bukan sebelumnya dan selanjutnya, Anda bisa menggunakan utara, selatan, timur, dan barat. Ada lebih banyak jenis penunjuk, tapi prinsipnya sama. Ubin di ujung peta akan mengarah ke Tidak Ada:
Anda
dapat melakukan ini sejauh yang anda butuhkan. Jika anda ingin bisa bergerak ke
barat laut, timur laut, tenggara, dan barat daya, yang harus anda lakukan
adalah menambahkan penunjuk ini ke kelas node anda.
DAFTAR TUNGGAL YANG DITAUTKAN
Daftar tertaut tunggal adalah daftar dengan hanya satu penunjuk di antara dua node yang berurutan. Ini hanya dapat dilalui dalam satu arah, yaitu, Anda dapat beralih dari node pertama dalam daftar ke node terakhir. node, tetapi Anda tidak dapat berpindah dari node terakhir ke node pertama.
Kita sebenarnya dapat menggunakan kelas node yang kita buat sebelumnya untuk mengimplementasikan secara tunggal yang sangat sederhana daftar tertaut:
>>> n1 = Node('eggs')
>>> n2 = Node('ham')
>>> n3 = Node('spam')
Selanjutnya kami menghubungkan node bersama sehingga mereka membentuk rantai:
>>> n1.next = n2
>>> n2.next = n3
Untuk melintasi daftar tersebut, Anda dapat melakukan sesuatu seperti berikut ini. Kita mulai dengan mengatur arus variabel ke item pertama dalam daftar:
current = n1
while current:
print(current.data)
current = current.next
Dalam loop kami mencetak elemen saat ini setelah kami mengatur arus untuk menunjuk ke berikutnya
elemen dalam daftar. Kami terus melakukan ini hingga kami mencapai akhir daftar.
Namun, ada beberapa masalah dengan penerapan daftar yang sederhana ini :
- Ini membutuhkan terlalu banyak pekerjaan manual oleh programmer
- itu terlalu rawan kesalahan (ini adalah konsekuensi dari poin pertama)
- Terlalu banyak cara kerja bagian dalam daftar diekspos ke programmer
Kami akan membahas semua masalah ini di bagian berikut.
KELAS DAFTAR TUNGGAL YANG DITAUTKAN
Sebuah daftar jelas merupakan konsep yang terpisah dari sebuah node. Jadi kita mulai dengan membuat kelas yang sangat sederhana untuk
pegang daftar kami. Kita akan mulai dengan konstruktor yang menyimpan referensi ke node pertama dalam daftar. Karena daftar ini awalnya kosong, kita akan mulai dengan menyetel referensi ini ke Tidak Ada:
class SinglyLinkedList:
def __init__(self):
self.tail = None
TAMBAHKAN OPERASI
Operasi pertama yang perlu kita lakukan adalah menambahkan item ke daftar. Operasi ini terkadang disebut operasi penyisipan. Di sini kita mendapat kesempatan untuk menyembunyikan kelas Node. Itu pengguna kelas daftar kami seharusnya tidak pernah berinteraksi dengan objek Node. Ini adalah murni untuk penggunaan internal.
Jepretan pertama pada metode append () mungkin terlihat seperti ini:
class SinglyLinkedList:
# ...
def append(self, data):
# Encapsulate the data in a Node
node = Node(data)
if self.tail == None:
self.tail = node
else:
current = self.tail
while current.next:
current = current.next
current.next = node
Kami merangkum data dalam sebuah node, sehingga sekarang memiliki atribut pointer berikutnya. Dari sini kami memeriksa apakah ada node yang ada dalam daftar (yaitu, melakukan self.tail menunjuk ke sebuah Node). Jika tidak ada, kita menjadikan simpul baru sebagai simpul pertama dari daftar; jika tidak, temukan penyisipan menunjuk dengan melintasi daftar ke simpul terakhir, memperbarui penunjuk berikutnya dari simpul terakhir kesimpulan baru.
Kami dapat menambahkan beberapa item:
>>> words = SinglyLinkedList()
>>> words.append('egg')
>>> words.append('ham')
>>> words.append('spam')
Penjelajahan daftar akan bekerja lebih atau kurang seperti sebelumnya. Anda akan mendapatkan elemen pertama daftar dari daftar itu sendiri:
>>> current = words.tail
>>> while current:
print(current.data)
current = current.next
Operasi penambahan yang lebih cepat
Ada masalah besar dengan metode append di bagian sebelumnya: metode ini harus melintasi seluruh daftar untuk menemukan titik penyisipan. Ini mungkin tidak menjadi masalah bila hanya ada beberapa item dalam daftar, tetapi tunggu hingga Anda perlu menambahkan ribuan item. Setiap lampiran akan menjadi sedikit lebih lambat dari yang sebelumnya. A O (n) membuktikan betapa lambatnya arus kita
penerapan metode append sebenarnya.
Untuk memperbaikinya, kami akan menyimpan, tidak hanya referensi ke node pertama dalam daftar, tetapi juga referensi ke node terakhir. Dengan begitu, kami dapat dengan cepat menambahkan node baru di akhir daftar. Waktu berjalan kasus terburuk dari operasi penambahan sekarang dikurangi dari O (n) menjadi O (1). Yang harus kita lakukan adalah memastikan simpul terakhir sebelumnya menunjuk ke simpul baru, yang akan ditambahkan ke daftar. Ini kode kami yang diperbarui:
class SinglyLinkedList:
def __init__(self):
# ...
self.tail = None
def append(self, data):
node = Node(data)
if self.head:
self.head.next = node
self.head = node
else:
self.tail = node
self.head = node
Catat konvensi yang digunakan. Titik di mana kami menambahkan node baru adalah melalui self.head. Variabel self.tail menunjuk ke node pertama dalam daftar.
Mendapatkan ukuran daftar
Kami ingin mendapatkan ukuran daftar dengan menghitung jumlah node. Salah satu cara kami dapat melakukan ini adalah dengan menelusuri seluruh daftar dan meningkatkan penghitung seiring berjalannya waktu:
def size(self):
count = 0
current = self.tail
while current:
count += 1
current = current.next
return count
Ini berfungsi, tetapi list traversal berpotensi menjadi operasi mahal yang harus kita hindari
kapan kita bisa. Jadi sebagai gantinya, kita akan memilih metode penulisan ulang yang lain. Kami menambahkan anggota ukuran ke kelas SinglyLinkedList, menginisialisasinya ke 0 di konstruktor. Kemudian kami menambah ukuran satu per satu dalam metode append:
class SinglyLinkedList:
def __init__(self):
# ...
self.size = 0
def append(self, data):
# ...
self.size += 1
Karena kita sekarang hanya membaca atribut size dari objek node, dan tidak menggunakan loop
untuk menghitung jumlah node dalam daftar, kita dapat mengurangi waktu berjalan dari kasus terburuk
O (n) sampai O (1).
Meningkatkan traversal daftar
Jika Anda memperhatikan bagaimana kami menelusuri daftar kami. Itu satu tempat di mana kita masih terkena node kelas. Kita perlu menggunakan node.data untuk mendapatkan konten dari node dan node.next untuk mendapatkan node berikutnya. Tapi kami sebutkan sebelumnya bahwa kode klien tidak perlu berinteraksi dengan objek Node. Kita dapat mencapai ini dengan membuat metode yang mengembalikan generator. Sepertinya berikut:
def iter(self):
current = self.tail
while current:
val = current.data
current = current.next
yield val
Sekarang traversal daftar jauh lebih sederhana dan terlihat jauh lebih baik juga. Kami sepenuhnya dapat mengabaikan fakta bahwa ada sesuatu yang disebut Node di luar daftar:
for word in words.iter():
print(word)
Perhatikan bahwa karena metode iter () menghasilkan anggota data dari node, kode klien kita tidak perlu mengkhawatirkan hal itu sama sekali.
Menghapus node
Operasi umum lainnya yang perlu Anda lakukan pada daftar adalah menghapus node. Ini mungkin tampak sederhana, tetapi pertama-tama kami harus memutuskan cara memilih node untuk dihapus. Apakah akan berdasarkan nomor indeks atau dengan data yang dikandung node? Di sini kita akan memilih untuk menghapus node berdasarkan data yang dikandungnya.
Berikut ini adalah gambaran kasus khusus yang dipertimbangkan saat menghapus node dari daftar:
Ketika kita ingin menghapus satu node yang berada di antara dua node lainnya, yang harus kita lakukan adalah membuat node sebelumnya langsung ke penerus node berikutnya. Artinya, kita cukup memotong simpul yang akan dihapus dari rantai seperti pada gambar sebelumnya.
Berikut adalah implementasi dari metode delete () mungkin terlihat seperti:
def delete(self, data):
current = self.tail
prev = self.tail
while current:
if current.data == data:
if current == self.tail:
self.tail = current.next
else:
prev.next = current.next
self.size -= 1
return
prev = current
current = current.next
Ini harus mengambil O (n) untuk menghapus node.
Pencarian daftar
Kami mungkin juga memerlukan cara untuk memeriksa apakah daftar berisi item. Metode ini cukup mudah diterapkan berkat metode iter () yang kami tulis sebelumnya. Setiap lintasan loop membandingkan data saat ini dengan data yang dicari. Jika kecocokan ditemukan, True dikembalikan, atau False dikembalikan:
def search(self, data):
for node in self.iter():
if data == node:
return True
return False
Menghapus daftar
Kami mungkin menginginkan cara cepat untuk menghapus daftar. Untungnya bagi kami, ini sangat sederhana. Yang kita lakukan hanyalah membersihkan kepala dan ekor penunjuk dengan mengaturnya ke Tidak Ada:
def clear(self):
""" Clear the entire list. """
self.tail = None
self.head = None
Dalam satu gerakan, kita menjadi yatim piatu semua node di ujung ekor dan kepala pointer daftar. Ini memiliki efek riak yang membuat semua node di antaranya menjadi yatim piatu.
Daftar yang ditautkan ganda
Sekarang setelah kita memiliki dasar yang kuat tentang apa itu daftar tertaut tunggal dan jenisnya operasi yang dapat dilakukan di atasnya, sekarang kita akan mengalihkan fokus kita satu tingkat lebih tinggi ke topik daftar tertaut ganda.
Daftar tertaut ganda entah bagaimana mirip dengan daftar tertaut tunggal di mana kami menggunakan ide dasar yang sama untuk merangkai node bersama-sama. Dalam daftar tertaut tunggal, terdapat satu tautan di antara setiap node yang berurutan. Sebuah node dalam daftar tertaut ganda memiliki dua petunjuk: a pointer ke node berikutnya dan pointer ke node sebelumnya:
Sebuah node dalam daftar tertaut tunggal hanya dapat menentukan node berikutnya yang terkait dengannya. Tetapinode yang direferensikan atau node berikutnya tidak memiliki cara untuk mengetahui siapa yang melakukan referensi. Aliran arah hanya satu arah.
Dalam daftar tertaut ganda, kami menambahkan ke setiap node kemampuan untuk tidak hanya mereferensikan node berikutnya tetapi juga node sebelumnya.
Mari kita periksa sifat dari keterkaitan yang ada antara dua node yang berurutan untuk lebih baik pemahaman:
Dengan adanya dua pointer yang mengarah ke node berikutnya dan sebelumnya, daftar tertaut ganda menjadi dilengkapi dengan kemampuan tertentu.
Daftar tertaut ganda dapat dilintasi ke segala arah. Bergantung pada operasi yang dilakukan, node dalam daftar tertaut ganda dapat dengan mudah merujuk ke node sebelumnya jika diperlukan tanpa harus menentukan variabel untuk melacak node tersebut. Karena A Daftar tertaut tunggal hanya dapat dilalui dalam satu arah, ini terkadang berarti berpindah ke awal atau awal daftar untuk mempengaruhi perubahan tertentu yang terkubur dalam daftar.
Karena ada akses langsung ke node berikutnya dan sebelumnya, operasi penghapusan dilakukan jauh lebih mudah dilakukan, seperti yang akan Anda lihat nanti di bab ini.
Node daftar tertaut ganda
Kode Python yang membuat kelas untuk menangkap apa yang termasuk node daftar tertaut ganda dalam metode inisialisasi, variabel instance prev, next, dan data. Saat node baru dibuat, semua variabel ini default ke Tidak Ada:
class Node(object):
def __init__(self, data=None, next=None, prev=None):
self.data = data
self.next = next
self.prev = prev
Variabel prev memegang referensi ke node sebelumnya, sedangkan variabel berikutnya berlanjut untuk menyimpan referensi ke node berikutnya.
Daftar tertaut ganda
Masih penting untuk membuat kelas yang menangkap data yang akan menjadi fungsi kita beroperasi pada:
class DoublyLinkedList(object):
def __init__(self):
self.head = None
self.tail = None
self.count = 0
Untuk tujuan meningkatkan metode ukuran, kami juga menyetel variabel contoh hitungan ke 0. head dan tail akan mengarah ke kepala dan ekor daftar ketika kami mulai memasukkan node ke dalam daftar.
Kami mengadopsi konvensi baru di mana self.head menunjuk ke simpul pemula daftar dan titik self.tail ke simpul terbaru yang ditambahkan ke daftar. Ini bertentangan dengan konvensi yang kami gunakan dalam daftar tertaut tunggal. Tidak ada aturan tetap untuk penamaan kepala dan ekor node pointer.
Daftar tertaut ganda juga perlu menyediakan fungsi yang mengembalikan ukuran daftar, menyisipkan ke dalam daftar, dan juga menghapus node dari daftar. Kami akan memeriksa beberapa kode untuk melakukan ini. Mari kita mulai dengan operasi penambahan.
Tambahkan operasi
Selama operasi penambahan, penting untuk memeriksa apakah head adalah None. Jika None, itu berarti list tersebut kosong dan harus memiliki head set yang mengarah ke node yang baru saja dibuat. Ekor daftar juga menunjuk ke simpul baru melalui kepala. Pada akhir rangkaian langkah ini, head dan tail sekarang akan mengarah ke node yang sama:
def append(self, data):
""" Append an item to the list. """
new_node = Node(data, None, None)
if self.head is None:
self.head = new_node
self.tail = self.head
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
self.count += 1
Diagram berikut mengilustrasikan penunjuk head dan tail dari daftar tertaut ganda ketika node baru ditambahkan ke daftar kosong.
Bagian lain dari algoritme hanya dijalankan jika daftarnya tidak kosong. Variabel node baru sebelumnya disetel ke ekor daftar:
new_node.prev = self.tail
Pointer (atau variabel) berikutnya dari ekor diatur ke simpul baru:
self.tail.next = new_node
Terakhir, kami memperbarui penunjuk ekor untuk menunjuk ke simpul baru:
self.tail = new_node
Karena operasi append meningkatkan jumlah node sebanyak satu, kami menambah penghitung sebanyak satu:
self.count += 1
Representasi visual dari operasi append adalah sebagai berikut:
Komentar
Posting Komentar