Linkitetyt luettelot Pythonissa

esittely

Linked List on tietorakenne, joka koostuu solmujonosta, joista jokainen sisältää arvon ja viittauksen sekvenssin seuraavaan solmuun. Toisin kuin taulukot, linkitetyt luettelot eivät vaadi jatkuvaa muistin varausta, mikä tekee niistä joustavampia ja tehokkaampia tietyille toiminnoille. Tässä artikkelissa tutkimme linkitettyjen luetteloiden etuja ja haittoja sekä niiden toteuttamista Pythonissa.

Linkitettyjen luetteloiden edut ja haitat

Linkitetyt listat tarjoavat useita etuja muihin tietorakenteisiin verrattuna. Ensinnäkin ne mahdollistavat elementtien tehokkaan lisäämisen ja poistamisen, koska ne edellyttävät vain naapurisolmujen viitteiden päivittämistä. Tämä tekee LinkedLists-luetteloista ihanteellisia skenaarioihin, joissa on odotettavissa usein muutoksia. Lisäksi LinkedLists voi kasvaa tai pienentyä dynaamisesti, toisin kuin taulukot, joilla on kiinteä koko.

Linkitetyillä listoilla on kuitenkin myös joitain haittoja. Toisin kuin taulukot, linkitetyt luettelot eivät tue satunnaista pääsyä elementteihin, mikä tarkoittaa, että tietyn indeksin elementin käyttäminen edellyttää luettelon läpikulkua alusta alkaen. Tämä voi heikentää tiettyjen toimintojen toimintaa. Lisäksi linkitetyt luettelot vaativat lisämuistia viittausten tallentamiseen seuraaviin solmuihin, mikä voi olla tehotonta pienille tietojoukoille.

Linkitettyjen luetteloiden käyttöönotto Pythonissa

Python tarjoaa joustavan ja intuitiivisen tavan toteuttaa linkitettyjä listoja. Linkitettyjä luetteloita on kolme päätyyppiä: Yksittäin linkitetty luettelo, kaksoislinkitetty luettelo ja pyöreä linkitetty luettelo. Tutkitaan jokaista niistä yksityiskohtaisesti.

Yksittäin linkitetty luettelo

Yksittäin linkitetty lista koostuu solmuista, joissa jokainen solmu sisältää arvon ja viittauksen sekvenssin seuraavaan solmuun. Näin voit luoda yksitellen linkitetyn luettelon Pythonissa:

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

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

Yksittäin linkitetyn luettelon luominen

Yksittäisen linkitetyn luettelon luomiseksi meidän on määritettävä solmuluokka, joka edustaa luettelon jokaista solmua. Jokainen solmu sisältää arvon ja viittauksen seuraavaan solmuun. Linked List -luokka toimii säiliönä solmuille, ja head-attribuutti osoittaa luettelon ensimmäiseen solmuun.

Solmujen lisääminen yksittäin linkitettyyn luetteloon

Solmujen lisääminen yksittäislinkitettyyn luetteloon sisältää naapurisolmujen viitteiden päivittämisen. Tässä on esimerkki solmun lisäämisestä luettelon alkuun:

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

Solmujen poistaminen yksittäisestä linkitetystä luettelosta

Solmujen poistaminen yksittäisestä linkitetystä luettelosta edellyttää naapurisolmujen viitteiden päivittämistä. Tässä on esimerkki tietyn arvon omaavan solmun poistamisesta:

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

Haku yksittäin linkitetystä luettelosta

Tietyn arvon etsiminen yksitellen linkitetystä luettelosta edellyttää luettelon läpikulkua, kunnes arvo löytyy tai luettelon loppu on saavutettu. Tässä on esimerkki arvon etsimisestä:

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

Yksittäin linkitetyn luettelon peruuttaminen

Yksittäin linkitetyn luettelon kääntäminen käänteiseksi edellyttää kunkin solmun viittausten päivittämistä osoittamaan edelliseen solmuun. Tässä on esimerkki yksittäisen linkitetyn luettelon kääntämisestä:

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

Kaksoislinkitetty lista

Kaksinkertaisesti linkitetty luettelo on samanlainen kuin yksittäinen linkitetty luettelo, mutta jokainen solmu sisältää viittauksen sekä sekvenssin seuraavaan solmuun että edelliseen solmuun. Tämä mahdollistaa tehokkaan liikkumisen molempiin suuntiin. Näin voit luoda kaksoislinkitetyn luettelon Pythonissa:

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

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

Kaksinkertaisesti linkitetyn luettelon luominen

Luodaksesi kaksoislinkitetyn listan määritämme solmuluokan, joka sisältää arvon, viittauksen seuraavaan solmuun ja viittauksen edelliseen solmuun. DoublyLinked List -luokka toimii säiliönä solmuille, ja head-attribuutti osoittaa luettelon ensimmäiseen solmuun.

