Koblede lister i Python

Introduksjon

En koblet liste er en datastruktur som består av en sekvens av noder, som hver inneholder en verdi og en referanse til neste node i sekvensen. I motsetning til matriser, krever ikke koblede lister sammenhengende minneallokering, noe som gjør dem mer fleksible og effektive for visse operasjoner. I denne artikkelen vil vi utforske fordelene og ulempene med koblede lister og hvordan du implementerer dem i Python.

Fordeler og ulemper med lenkede lister

Koblede lister gir flere fordeler i forhold til andre datastrukturer. For det første gir de mulighet for effektiv innsetting og sletting av elementer, da de bare krever oppdatering av referansene til nabonoder. Dette gjør LinkedLists ideelle for scenarier der hyppige endringer forventes. I tillegg kan LinkedLists dynamisk vokse eller krympe i størrelse, i motsetning til arrays, som har en fast størrelse.

Men lenkede lister har også noen ulemper. I motsetning til arrays, støtter ikke koblede lister tilfeldig tilgang til elementer, noe som betyr at tilgang til et element på en bestemt indeks krever at du krysser listen fra begynnelsen. Dette kan føre til tregere ytelse for visse operasjoner. Videre krever koblede lister ekstra minne for å lagre referansene til de neste nodene, noe som kan være ineffektivt for små datasett.

Implementering av koblede lister i Python

Python gir en fleksibel og intuitiv måte å implementere koblede lister på. Det er tre hovedtyper av lenkede lister: Enkeltlenket liste, dobbeltlenket liste og sirkulær lenket liste. La oss utforske hver av dem i detalj.

Enkeltlenket liste

En Singly Linked List består av noder der hver node inneholder en verdi og en referanse til neste node i sekvensen. Slik kan du opprette en enkeltlenket liste i Python:

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

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

Opprette en enkeltlenket liste

For å lage en enkeltlenket liste, må vi definere en nodeklasse som representerer hver node i listen. Hver node inneholder en verdi og en referanse til neste node. Linked List-klassen fungerer som beholder for nodene, med head-attributtet som peker til den første noden i listen.

Sette inn noder i en enkeltkoblet liste

Å sette inn noder i en enkeltlenket liste innebærer å oppdatere referansene til nabonoder. Her er et eksempel på å sette inn en node på begynnelsen av listen:

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

Slette noder fra en enkeltkoblet liste

Sletting av noder fra en enkeltlenket liste krever oppdatering av referansene til nabonoder. Her er et eksempel på sletting av en node med en bestemt verdi:

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

Søker i en enkeltlenket liste

Å søke etter en bestemt verdi i en enkeltlenket liste innebærer å gå gjennom listen til verdien er funnet eller slutten av listen er nådd. Her er et eksempel på søk etter en verdi:

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

Reversere en enkeltlenket liste

Å reversere en enkeltlenket liste krever oppdatering av referansene til hver node for å peke til forrige node. Her er et eksempel på reversering av en enkeltlenket liste:

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

Dobbeltkoblet liste

En dobbeltlenket liste ligner på en enkeltlenket liste, men hver node inneholder en referanse til både neste node og forrige node i sekvensen. Dette muliggjør effektiv traversering i begge retninger. Slik kan du opprette en dobbeltlenket liste i Python:

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

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

Opprette en dobbeltlenket liste

For å lage en dobbeltlenket liste, definerer vi en nodeklasse som inneholder en verdi, en referanse til neste node og en referanse til forrige node. DoublyLinked List-klassen fungerer som beholder for nodene, med head-attributtet som peker til den første noden i listen.

Sette inn noder i en dobbeltlenket liste

Å sette inn noder i en dobbeltlenket liste innebærer å oppdatere referansene til nabonoder. Her er et eksempel på å sette inn en node på begynnelsen av listen:

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

Slette noder fra en dobbeltkoblet liste

Sletting av noder fra en dobbeltkoblet liste krever oppdatering av referansene til nabonoder. Her er et eksempel på sletting av en node med en bestemt verdi:

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

Søker i en dobbeltlenket liste

Å søke etter en bestemt verdi i en dobbeltlenket liste innebærer å krysse listen i begge retninger til verdien er funnet eller slutten av listen er nådd. Her er et eksempel på søk etter en verdi:

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

Reversere en dobbeltlenket liste

Å reversere en dobbeltlenket liste krever oppdatering av referansene til hver node for å bytte neste og forrige pekere. Her er et eksempel på reversering av en dobbeltlenket liste:

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

Sirkulær lenket liste

En sirkulær lenket liste er en variant av en enkelt lenket liste der den siste noden peker tilbake til den første noden, og skaper en sirkulær struktur. Dette gir mulighet for effektiv traversering fra hvilken som helst node i listen. Slik kan du opprette en sirkulær lenket liste i Python:

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

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

