Povezani seznami v Pythonu

Predstavitev

Povezani seznam je podatkovna struktura, sestavljena iz zaporedja vozlišč, od katerih vsako vsebuje vrednost in sklic na naslednje vozlišče v zaporedju. Za razliko od nizov povezani seznami ne zahtevajo neprekinjenega dodeljevanja pomnilnika, zaradi česar so bolj prilagodljivi in ​​učinkoviti za določene operacije. V tem članku bomo raziskali prednosti in slabosti povezanih seznamov ter kako jih implementirati v Python.

Prednosti in slabosti povezanih seznamov

Povezani seznami ponujajo več prednosti pred drugimi podatkovnimi strukturami. Prvič, omogočajo učinkovito vstavljanje in brisanje elementov, saj zahtevajo le posodobitev referenc sosednjih vozlišč. Zaradi tega so LinkedLists idealni za scenarije, kjer se pričakujejo pogoste spremembe. Poleg tega lahko seznami LinkedLists dinamično rastejo ali se zmanjšujejo v velikosti, za razliko od nizov, ki imajo fiksno velikost.

Vendar imajo povezani seznami tudi nekaj slabosti. Za razliko od matrik povezani seznami ne podpirajo naključnega dostopa do elementov, kar pomeni, da dostop do elementa na določenem indeksu zahteva prečkanje seznama od začetka. To lahko povzroči počasnejše delovanje nekaterih operacij. Poleg tega povezani seznami potrebujejo dodaten pomnilnik za shranjevanje referenc na naslednja vozlišča, kar je lahko neučinkovito za majhne nize podatkov.

Implementacija povezanih seznamov v Pythonu

Python ponuja prilagodljiv in intuitiven način za implementacijo povezanih seznamov. Obstajajo tri glavne vrste povezanih seznamov: enojni povezani seznam, dvojno povezani seznam in krožni povezani seznam. Raziščimo vsakega od njih podrobno.

Posamezno povezan seznam

Posamezno povezan seznam je sestavljen iz vozlišč, kjer vsako vozlišče vsebuje vrednost in sklic na naslednje vozlišče v zaporedju. Takole lahko ustvarite posamično povezan seznam v Pythonu:

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

class Linked List:
    def __init__(self):
        self.head = None

Ustvarjanje enojno povezanega seznama

Če želite ustvariti posamično povezan seznam, moramo definirati razred vozlišča, ki predstavlja vsako vozlišče na seznamu. Vsako vozlišče vsebuje vrednost in sklic na naslednje vozlišče. Razred povezanega seznama služi kot vsebnik za vozlišča, pri čemer atribut glave kaže na prvo vozlišče na seznamu.

Vstavljanje vozlišč v posamično povezan seznam

Vstavljanje vozlišč v posamično povezan seznam vključuje posodabljanje referenc sosednjih vozlišč. Tukaj je primer vstavljanja vozlišča na začetek seznama:

def insert_at_beginning(self, value):
    new_node = Node(value)
    new_node.next = self.head
    self.head = new_node

Brisanje vozlišč s posamično povezanega seznama

Brisanje vozlišč s posamično povezanega seznama zahteva posodobitev referenc sosednjih vozlišč. Tukaj je primer brisanja vozlišča z določeno vrednostjo:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                break
            current = current.next

Iskanje v enojno povezanem seznamu

Iskanje določene vrednosti na posamično povezanem seznamu vključuje prečkanje seznama, dokler vrednost ni najdena ali dokler ni dosežen konec seznama. Tukaj je primer iskanja vrednosti:

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Obračanje enojno povezanega seznama

Obrnitev posamično povezanega seznama zahteva posodobitev referenc vsakega vozlišča, da kažejo na prejšnje vozlišče. Tukaj je primer obračanja enojno povezanega seznama:

def reverse(self):
    previous = None
    current = self.head
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    self.head = previous

Dvopovezan seznam

Dvojno povezan seznam je podoben enojno povezanemu seznamu, vendar vsako vozlišče vsebuje sklic na naslednje in prejšnje vozlišče v zaporedju. To omogoča učinkovito prečenje v obe smeri. Tukaj je opisano, kako lahko ustvarite dvojno povezan seznam v Pythonu:

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

class DoublyLinked List:
    def __init__(self):
        self.head = None

Ustvarjanje dvojno povezanega seznama

Za ustvarjanje dvojno povezanega seznama definiramo razred vozlišča, ki vsebuje vrednost, sklic na naslednje vozlišče in sklic na prejšnje vozlišče. Razred DoubleLinked List služi kot vsebnik za vozlišča, pri čemer atribut head kaže na prvo vozlišče na seznamu.

Vstavljanje vozlišč v dvojno povezan seznam