Solmujen lisääminen kaksoislinkitettyyn luetteloon

Solmujen lisääminen kaksoislinkitettyyn luetteloon sisältää naapurisolmujen viitteiden päivittämisen. Tässä on esimerkki solmun lisäämisestä luettelon alkuun:

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

Solmujen poistaminen kaksoislinkitetystä luettelosta

Solmujen poistaminen kaksoislinkitetystä luettelosta edellyttää naapurisolmujen viitteiden päivittämistä. Tässä on esimerkki tietyn arvon omaavan solmun poistamisesta:

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

Haku kaksoislinkitetystä luettelosta

Tietyn arvon etsiminen kaksoislinkitetystä luettelosta sisältää luettelon kulkemisen kumpaankin suuntaan, kunnes arvo löytyy tai luettelon loppu on saavutettu. Tässä on esimerkki arvon etsimisestä:

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

Kaksinkertaisesti linkitetyn luettelon peruuttaminen

Kaksinkertaisesti linkitetyn luettelon kääntäminen edellyttää kunkin solmun viitteiden päivittämistä seuraavan ja edellisen osoittimen vaihtamiseksi. Tässä on esimerkki kaksoislinkitetyn luettelon kääntämisestä:

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

Pyöreä linkitetty luettelo

Pyöreä linkitetty luettelo on muunnelma yksitellen linkitetystä luettelosta, jossa viimeinen solmu osoittaa takaisin ensimmäiseen solmuun ja luo pyöreän rakenteen. Tämä mahdollistaa tehokkaan läpikäynnin mistä tahansa luettelon solmusta. Näin voit luoda pyöreän linkitettyjen luettelon Pythonissa:

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

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

Pyöreän linkitetyn luettelon luominen

Circular Linked List -luettelon luomiseksi määritämme Node-luokan, joka sisältää arvon ja viittauksen seuraavaan solmuun. CircularLinked List -luokka toimii säiliönä solmuille, ja head-attribuutti osoittaa luettelon ensimmäiseen solmuun. Lisäksi viimeisen solmun seuraava viittaus asetetaan päähän, mikä luo pyöreän rakenteen.

Solmujen lisääminen pyöreään linkitettyyn luetteloon

Solmujen lisääminen pyöreään linkitettyyn luetteloon sisältää naapurisolmujen viitteiden päivittämisen. Tässä on esimerkki solmun lisäämisestä luettelon alkuun:

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

Solmujen poistaminen pyöreästä linkitetystä luettelosta

Solmujen poistaminen pyöreästä linkitetystä luettelosta edellyttää naapurisolmujen viitteiden päivittämistä. Tässä on esimerkki tietyn arvon omaavan solmun poistamisesta:

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

Haku kiertokirjeestä linkitetystä luettelosta

Tietyn arvon etsiminen pyöreästä linkitetystä luettelosta sisältää luettelon kulkemisen, kunnes arvo löytyy tai koko luettelo on kuljetettu. Tässä on esimerkki arvon etsimisestä:

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

Pyöreän linkitetyn luettelon kääntäminen käänteiseksi

Pyöreän linkitetyn listan kääntäminen käänteiseksi edellyttää kunkin solmun viitteiden päivittämistä pyöreän rakenteen kääntämiseksi. Tässä on esimerkki pyöreän linkitetyn luettelon kääntämisestä:

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

Yhteiset toiminnot linkitetyissä luetteloissa

Linkitetyt luettelot tukevat erilaisia ​​yleisiä toimintoja, jotka voidaan suorittaa elementeille. Tutustutaanpa joihinkin näistä toiminnoista:

Elementtien käyttö linkitetyssä luettelossa

Päästäksemme linkitetyn luettelon elementteihin, voimme kulkea listan läpi alkaen pääsolmusta ja siirtyä seuraavaan solmuun, kunnes saavutamme halutun kohdan. Tässä on esimerkki tietyn hakemiston elementin käyttämisestä:

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")

Elementtien muokkaaminen linkitetyssä luettelossa

Elementtien muokkaaminen linkitetyssä luettelossa sisältää luettelon läpikäymisen halutun elementin löytämiseksi ja sen arvon päivittämisen. Tässä on esimerkki tietyn indeksin elementin muokkaamisesta:

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")

Linkitetyn luettelon pituuden löytäminen

Linkitetyn listan pituuden selvittämiseksi voimme kulkea luettelon läpi ja laskea solmujen lukumäärän. Tässä on esimerkki linkitetyn luettelon pituuden selvittämisestä:

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

Tarkistaa, onko linkitetty luettelo tyhjä