Opprette en sirkulær lenket liste

For å lage en sirkulær lenket liste, definerer vi en nodeklasse som inneholder en verdi og en referanse til neste node. CircularLinked List-klassen fungerer som beholder for nodene, med head-attributtet som peker til den første noden i listen. I tillegg settes den siste nodens neste referanse til hodet, og skaper en sirkulær struktur.

Sette inn noder i en sirkulær lenket liste

Å sette inn noder i en sirkulær lenket liste innebærer å oppdatere referansene til nabonoder. Her er et eksempel på å sette inn en node på begynnelsen av listen:

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

Slette noder fra en sirkulær lenket liste

Sletting av noder fra en sirkulær lenket liste krever oppdatering av referansene til nabonoder. Her er et eksempel på sletting av en node med en bestemt verdi:

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

Søker i en sirkulær lenket liste

Å søke etter en bestemt verdi i en sirkulær lenket liste innebærer å krysse listen til verdien er funnet eller hele listen er krysset. Her er et eksempel på søk etter en verdi:

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

Reversere en sirkulær lenket liste

Å reversere en sirkulær lenket liste krever oppdatering av referansene til hver node for å reversere den sirkulære strukturen. Her er et eksempel på reversering av en sirkulær lenket liste:

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

Vanlige operasjoner på koblede lister

Koblede lister støtter ulike vanlige operasjoner som kan utføres på elementene. La oss utforske noen av disse operasjonene:

Tilgang til elementer i en koblet liste

For å få tilgang til elementer i en koblet liste, kan vi krysse listen fra hovednoden og flytte til neste node til vi når ønsket posisjon. Her er et eksempel på tilgang til et element ved en bestemt indeks:

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

Endre elementer i en koblet liste

Å endre elementer i en koblet liste innebærer å gå gjennom listen for å finne ønsket element og oppdatere verdien. Her er et eksempel på hvordan du endrer et element ved en bestemt indeks:

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

Finne lengden på en koblet liste

For å finne lengden på en koblet liste kan vi krysse listen og telle antall noder. Her er et eksempel på hvordan du finner lengden på en koblet liste:

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

Sjekker om en koblet liste er tom

For å sjekke om en koblet liste er tom, kan vi ganske enkelt sjekke om hodenoden er Ingen. Her er et eksempel på hvordan du sjekker om en koblet liste er tom:

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

Sammenknytte koblede lister

For å sette sammen to koblede lister, kan vi krysse den første listen for å finne den siste noden og oppdatere den neste referansen til hodet på den andre listen. Her er et eksempel på sammenkobling av to koblede lister:

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

Linked List vs. Array

Koblede lister og matriser er begge vanlig brukte datastrukturer, men de har forskjellige egenskaper som gjør dem egnet for forskjellige scenarier. La oss sammenligne lenkede lister og arrays når det gjelder minneeffektivitet, innsettings- og slettingseffektivitet og tilfeldig tilgangseffektivitet.

Minneeffektivitet

Koblede lister er mer minneeffektive enn matriser fordi de ikke krever sammenhengende minneallokering. Hver node i en koblet liste trenger bare å lagre verdien og en referanse til neste node, mens arrays trenger å allokere minne for alle elementer, selv om de ikke brukes.

Innsettings- og slettingseffektivitet

Koblede lister utmerker seg i innsettings- og slettingsoperasjoner, spesielt når elementer ofte legges til eller fjernes fra midten av listen. Innsetting eller sletting av et element i en koblet liste krever bare oppdatering av referansene til nabonoder, mens arrays kan kreve skiftende elementer for å imøtekomme endringen.

Tilfeldig tilgangseffektivitet

Matriser gir effektiv tilfeldig tilgang til elementer basert på deres indekser, ettersom de tillater direkte minneadressering. I motsetning til dette krever koblede lister å gå gjennom listen fra begynnelsen for å få tilgang til et element ved en spesifikk indeks, noe som resulterer i tregere ytelse for operasjoner med tilfeldig tilgang.

Velge riktig datastruktur

Valget mellom koblede lister og matriser avhenger av de spesifikke kravene til applikasjonen. Hvis hyppige endringer og dynamisk endring av størrelse forventes, er lenkede lister et bedre valg. På den annen side, hvis tilfeldig tilgang og minneeffektivitet er avgjørende, er arrays mer egnet.

Koblede listeapplikasjoner

Nå som vi har en god forståelse av koblede lister og hvordan de fungerer, la oss utforske noen av de praktiske applikasjonene der koblede lister kan brukes effektivt.

Du kan også melde deg på vår Gratis kurs I dag!

Implementering av stabler og køer

