Meniru Senarai Kamus dengan Senarai Terpaut dalam Python

Saya akan memulakan artikel ini dengan proses pemikiran dan visualisasi saya. Percubaan (anda boleh memilih untuk memanggilnya) yang membuka mata saya untuk mendapatkan lebih jelas tentang senarai terpaut. Ini membuatkan saya berhenti melihatnya sebagai abstrak, mengikut cara klise(data dan seterusnya) yang selalu dijelaskan.

Proses Pemikiran dan Visualisasi

Kebelakangan ini saya mula melihat kod dari perspektif yang lebih fizikal (OOP seperti yang biasanya dirujuk sebagai). Walau bagaimanapun, saya melangkaui kelas dan atribut; Saya mula menulis langkah dan algoritma sebelum setiap masa dan untuk gelung. Penat melompat ke abstraksi hanya untuk kepentingan. Ini menyebabkan saya mencuba beberapa perkara lagi yang seterusnya mengajar saya beberapa perkara lagi yang akan saya kongsikan dalam artikel ini.

Tiga soalan dan jawapan utama sebelum kita menyelidiki lebih mendalam:

• Apakah yang membentuk senarai terpaut?
• Apakah rupa nod?
• Apakah rupa senarai terpaut pada permulaan?

Untuk menjawab yang pertama; nod membentuk senarai terpaut.

Untuk soalan kedua; fikirkan nod dalam senarai terpaut seperti kereta menunda kereta lain. Dalam senario ini, anggap kedua-dua kereta mengandungi barang. Kereta kedua dipasang di belakang kereta pertama dengan rantai. Nod melakukan ini dalam senarai Terpaut dengan menahan data seperti barangan atau penumpang di dalam kereta. Jenis data ini boleh menjadi ringkas seperti integer atau rentetan atau struktur data yang lebih kompleks. Pada masa yang sama, setiap kereta mempunyai penyambung (rantai) yang menghubungkannya ke kereta seterusnya di jalan raya. Dalam senarai terpaut, ini ialah atribut seterusnya yang menghala ke alamat memori nod seterusnya atau nod sebelum (dalam senarai terpaut dua kali). Senarai bukan senarai terpaut tanpa atribut seterusnya.

Setiap kereta hanya tahu tentang kereta di hadapan atau di belakangnya sahaja (bergantung pada jenis senarai terpaut). Kereta terakhir tidak mempunyai rantai, bermakna ia tidak menunjukkan apa-apa. Dalam senarai terpaut ini selalunya diwakili oleh Tiada.

class Node:
    def __init__(self, data):
     self.data = data
     self.next = None

Untuk menjawab soalan ketiga; nod kepala memulakan senarai terpaut sama seperti kereta pertama memulakan tunda.

class LinkedList:
    def __init__(self):
      self.head = None

Setakat ini, kami telah melihat asas senarai terpaut. Kini kami akan membincangkan sebab utama saya menulis artikel ini.

pengenalan

Struktur data terbina dalam Python, seperti senarai dan kamus, menyediakan cara yang fleksibel untuk menyimpan dan mengurus data. Senarai membolehkan kami menyimpan urutan tersusun, manakala kamus membenarkan kami memasangkan kunci dengan nilai untuk akses mudah.

Dalam artikel ini, kami akan meneroka cara membuat senarai terpaut seperti kamus dengan menggunakan gubahan. Kami akan melihat perbezaan dalam penggunaan ingatan antara senarai terpaut seperti kamus kami dan senarai kamus. Kami juga akan melihat bagaimana nod kami boleh mendapatkan warisan daripada dict untuk menjadikan contoh nod sebagai kamus sebenar. Semua ini dalam usaha untuk memberikan lebih banyak perspektif untuk pemahaman kami tentang senarai terpaut.

Mencipta Senarai Terpaut Kami

Seperti yang diperiksa sebelum ini, senarai terpaut terdiri daripada nod. Nod ini setiap satu mempunyai segmen data dan segmen seterusnya. Data boleh menjadi ringkas seperti rentetan atau integer, atau kompleks.

Mudah:

