Halo lagi! Untuk mengantisipasi dimulainya kursus Pengembang Python, kami telah menyiapkan untuk Anda materi kepenulisan kecil pada daftar tertaut di Python.
Python adalah bahasa yang sangat nyaman dan beragam, tetapi secara default tidak memiliki struktur data seperti daftar tertaut atau LinkedList. Hari ini saya akan membagikan praktik terbaik saya tentang topik ini dan berbicara sedikit tentang apa struktur data ini. Artikel ini akan menarik bagi mereka yang pertama kali menemukan topik daftar tertaut dan ingin memahami cara kerjanya dari sudut pandang algoritmik.
Apa itu LinkedList?
LinkedList atau daftar tertaut adalah struktur data. Daftar tertaut menyediakan kemampuan untuk membuat antrian dua arah dari elemen apa pun. Setiap elemen dari daftar tersebut dianggap sebagai simpul. Bahkan, sebuah simpul memiliki nilainya, serta dua tautan ke simpul sebelumnya dan selanjutnya. Artinya, daftar ini "ditautkan" oleh simpul yang membantu memindahkan daftar ke atas atau ke bawah. Karena fitur struktural ini, Anda dapat mengatur tumpukan, antrian, atau antrian ganda dari daftar tertaut.
Mari kita visualisasikan definisi kering. Sekarang kami memiliki kucing yang duduk di dalam kotak. Dan pada setiap kotak dikatakan apa itu dalam urutan dan apa yang harus diperjuangkan.
Apa yang akan kami lakukan dengan daftar tertaut:- Periksa apakah elemen ini atau itu terkandung di dalamnya;
- Tambahkan node ke ujung;
- Dapatkan nilai sebuah node berdasarkan indeks;
- Hapus node.
Sebenarnya, ada lebih banyak pilihan untuk bekerja dengan mereka, tetapi kami akan memikirkan implementasi langkah-langkah dasar ini. Setelah memahami prinsip apa yang mereka bangun, Anda sendiri dapat dengan mudah menerapkan metode Anda sendiri.
Anda harus mulai dengan membuat dua kelas:
class Box: def __init__ (self,cat = None): self.cat = cat self.nextcat = None class LinkedList: def __init__(self): self.head = None
Dalam kasus umum, kami memiliki simpul yang memiliki beberapa nilai di dalamnya - kucing, dan tautan ke simpul berikutnya. Yaitu, di kelas Kotak, masing-masing, ada kucing dan tautan ke kotak berikutnya. Seperti daftar mana pun, koheren juga memiliki permulaan, yaitu kepala. Karena tidak ada apa-apa di sana pada awalnya, elemen awal diatur ke Tidak ada.
Apakah item dalam daftar
Mari kita mulai dengan yang sederhana. Untuk memeriksa apakah ada kucing tertentu di salah satu kotak yang terletak di seri, Anda perlu menelusuri seluruh daftar, memeriksa nilai yang ada dengan nilai-nilai elemen dalam daftar.
def contains (self, cat): lastbox = self.head while (lastbox): if cat == lastbox.cat: return True else: lastbox = lastbox.nextcat return False
Tambahkan simpul ke akhir daftar
Pertama, Anda perlu membuat kotak baru, dan sudah memasukkan kucing baru di dalamnya. Setelah itu, Anda perlu memeriksa, mulai dari awal daftar tertaut, jika ada tautan ke yang berikutnya di simpul saat ini dan jika ada, kemudian pergi ke sana, jika simpul adalah yang terakhir, maka Anda perlu membuat tautan ke simpul berikutnya dan meletakkan kotak baru yang sama di dalamnya, yang kami buat.
def addToEnd(self, newcat): newbox = Box(newcat) if self.head is None: self.head = newbox return lastbox = self.head while (lastbox.nextcat): lastbox = lastbox.nextcat lastbox.nextcat = newbox
Dapatkan node berdasarkan indeks
Dengan indeks catIndex kami ingin mendapatkan node kotak, tetapi karena indeks tidak disediakan untuk node seperti itu, kita perlu membuat beberapa jenis penggantian, yaitu variabel yang akan bertindak sebagai indeks. Variabel ini adalah boxIndex. Kami memeriksa seluruh daftar dan memeriksa "nomor seri" dari node, dan jika cocok dengan indeks yang diinginkan, kami menghasilkan hasilnya.
def get(self, catIndex): lastbox = self.head boxIndex = 0 while boxIndex <= catIndex: if boxIndex == catIndex: return lastbox.cat boxIndex = boxIndex + 1 lastbox = lastbox.nextcat
Hapus simpul
Di sini kami mempertimbangkan penghapusan elemen bukan oleh indeks, tetapi dengan nilai, untuk memperkenalkan setidaknya beberapa variasi.
Pencarian dimulai dari kepala daftar, yaitu, dari kotak pertama berturut-turut, dan berlanjut sampai kotak habis, yaitu, sampai headcat menjadi Tidak ada. Kami memeriksa apakah nilai yang disimpan dalam simpul saat ini cocok dengan yang kami ingin hapus. Jika tidak, maka kita lanjutkan saja. Namun, jika cocok, maka kami menghapusnya dan "menautkan kembali" tautannya, yaitu, kami menghapus kotak N-th, sementara kotak N-1 sekarang merujuk ke kotak N +1.
def removeBox(self,rmcat): headcat = self.head if headcat is not None: if headcat.cat==rmcat: self.head = headcat.nextcat headcat = None return while headcat is not None: if headcat.cat==rmcat: break lastcat = headcat headcat = headcat.nextcat if headcat == None: return lastcat.nextcat = headcat.nextcat headcat = None
Itu saja, terima kasih sudah membaca materi! Faktanya, struktur LinkedList tidak rumit, dan penting untuk memahami cara kerjanya dari dalam. Tentu saja, dalam Python itu bisa diimplementasikan dalam ekspresi lambda, itu akan memakan banyak ruang lebih sedikit, tetapi di sini saya bertujuan untuk menjelaskan strukturnya, dan prinsip operasinya dalam Python sedetail mungkin, daripada mengejar optimasi.
Kode sumber dapat
ditemukan di sini .