Vstavljanje vozlišč v dvojno povezan seznam vključuje posodabljanje referenc sosednjih vozlišč. Tukaj je primer vstavljanja vozlišča na začetek seznama:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if self.head:
        self.head.previous = new_node
    new_node.next = self.head
    self.head = new_node

Brisanje vozlišč z dvojno povezanega seznama

Brisanje vozlišč z dvojno povezanega seznama zahteva posodobitev referenc sosednjih vozlišč. Tukaj je primer brisanja vozlišča z določeno vrednostjo:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
        if self.head:
            self.head.previous = None
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                if current.next:
                    current.next.previous = current
                break
            current = current.next

Iskanje na dvojno povezanem seznamu

Iskanje določene vrednosti na dvojno povezanem seznamu vključuje prečkanje seznama v obe smeri, dokler ni vrednost najdena ali dosežen konec seznama. Tukaj je primer iskanja vrednosti:

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Obračanje dvojno povezanega seznama

Obračanje dvojno povezanega seznama zahteva posodobitev referenc vsakega vozlišča, da se zamenjajo naslednji in prejšnji kazalec. Tukaj je primer obračanja dvojno povezanega seznama:

def reverse(self):
    current = self.head
    while current:
        next_node = current.next
        current.next = current.previous
        current.previous = next_node
        if not next_node:
            self.head = current
        current = next_node

Krožni povezani seznam

Krožni povezani seznam je različica posamično povezanega seznama, kjer zadnje vozlišče kaže nazaj na prvo vozlišče, kar ustvarja krožno strukturo. To omogoča učinkovito prečkanje iz katerega koli vozlišča na seznamu. Tukaj je opisano, kako lahko ustvarite krožni povezani seznam v Pythonu:

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

class CircularLinked List:
    def __init__(self):
        self.head = None

Ustvarjanje krožnega povezanega seznama

Za ustvarjanje krožnega povezanega seznama definiramo razred vozlišča, ki vsebuje vrednost in sklic na naslednje vozlišče. Razred CircularLinked List služi kot vsebnik za vozlišča, pri čemer atribut head kaže na prvo vozlišče na seznamu. Poleg tega je naslednja referenca zadnjega vozlišča nastavljena na glavo, kar ustvarja krožno strukturo.

Vstavljanje vozlišč v krožni povezan seznam

Vstavljanje vozlišč v krožni povezan seznam vključuje posodabljanje referenc sosednjih vozlišč. Tukaj je primer vstavljanja vozlišča na začetek seznama:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if not self.head:
        self.head = new_node
        new_node.next = self.head
    else:
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head
        self.head = new_node

Brisanje vozlišč s krožnega povezanega seznama

Brisanje vozlišč s krožnega povezanega seznama zahteva posodobitev referenc sosednjih vozlišč. Tukaj je primer brisanja vozlišča z določeno vrednostjo:

def delete_node(self, value):
    if not self.head:
        return
    current = self.head
    if current.value == value:
        while current.next != self.head:
            current = current.next
        if current == self.head:
            self.head = None
        else:
            current.next = self.head.next
            self.head = self.head.next
    else:
        previous = None
        while current.next != self.head:
            previous = current
            current = current.next
            if current.value == value:
                previous.next = current.next
                break

Iskanje v krožnem povezanem seznamu

Iskanje določene vrednosti na krožnem povezanem seznamu vključuje prečkanje seznama, dokler vrednost ni najdena ali pa je prečkan celoten seznam. Tukaj je primer iskanja vrednosti:

def search(self, value):
    if not self.head:
        return False
    current = self.head
    while True:
        if current.value == value:
            return True
        current = current.next
        if current == self.head:
            break
    return False

Obračanje krožnega povezanega seznama

Obrnitev krožnega povezanega seznama zahteva posodobitev referenc vsakega vozlišča, da se obrne krožna struktura. Tukaj je primer obračanja krožnega povezanega seznama:

def reverse(self):
    if not self.head:
        return
    previous = None
    current = self.head
    next_node = current.next
    while True:
        current.next = previous
        previous = current
        current = next_node
        next_node = next_node.next
        if current == self.head:
            break
    self.head = previous

Pogoste operacije na povezanih seznamih

Povezani seznami podpirajo različne običajne operacije, ki jih je mogoče izvesti na elementih. Raziščimo nekaj teh operacij:

Dostop do elementov na povezanem seznamu

Za dostop do elementov na povezanem seznamu lahko prečkamo seznam, začenši od glavnega vozlišča in se premaknemo na naslednje vozlišče, dokler ne dosežemo želenega položaja. Tukaj je primer dostopa do elementa na določenem indeksu:

def get_element(self, index):
    current = self.head
    count = 0
    while current:
        if count == index:
            return current.value
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Spreminjanje elementov na povezanem seznamu