class Node:
    def __init__(self, data):
     self.data = data
     self.next = None

Kelas Node (diwakili oleh My_Int) mempunyai data dan seterusnya sebagai atribut.

class LinkedList:
    def __init__(self):
      self.head = None

Akan berurusan dengan kes yang rumit dalam artikel ini:

Kompleks:

class My_Int:
    def __init__(self, data):
        self.data=data
        self.next=None    

Kelas nod (diwakili oleh My_Dict) memegang berbilang atribut: nama pengguna, kulit muka dan seterusnya. **kwargs sebagai hujah, membenarkan kaedah menerima sebarang bilangan hujah kata kunci tanpa mentakrifkan setiap satu secara eksplisit.

Setiap nod bukan sahaja menyimpan sekeping data tetapi menggabungkan berbilang bahagian (nama pengguna dan warna kulit) menjadi satu, menjadikannya lebih kompleks daripada struktur data asas seperti integer atau rentetan.

Kami kini akan membuat kelas My_List yang akan mengurus senarai terpaut kejadian My_Dict. Ia memerlukan atribut kepala. Kepala ini biasanya nod pertama yang memulakan senarai terpaut.

class My_Int:
          def __init__(self, data):
                 self.data=data
                 self.next=None


class LinkedList:
          def __init__(self):
                 self.head=None
          def  insert(self, node):
                  if self.head==None:
                     self.head = node
                     return

                  last_node = self.head
                  while(last_node.next):
                      last_node =last_node.next
                  last_node.next = node

          def traverse(self):
                current_node = self.head
                while(current_node):
                    print(current_node.data, end="->")
                    current_node = current_node.next
                print("None")

node1 = My_Int(5)
node2 = My_Int (10)
node3 = My_Int(15)

linked_list = LinkedList()
linked_list.insert(node1)
linked_list.insert(node2)
linked_list.insert(node3)
linked_list.traverse()

Kelas ini juga menyediakan kaedah sisipan untuk menambah entri nod baharu pada penghujungnya.
Kami juga mencipta contoh My_Dict di sini (iaitu nod). My_List akan bertindak sebagai bekas untuk objek My_Dict dalam struktur senarai terpaut. Setiap tika My_Dict disambungkan dengan rujukan seterusnya yang membolehkan My_List menguruskan traversal dan sisipan tika My_Dict secara dinamik. Ini pada asasnya menunjukkan komposisi.

Selepas penciptaan contoh My_Dict, kami menyemak untuk memastikan senarai itu tidak kosong dengan menyemak kehadiran kepala. Jika kepala tidak hadir, ini bermakna senarai itu kosong, jadi kita mulakan self.head sebagai nod baharu (iaitu my_dict). Pulangan kemudian segera keluar dari fungsi. Tidak perlu laksanakan lagi.

class My_Dict: #dict keys as attributes
    def __init__(self, **kwargs):
        self.username = kwargs['username']
        self.complexion = kwargs['complexion']
        self.next = None

Barisan selepas pemulangan berjalan apabila terdapat nod sebelum ini dalam senarai dan kami ingin memasukkan nod baharu. Kami memulakan nod last_dict itu sebagai kepala dan ini akan digunakan untuk mencari nod terakhir (penghujung senarai) supaya nod baharu boleh dilampirkan di sana. Gelung while mengulangi senarai sehingga ia mencapai nod terakhir. Selagi last_dict.next tidak sama dengan Tiada, ia bergerak ke nod seterusnya dengan menetapkan last_dict = lastdict.next.

Akhirnya last_dict.next = my_dict menambahkan my_dict ke penghujung senarai yang melengkapkan sisipan. Sebaik sahaja kami mengetahui last_dict.next ialah Tiada (iaitu, kami berada di nod terakhir), kami melampirkan my_dict di sana.

Kami kini berurusan dengan fungsi lintasan:

class Node:
    def __init__(self, data):
     self.data = data
     self.next = None

Fungsi traverse berulang melalui setiap nod dalam senarai terpaut dan melakukan tindakan (dalam kes ini, mencetak) pada setiap nod, dari kepala hingga hujung. Kaedah ini menyediakan paparan berjujukan semua nod dalam senarai.