Tarkistaaksemme, onko linkitetty luettelo tyhjä, voimme yksinkertaisesti tarkistaa, onko pääsolmu Ei mitään. Tässä on esimerkki sen tarkistamisesta, onko linkitetty luettelo tyhjä:

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

Linkitettyjen luetteloiden ketjuttaminen

Kahden linkitetyn listan yhdistämiseksi voimme kulkea ensimmäisen luettelon läpi löytääksemme viimeisen solmun ja päivittämällä sen seuraavan viittauksen toisen luettelon päähän. Tässä on esimerkki kahden linkitetyn luettelon yhdistämisestä:

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

Linkitetty lista vs. Array

Linkitetyt listat ja taulukot ovat molemmat yleisesti käytettyjä tietorakenteita, mutta niillä on erilaiset ominaisuudet, jotka tekevät niistä sopivia erilaisiin skenaarioihin. Verrataan linkitettyjä listoja ja taulukoita muistin tehokkuuden, lisäys- ja poistotehokkuuden sekä hajasaannin tehokkuuden suhteen.

Muistin tehokkuus

Linkitetyt listat ovat muistitehokkaampia kuin taulukot, koska ne eivät vaadi jatkuvaa muistin varausta. Jokaisen linkitetyn listan solmun tarvitsee vain tallentaa arvo ja viittaus seuraavaan solmuun, kun taas taulukoiden on varattava muisti kaikille elementeille, vaikka niitä ei käytetä.

Lisäys- ja poistotehokkuus

Linkitetyt listat ovat loistavia lisäys- ja poistotoiminnoissa, varsinkin kun elementtejä lisätään usein tai poistetaan luettelon keskeltä. Elementin lisääminen tai poistaminen linkitetystä luettelosta edellyttää vain naapurisolmujen viitteiden päivittämistä, kun taas taulukot voivat vaatia elementtien siirtämistä muutoksen mukauttamiseksi.

Random Access -tehokkuus

Taulukot tarjoavat tehokkaan satunnaisen pääsyn elementteihin niiden indeksien perusteella, koska ne mahdollistavat suoran muistiosoitteen. Sitä vastoin linkitetyt luettelot edellyttävät luettelon läpikulkua alusta alkaen tietyn indeksin elementin käyttämiseksi, mikä johtaa hitaampaan suorituskykyyn hajasaantioperaatioissa.

Oikean tietorakenteen valitseminen

Valinta linkitettyjen luetteloiden ja taulukoiden välillä riippuu sovelluksen erityisvaatimuksista. Jos toistuvia muutoksia ja dynaamista koon muutosta odotetaan, linkitetyt luettelot ovat parempi valinta. Toisaalta, jos satunnaiskäyttö ja muistin tehokkuus ovat ratkaisevia, taulukot ovat sopivampia.

Linkitetyt luettelosovellukset

Nyt kun meillä on hyvä käsitys linkitetyistä luetteloista ja niiden toiminnasta, tutkitaan joitain käytännön sovelluksia, joissa linkitettyjä luetteloita voidaan käyttää tehokkaasti.

Voit myös ilmoittautua meille Ilmainen Kurssit Tänään!

Pinojen ja jonojen käyttöönotto

Yksi linkitettyjen listojen yleisimmistä sovelluksista on pinojen ja jonojen toteuttaminen. Sekä pinot että jonot ovat abstrakteja tietotyyppejä, jotka voidaan helposti toteuttaa linkitettyjen luetteloiden avulla.

Pino on tietorakenne, joka noudattaa Last-In-First-Out (LIFO) -periaatetta. Elementit lisätään ja poistetaan samasta päästä, joka tunnetaan pinon yläosassa. Linkitetyt listat tarjoavat tehokkaan tavan toteuttaa pinot, koska voimme helposti lisätä tai poistaa elementtejä luettelon päähän.

Tässä on esimerkki pinon toteuttamisesta Pythonissa linkitetyn luettelon avulla:

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

Jono sen sijaan noudattaa FIFO (First-In-First-Out) -periaatetta. Elementit lisätään toiseen päähän, joka tunnetaan nimellä takaosa, ja poistetaan toisesta päästä, joka tunnetaan nimellä etuosa. Linkitettyjä listoja voidaan käyttää myös jonojen tehokkaaseen toteuttamiseen.

Tässä on esimerkki jonon toteuttamisesta Pythonin linkitetyn luettelon avulla:

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

Suurten tietojoukkojen käsittely

Linkitetyt luettelot ovat hyödyllisiä myös suuria tietojoukkoja käsiteltäessä. Toisin kuin taulukot, linkitetyt luettelot eivät vaadi jatkuvaa muistin varausta. Tämä tarkoittaa, että linkitetyt luettelot voivat käsitellä tehokkaasti erikokoisia tietojoukkoja ilman kokoa tai kohdistamista uudelleen.