Spreminjanje elementov na povezanem seznamu vključuje prečkanje seznama za iskanje želenega elementa in posodabljanje njegove vrednosti. Tukaj je primer spreminjanja elementa na določenem indeksu:

def modify_element(self, index, new_value):
    current = self.head
    count = 0
    while current:
        if count == index:
            current.value = new_value
            return
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Iskanje dolžine povezanega seznama

Da bi našli dolžino povezanega seznama, lahko prečkamo seznam in preštejemo število vozlišč. Tu je primer ugotavljanja dolžine povezanega seznama:

def get_length(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.next
    return count

Preverjanje, ali je povezan seznam prazen

Če želite preveriti, ali je povezani seznam prazen, lahko preprosto preverimo, ali je glavno vozlišče None. Tukaj je primer preverjanja, ali je povezan seznam prazen:

def is_empty(self):
    return self.head is None

Združevanje povezanih seznamov

Če želite združiti dva povezana seznama, lahko prečkamo prvi seznam, da poiščemo zadnje vozlišče in posodobimo njegovo naslednjo referenco na glavo drugega seznama. Tu je primer združevanja dveh povezanih seznamov:

def concatenate(self, other_list):
    if not self.head:
        self.head = other_list.head
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = other_list.head

Povezani seznam proti nizu

Povezani seznami in polja so pogosto uporabljene podatkovne strukture, vendar imajo različne značilnosti, zaradi katerih so primerni za različne scenarije. Primerjajmo povezane sezname in polja glede učinkovitosti pomnilnika, učinkovitosti vstavljanja in brisanja ter učinkovitosti naključnega dostopa.

Učinkovitost pomnilnika

Povezani seznami so pomnilniško učinkovitejši od nizov, ker ne zahtevajo neprekinjenega dodeljevanja pomnilnika. Vsako vozlišče na povezanem seznamu mora shraniti le vrednost in sklic na naslednje vozlišče, medtem ko morajo polja dodeliti pomnilnik za vse elemente, tudi če niso uporabljeni.

Učinkovitost vstavljanja in brisanja

Povezani seznami so odlični pri operacijah vstavljanja in brisanja, zlasti kadar se elementi pogosto dodajajo ali odstranjujejo s sredine seznama. Vstavljanje ali brisanje elementa na povezanem seznamu zahteva samo posodobitev referenc sosednjih vozlišč, medtem ko lahko nizi zahtevajo premikanje elementov, da se prilagodijo spremembi.

Učinkovitost naključnega dostopa

Nizi zagotavljajo učinkovit naključen dostop do elementov na podlagi njihovih indeksov, saj omogočajo neposredno naslavljanje pomnilnika. Nasprotno pa povezani seznami zahtevajo prečkanje seznama od začetka za dostop do elementa na določenem indeksu, kar povzroči počasnejše delovanje operacij naključnega dostopa.

Izbira prave podatkovne strukture

Izbira med povezanimi seznami in nizi je odvisna od posebnih zahtev aplikacije. Če pričakujete pogoste spremembe in dinamično spreminjanje velikosti, so povezani seznami boljša izbira. Po drugi strani pa, če sta ključnega pomena naključni dostop in učinkovitost pomnilnika, so polja primernejša.

Aplikacije povezanega seznama

Zdaj, ko dobro razumemo povezane sezname in njihovo delovanje, poglejmo nekaj praktičnih aplikacij, kjer je mogoče povezane sezname učinkovito uporabiti.

Lahko se tudi vpišete v naše Prosti Tečaji Danes!

Implementacija skladov in čakalnih vrst

Ena najpogostejših aplikacij povezanih seznamov je implementacija skladov in čakalnih vrst. Tako skladi kot čakalne vrste so abstraktni podatkovni tipi, ki jih je mogoče preprosto implementirati z uporabo povezanih seznamov.

Sklad je podatkovna struktura, ki sledi načelu LIFO (Last-In-First-Out). Elementi se dodajajo in odstranjujejo z istega konca, znanega kot vrh sklada. Povezani seznami zagotavljajo učinkovit način za implementacijo skladov, saj lahko preprosto dodajamo ali odstranjujemo elemente z glave seznama.

Tukaj je primer implementacije sklada z uporabo povezanega seznama v Pythonu:

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

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

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.head is None:
            return None
        popped = self.head.data
        self.head = self.head.next
        return popped

Čakalna vrsta po drugi strani sledi načelu FIFO (first-in-first-out). Elementi so dodani na enem koncu, imenovanem zadnji del, in odstranjeni z drugega konca, znanega kot sprednji del. Povezane sezname je mogoče uporabiti tudi za učinkovito izvajanje čakalnih vrst.

Tukaj je primer implementacije čakalne vrste z uporabo povezanega seznama v Pythonu:

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

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return None
        dequeued = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return dequeued

Ravnanje z velikimi nabori podatkov

Povezani seznami so uporabni tudi pri delu z velikimi nabori podatkov. Za razliko od nizov povezani seznami ne zahtevajo neprekinjenega dodeljevanja pomnilnika. To pomeni, da lahko povezani seznami učinkovito obravnavajo nize podatkov različnih velikosti brez potrebe po spreminjanju velikosti ali prerazporeditvi.

Na primer, recimo, da imamo nabor podatkov z milijoni zapisov in moramo izvesti operacije, kot so vstavljanje, brisanje ali prečkanje. Uporaba matrike za to nalogo je lahko neučinkovita, saj zahteva premikanje elementov pri vstavljanju ali brisanju. Vendar pa lahko s povezanim seznamom preprosto vstavljamo ali brišemo elemente s posodabljanjem kazalcev, kar ima za posledico hitrejše operacije.

Algoritmi prečkanja grafov

Algoritme prečkanja grafa, kot sta iskanje najprej v širino (BFS) in iskanje najprej v globino (DFS), je mogoče implementirati tudi z uporabo povezanih seznamov. Pri prehodu grafa obiščemo vsako točko ali vozlišče v grafu v določenem vrstnem redu.

Povezane sezname je mogoče uporabiti za predstavitev seznama sosednosti grafa, kjer vsako vozlišče na povezanem seznamu predstavlja vozlišče, njegova sosednja vozlišča pa so shranjena kot vozlišča povezanega seznama. Ta predstavitev omogoča učinkovito prečkanje in raziskovanje grafa.

Polinomska predstavitev

Povezane sezname je mogoče uporabiti za učinkovito predstavitev polinomov. V matematiki so polinomi izrazi, sestavljeni iz spremenljivk in koeficientov. Vsak člen v polinomu je mogoče predstaviti kot vozlišče na povezanem seznamu, kjer sta koeficient in eksponent shranjena kot podatek.

Z uporabo povezanih seznamov lahko enostavno izvajamo operacije na polinomih, kot so seštevanje, odštevanje in množenje. Z vozlišči je mogoče manipulirati za izvajanje teh operacij, kar ima za posledico jedrnato in učinkovito predstavitev polinomov.

Seznami predvajanja glasbe in videa

Povezani seznami se običajno uporabljajo za izvajanje seznamov predvajanja v glasbenih in video predvajalnikih. Vsako pesem ali video je mogoče predstaviti kot vozlišče na povezanem seznamu, kjer podatki vsebujejo informacije o predstavnostni datoteki, kazalec pa kaže na naslednjo pesem ali video na seznamu predvajanja.

Uporaba povezanih seznamov za sezname predvajanja omogoča preprosto krmarjenje med pesmimi ali videoposnetki. Pesmi lahko preprosto dodamo ali odstranimo s seznama predvajanja s posodobitvijo kazalcev, kar zagotavlja brezhibno uporabniško izkušnjo.

zaključek

Skratka, povezani seznami so vsestranske podatkovne strukture, ki se uporabljajo na različnih področjih. Uporabljajo se lahko za izvajanje skladov in čakalnih vrst, obdelavo velikih naborov podatkov, izvajanje prečkanja grafov, predstavljanje polinomov in ustvarjanje seznamov predvajanja. Povezani seznami nudijo učinkovite rešitve za te težave z izkoriščanjem dinamičnega dodeljevanja pomnilnika in enostavnega upravljanja vozlišč.

Z razumevanjem aplikacij povezanih seznamov lahko sprejemamo premišljene odločitve pri izbiri podatkovnih struktur za naše programe. Ne glede na to, ali gre za upravljanje podatkov, izvajanje algoritmov ali ustvarjanje uporabniku prijaznih vmesnikov, povezani seznami ponujajo dragoceno orodje v programerjevem kompletu orodij.

Ko torej naslednjič naletite na težavo, ki zahteva učinkovito vstavljanje, brisanje ali prečkanje, razmislite o uporabi povezanih seznamov za poenostavitev rešitve in optimizacijo kode.

Tukaj lahko preberete tudi več člankov, povezanih s seznami Python:

Pogosto zastavljena vprašanja

Podobni

• Distribucija vsebine in PR s pomočjo SEO. Okrepite se še danes.
• PlatoData.Network Vertical Generative Ai. Opolnomočite se. Dostopite tukaj.
• PlatoAiStream. Web3 Intelligence. Razširjeno znanje. Dostopite tukaj.
• PlatoESG. Ogljik, CleanTech, Energija, Okolje, sončna energija, Ravnanje z odpadki. Dostopite tukaj.
• PlatoHealth. Obveščanje o biotehnologiji in kliničnih preskušanjih. Dostopite tukaj.
• vir: https://www.analyticsvidhya.com/blog/2024/02/linked-lists-in-python/