Lihat kod penuh di bawah:

class LinkedList:
    def __init__(self):
      self.head = None

class My_Int:
    def __init__(self, data):
        self.data=data
        self.next=None    

Pelaksanaan kami di atas boleh dianggap sebagai senarai tersuai terpaut objek seperti kamus, tetapi ia berstruktur berbeza daripada senarai biasa Python standard kamus. Berikut adalah perkara yang perlu diberi perhatian:

• Kelas My_Dict: Setiap tika bertindak sebagai objek seperti kamus dengan atribut (nama pengguna dan warna kulit) dan penuding seterusnya, membolehkannya dipautkan kepada tika My_Dict yang lain.
• Kelas My_List: Kelas ini menguruskan senarai terpaut contoh My_Dict, mengekalkan kepala dan menyediakan kaedah sisipan untuk menambah entri baharu pada penghujungnya. Setiap nod disambungkan ke seterusnya melalui penuding seterusnya, mensimulasikan struktur senarai terpaut.

Algoritma

Adalah baik untuk mempunyai algoritma semasa menulis kod. Ini dikenali sebagai langkah yang diambil. Mungkin saya sepatutnya menulisnya sebelum kod di atas. Tetapi saya hanya mahu menunjukkan perbezaan dahulu antara senarai pautan klise setiap hari dan jenis yang lebih kompleks. Tanpa berlengah lagi, di bawah adalah langkah-langkahnya.

1. Buat kelas dengan atribut struktur nod.
2. Buat kelas lain memanggilnya LinkedList(atau apa sahaja). Tambahkan kepala sebagai atribut tunggal. Buat kepala=Tiada.
3. Untuk mencipta dan memasukkan nod:
   • buat tika Node.
   • Jika senarai kosong, biarkan contoh nod menjadi nilai kepala.
   • Jika senarai tidak kosong, tetapkan nod sebelumnya dengan nilai sebagai kepala.
   • Dengan semak syarat sebagai; jika atribut seterusnya nod sebelumnya bukan Tiada, gelung melalui senarai.
   • Akhirnya tetapkan sebelah nod sebelumnya untuk menghala ke nod baharu.
4. Untuk merentasi senarai:
   • Buat nod sementara dan tetapkan kepala sebagai nilai permulaannya.
   • Gelung dengan syarat jika nod sementara bukan Tiada.
   • Cetak data dalam nod sementara.
   • Alihkan nod sementara ke seterusnya
   • Akhirnya di penghujung, seterusnya ialah Tiada, jadi cetak Tiada.
5. Buat kejadian kelas seperti yang diperlukan.

Perbandingan dengan Senarai Kamus

Kami kini akan membandingkan apa yang kami ada di atas dengan senarai kamus Python dengan melihat beberapa perkara:

• Struktur dan Storan:

Senarai Kamus: Dalam Python, senarai kamus menyimpan setiap kamus sebagai elemen dalam struktur senarai bersebelahan, menjadikan setiap kamus boleh diakses melalui indeks.

class Node:
    def __init__(self, data):
     self.data = data
     self.next = None

Senarai Kamus Terpaut: Kod kami menggunakan struktur senarai terpaut, di mana setiap nod (contoh My_Dict seperti kamus) memegang rujukan kepada nod seterusnya dan bukannya menggunakan storan memori bersebelahan. Ini adalah lebih cekap ingatan untuk senarai besar jika elemen kerap berubah, tetapi ia lebih perlahan untuk akses mengikut kedudukan.

• Akses dan Sisipan: Senarai Kamus: Dalam senarai Python standard, mengakses elemen mengikut indeks ialah O(1) (masa tetap) kerana senarai Python ialah tatasusunan di bawah hud. Menambah kamus baharu pada penghujung biasanya O(1) tetapi menjadi O(n) jika saiz semula diperlukan.