En av de vanligste bruksområdene for koblede lister er implementering av stabler og køer. Både stabler og køer er abstrakte datatyper som enkelt kan implementeres ved hjelp av koblede lister.

En stack er en datastruktur som følger Last-In-First-Out (LIFO)-prinsippet. Elementer legges til og fjernes fra samme ende, kjent som toppen av stabelen. Koblede lister gir en effektiv måte å implementere stabler på, da vi enkelt kan legge til eller fjerne elementer fra toppen av listen.

Her er et eksempel på implementering av en stabel ved hjelp av en koblet liste i Python:

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

En kø, derimot, følger First-In-First-Out (FIFO)-prinsippet. Elementer legges til i den ene enden, kjent som baksiden, og fjernes fra den andre enden, kjent som fronten. Koblede lister kan også brukes til å implementere køer effektivt.

Her er et eksempel på implementering av en kø ved å bruke en koblet liste i Python:

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

Håndtering av store datasett

Koblede lister er også nyttige når du arbeider med store datasett. I motsetning til arrays, krever koblede lister ikke sammenhengende minneallokering. Dette betyr at koblede lister effektivt kan håndtere datasett av varierende størrelse uten behov for endring av størrelse eller omfordeling.

La oss for eksempel si at vi har et datasett med millioner av poster, og vi må utføre operasjoner som innsetting, sletting eller kryssing. Å bruke en matrise for denne oppgaven kan være ineffektiv, da det krever skiftende elementer når du setter inn eller sletter. Men med en koblet liste kan vi enkelt sette inn eller slette elementer ved å oppdatere pekerne, noe som resulterer i raskere operasjoner.

Algoritmer for grafgjennomgang

Graftraversalalgoritmer, for eksempel bredde-først-søk (BFS) og dybde-først-søk (DFS), kan også implementeres ved å bruke koblede lister. Ved grafovergang besøker vi hvert toppunkt eller node i en graf i en bestemt rekkefølge.

Koblede lister kan brukes til å representere nabolisten til en graf, der hver node i den koblede listen representerer et toppunkt og dets tilstøtende toppunkter lagres som koblede listenoder. Denne representasjonen gir mulighet for effektiv traversering og utforskning av grafen.

Polynomrepresentasjon

Koblede lister kan brukes til å representere polynomer effektivt. I matematikk er polynomer uttrykk som består av variabler og koeffisienter. Hvert ledd i et polynom kan representeres som en node i en koblet liste, hvor koeffisienten og eksponenten er lagret som data.

Ved å bruke koblede lister kan vi enkelt utføre operasjoner på polynomer, som addisjon, subtraksjon og multiplikasjon. Nodene kan manipuleres for å utføre disse operasjonene, noe som resulterer i en kortfattet og effektiv representasjon av polynomer.

Musikk- og videospillelister

Koblede lister brukes ofte til å implementere spillelister i musikk- og videospillere. Hver sang eller video kan representeres som en node i en koblet liste, der dataene inneholder informasjon om mediefilen og pekeren peker til neste sang eller video i spillelisten.

Ved å bruke koblede lister for spillelister kan du enkelt navigere mellom sanger eller videoer. Vi kan enkelt legge til eller fjerne sanger fra spillelisten ved å oppdatere pekerne, noe som gir en sømløs brukeropplevelse.

konklusjonen

Avslutningsvis er koblede lister allsidige datastrukturer som finner applikasjoner i ulike domener. De kan brukes til å implementere stabler og køer, håndtere store datasett, utføre grafovergang, representere polynomer og lage spillelister. Koblede lister gir effektive løsninger på disse problemene ved å utnytte deres dynamiske minneallokering og enkle manipulering av noder.

Ved å forstå applikasjonene til koblede lister, kan vi ta informerte beslutninger når vi velger datastrukturer for programmene våre. Enten det er å administrere data, implementere algoritmer eller lage brukervennlige grensesnitt, lenkede lister tilbyr et verdifullt verktøy i programmererens verktøysett.

Så neste gang du støter på et problem som krever effektiv innsetting, sletting eller kryssing, bør du vurdere å bruke koblede lister for å forenkle løsningen og optimalisere koden.

Du kan også lese flere artikler relatert til Python Lists her:

Ofte Stilte Spørsmål

I slekt

• SEO-drevet innhold og PR-distribusjon. Bli forsterket i dag.
• PlatoData.Network Vertical Generative Ai. Styrk deg selv. Tilgang her.
• PlatoAiStream. Web3 Intelligence. Kunnskap forsterket. Tilgang her.
• PlatoESG. Karbon, CleanTech, Energi, Miljø, Solenergi, Avfallshåndtering. Tilgang her.
• PlatoHelse. Bioteknologisk og klinisk etterretning. Tilgang her.
• kilde: https://www.analyticsvidhya.com/blog/2024/02/linked-lists-in-python/