Oletetaan esimerkiksi, että meillä on miljoonien tietueiden tietojoukko ja meidän on suoritettava toimintoja, kuten lisäys, poistaminen tai läpikulku. Taulukon käyttäminen tähän tehtävään voi olla tehotonta, koska se vaatii elementtien siirtämistä lisättäessä tai poistettaessa. Linkitetyn luettelon avulla voimme kuitenkin helposti lisätä tai poistaa elementtejä päivittämällä osoittimia, mikä nopeuttaa toimintaa.

Graafisen läpikulkualgoritmit

Graafisten läpikulkualgoritmit, kuten leveyshaku (BFS) ja syvyyshaku (DFS), voidaan myös toteuttaa linkitettyjen listojen avulla. Graafin läpikäymisessä käymme graafin jokaisessa kärjessä tai solmussa tietyssä järjestyksessä.

Linkitettyjä listoja voidaan käyttää kuvaamaan graafin vierekkäisyyslistaa, jossa jokainen linkitetyn listan solmu edustaa kärkeä ja sen viereiset kärjet tallennetaan linkitetyiksi listasolmuiksi. Tämä esitys mahdollistaa tehokkaan kaavion läpikäynnin ja tutkimisen.

Polynomiesitys

Linkitettyjä listoja voidaan käyttää polynomien tehokkaaseen esittämiseen. Matematiikassa polynomit ovat lausekkeita, jotka koostuvat muuttujista ja kertoimista. Jokainen polynomin termi voidaan esittää solmuna linkitetyssä listassa, jossa kerroin ja eksponentti tallennetaan datana.

Linkitettyjen listojen avulla voimme helposti suorittaa polynomeille operaatioita, kuten yhteen-, vähennys- ja kertolaskuja. Solmuja voidaan manipuloida suorittamaan nämä toiminnot, mikä johtaa tiiviiseen ja tehokkaaseen polynomien esitykseen.

Musiikki- ja videosoittolistat

Linkitettyjä listoja käytetään yleisesti soittolistojen toteuttamiseen musiikki- ja videosoittimissa. Jokainen kappale tai video voidaan esittää solmuna linkitetyssä luettelossa, jossa tiedot sisältävät tiedot mediatiedostosta ja osoitin osoittaa soittolistan seuraavaan kappaleeseen tai videoon.

Linkitettyjen luetteloiden käyttö soittolistoille mahdollistaa helpon navigoinnin kappaleiden tai videoiden välillä. Voimme helposti lisätä tai poistaa kappaleita soittolistalta päivittämällä osoittimia, mikä tarjoaa saumattoman käyttökokemuksen.

Yhteenveto

Yhteenvetona voidaan todeta, että linkitetyt listat ovat monipuolisia tietorakenteita, jotka löytävät sovelluksia eri aloilla. Niillä voidaan toteuttaa pinoja ja jonoja, käsitellä suuria tietojoukkoja, suorittaa kuvaajan läpikulkua, edustaa polynomeja ja luoda soittolistoja. Linkitetyt luettelot tarjoavat tehokkaita ratkaisuja näihin ongelmiin hyödyntämällä niiden dynaamista muistin varausta ja helppoa solmujen käsittelyä.

Ymmärtämällä linkitettyjen luetteloiden sovellukset voimme tehdä tietoisia päätöksiä valittaessa tietorakenteita ohjelmillemme. Olipa kyse tietojen hallinnasta, algoritmien toteuttamisesta tai käyttäjäystävällisten käyttöliittymien luomisesta, linkitetyt luettelot tarjoavat arvokkaan työkalun ohjelmoijan työkalupakkiin.

Joten kun seuraavan kerran kohtaat ongelman, joka vaatii tehokasta lisäämistä, poistamista tai läpikulkua, harkitse linkitettyjen luetteloiden käyttöä ratkaisun yksinkertaistamiseksi ja koodin optimoimiseksi.

Voit myös lukea lisää Python-listoihin liittyviä artikkeleita täältä:

Usein kysytyt kysymykset

liittyvä

• SEO-pohjainen sisällön ja PR-jakelu. Vahvista jo tänään.
• PlatoData.Network Vertical Generatiivinen Ai. Vahvista itseäsi. Pääsy tästä.
• PlatoAiStream. Web3 Intelligence. Tietoa laajennettu. Pääsy tästä.
• PlatoESG. hiili, CleanTech, energia, ympäristö, Aurinko, Jätehuolto. Pääsy tästä.
• PlatonHealth. Biotekniikan ja kliinisten kokeiden älykkyys. Pääsy tästä.
• Lähde: https://www.analyticsvidhya.com/blog/2024/02/linked-lists-in-python/