Senarai Kamus Terpaut: Dalam senarai terpaut kami, mengakses elemen memerlukan masa traversal (O(n)), kerana kami perlu mengulangi nod demi nod. Memasukkan pada akhir juga O(n) kerana kita perlu mencari nod terakhir setiap kali. Walau bagaimanapun, memasukkan pada permulaan boleh menjadi O(1) kerana kita boleh menetapkan nod baharu sebagai kepala.

• Penggunaan Memori:

Senarai Kamus: Senarai Python menggunakan lebih banyak memori untuk menyimpan kamus dalam blok bersebelahan, kerana setiap item disimpan secara berurutan. Memori diperuntukkan secara dinamik untuk senarai Python, kadangkala mengubah saiz dan menyalin senarai apabila ia berkembang. Kita boleh membuktikan ini dalam kod menggunakan modul sys:

class LinkedList:
    def __init__(self):
      self.head = None

class My_Int:
    def __init__(self, data):
        self.data=data
        self.next=None    

Senarai Kamus Terpaut: Senarai terpaut menggunakan memori dengan cekap untuk setiap nod kerana ia hanya memperuntukkan memori seperti yang diperlukan. Walau bagaimanapun, ia memerlukan ruang tambahan untuk rujukan seterusnya dalam setiap nod.

class My_Int:
          def __init__(self, data):
                 self.data=data
                 self.next=None


class LinkedList:
          def __init__(self):
                 self.head=None
          def  insert(self, node):
                  if self.head==None:
                     self.head = node
                     return

                  last_node = self.head
                  while(last_node.next):
                      last_node =last_node.next
                  last_node.next = node

          def traverse(self):
                current_node = self.head
                while(current_node):
                    print(current_node.data, end="->")
                    current_node = current_node.next
                print("None")

node1 = My_Int(5)
node2 = My_Int (10)
node3 = My_Int(15)

linked_list = LinkedList()
linked_list.insert(node1)
linked_list.insert(node2)
linked_list.insert(node3)
linked_list.traverse()

class My_Dict: #dict keys as attributes
    def __init__(self, **kwargs):
        self.username = kwargs['username']
        self.complexion = kwargs['complexion']
        self.next = None

Daripada perkara di atas, kita dapat melihat perbezaan dalam bait; 776 dan 192.

Secara Teknikal Bukan Kamus

Dalam kod kami, kejadian My_Dict ialah objek seperti kamus dan bukannya kamus sebenar.

Berikut ialah beberapa sebab mengapa:

• Atribut seterusnya memautkan kejadian My_Dict bersama-sama, menjadikannya lebih seperti nod dalam senarai terpaut daripada kamus kendiri. Atribut seterusnya ini bukan ciri yang kami temui dalam kamus biasa.

  • Kaedah dan Tingkah Laku: Objek seperti kamus (seperti contoh My_Dict) boleh mempunyai kaedah dan gelagat yang menyerupai kamus tetapi secara teknikalnya bukan kamus. Mereka kekurangan kaedah seperti .keys(), .values(), .items(), dan operasi khusus kamus seperti pencincangan. Jika kami mahu objek My_Dict berkelakuan lebih seperti kamus, kami boleh mewarisi daripada dict terbina dalam Python untuk melaksanakan kaedah untuk memberi mereka fungsi kamus. Tetapi seperti yang dinyatakan, objek ini seperti kamus, kerana ia menyimpan data dalam gaya nilai kunci tetapi tidak mewarisi atau berkelakuan sama seperti kamus Python.

Di bawah ialah lihat bagaimana kita boleh mewarisi daripada kelas dict:

class My_List: #manager
    def __init__(self):
        self.head=None

def insert(self, **kwargs):
        my_dict = My_Dict(**kwargs) #instantiate dict
        #check if list is empty
        if self.head==None:
            self.head=my_dict
            return

        last_dict = self.head
        while(last_dict.next): 
            last_dict = last_dict.next
            last_dict.next = my_dict #makes the insertion dynamic       

Barisan pertama mengimport Dict daripada modul menaip Python. Ini menunjukkan bahawa My_Dict ialah kamus khusus.

class Node:
    def __init__(self, data):
     self.data = data
     self.next = None

Kelas My_Dict mewarisi daripada dict, bermakna ia akan mempunyai sifat kamus tetapi boleh disesuaikan.

class LinkedList:
    def __init__(self):
      self.head = None

Mari kita lihat pembina:

class My_Int:
    def __init__(self, data):
        self.data=data
        self.next=None    

__init__ memulakan instance My_Dict dengan nama pengguna dan atribut warna kulit. super().__init_() memanggil pembina kelas Dict induk. self['username'] = username dan self['complexion'] = complexion menyimpan nama pengguna dan complexion sebagai entri kamus, membenarkan kejadian My_Dict diakses seperti kamus (cth., new_dict['username']). Terdapat juga
atribut seterusnya dimulakan sebagai Tiada, menyediakan struktur senarai terpaut dengan membenarkan setiap tika My_Dict dipautkan kepada yang lain.

class My_Int:
          def __init__(self, data):
                 self.data=data
                 self.next=None


class LinkedList:
          def __init__(self):
                 self.head=None
          def  insert(self, node):
                  if self.head==None:
                     self.head = node
                     return

                  last_node = self.head
                  while(last_node.next):
                      last_node =last_node.next
                  last_node.next = node

          def traverse(self):
                current_node = self.head
                while(current_node):
                    print(current_node.data, end="->")
                    current_node = current_node.next
                print("None")

node1 = My_Int(5)
node2 = My_Int (10)
node3 = My_Int(15)

linked_list = LinkedList()
linked_list.insert(node1)
linked_list.insert(node2)
linked_list.insert(node3)
linked_list.traverse()

Kaedah di atas mengatasi kaedah kekunci daripada dict, membenarkannya mengembalikan semua kekunci dalam My_Dict. Menggunakan super().keys() memanggil induk
kaedah keys(), memastikan tingkah laku kamus standard.

class My_Dict: #dict keys as attributes
    def __init__(self, **kwargs):
        self.username = kwargs['username']
        self.complexion = kwargs['complexion']
        self.next = None

Dalam kaedah sisipan kelas MyList, kami boleh melihat cara kami membuat contoh tercipta bagi kelakuan kamus pameran kamus kami. Kami rantaikan kaedah keys() kepadanya dan kami juga menilai kunci nama pengguna dengannya. Kami melakukan ini dalam blok if and else. Dalam blok if ia mencetak kekunci nod kepala dan nama pengguna. Dalam blok else ia mencetak kekunci nod lain dan nama pengguna nod lain.

class My_List: #manager
    def __init__(self):
        self.head=None

Dalam kaedah traverse di atas di dalam pemahaman kamus:

def insert(self, **kwargs):
        my_dict = My_Dict(**kwargs) #instantiate dict
        #check if list is empty
        if self.head==None:
            self.head=my_dict
            return

        last_dict = self.head
        while(last_dict.next): 
            last_dict = last_dict.next
            last_dict.next = my_dict #makes the insertion dynamic       

Kami membina kamus dengan setiap pasangan nilai kunci daripada current_dict. current_dict = getattr(current_dict, 'next', None) berpindah ke nod seterusnya, berterusan sehingga current_dict menjadi Tiada.

Nota: apabila ia berkaitan dengan penggunaan memori, Mewarisi kelas kami daripada dict bermakna lebih banyak penggunaan memori. Tidak seperti senarai terpaut nod seperti kamus yang kami buat sebelum ini.

Kesimpulan

Matlamat artikel ini adalah untuk memberikan lebih banyak perspektif dan cerapan tentang senarai yang dipautkan, melebihi apa yang biasanya saya lihat dijelaskan sebagai. Saya tidak inovatif. Saya hanya bereksperimen dengan kod, cuba memberikan lebih banyak pandangan kepada mereka yang mungkin menganggapnya terlalu abstrak. Walau bagaimanapun, saya ingin tahu daripada pengaturcara yang lebih senior, apakah kelemahan yang boleh berlaku jika digunakan atau apabila digunakan pada masa lalu.

Atas ialah kandungan terperinci Meniru Senarai Kamus dengan Senarai Terpaut dalam Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!