Lingitud loendid Pythonis – Plato AiStream V2.1

Taasavaldanud Platon

järgijaid: 0

Sissejuhatus

Lingitud loend on andmestruktuur, mis koosneb sõlmede jadast, millest igaüks sisaldab väärtust ja viidet jada järgmisele sõlmele. Erinevalt massiividest ei nõua lingitud loendid külgnevat mälu eraldamist, muutes need teatud toimingute jaoks paindlikumaks ja tõhusamaks. Selles artiklis uurime lingitud loendite eeliseid ja puudusi ning nende rakendamist Pythonis.

Sisukord

Lingitud loendite eelised ja puudused

Lingitud loendid pakuvad teiste andmestruktuuride ees mitmeid eeliseid. Esiteks võimaldavad need elementide tõhusat sisestamist ja kustutamist, kuna need nõuavad ainult naabersõlmede viidete värskendamist. See muudab LinkedListsi ideaalseks stsenaariumide jaoks, kus on oodata sagedasi muudatusi. Lisaks võivad LinkedListsi suurus dünaamiliselt kasvada või kahaneda, erinevalt massiividest, millel on kindel suurus.

Lingitud loenditel on aga ka mõningaid puudusi. Erinevalt massiividest ei toeta lingitud loendid juhuslikku juurdepääsu elementidele, mis tähendab, et konkreetse indeksi elemendile juurdepääs nõuab loendi läbimist algusest peale. Selle tulemuseks võib olla teatud toimingute aeglasem jõudlus. Lisaks vajavad lingitud loendid lisamälu, et salvestada viideid järgmistele sõlmedele, mis võib väikeste andmekogumite puhul olla ebaefektiivne.

Lingitud loendite rakendamine Pythonis

Python pakub paindlikku ja intuitiivset viisi lingitud loendite rakendamiseks. Lingitud loendeid on kolme peamist tüüpi: üksikult lingitud loend, topeltlingitud loend ja ringlingitud loend. Uurime igaüks neist üksikasjalikult.

Üksiklingitud loend

Üksiklingitud loend koosneb sõlmedest, kus iga sõlm sisaldab väärtust ja viidet jada järgmisele sõlmele. Pythonis üksikult lingitud loendi saate luua järgmiselt.

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

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

Üksiklingitud loendi loomine

Üksiklingitud loendi loomiseks peame määratlema sõlme klassi, mis esindab loendi iga sõlme. Iga sõlm sisaldab väärtust ja viidet järgmisele sõlmele. Lingitud loendi klass toimib sõlmede konteinerina, atribuut head osutab loendi esimesele sõlmele.

Sõlmede lisamine üksikult lingitud loendisse

Sõlmede lisamine üksikult lingitud loendisse hõlmab naabersõlmede viidete värskendamist. Siin on näide sõlme lisamisest loendi algusesse:

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

Sõlmede kustutamine üksikult lingitud loendist

Sõlmede kustutamine üksikult lingitud loendist nõuab naabersõlmede viidete värskendamist. Siin on näide konkreetse väärtusega sõlme kustutamisest.

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

Otsimine üksikult lingitud loendist

Konkreetse väärtuse otsimine üksikult lingitud loendist hõlmab loendi läbimist, kuni väärtus leitakse või loendi lõppu jõutakse. Siin on näide väärtuse otsimisest.

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

Üksiklingitud loendi ümberpööramine

Üksiklingitud loendi ümberpööramine nõuab iga sõlme viidete värskendamist, et need osutaksid eelmisele sõlmele. Siin on näide üksikult lingitud loendi ümberpööramisest:

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

Topeltlingitud loend

Topeltlingitud loend sarnaneb üksikult lingitud loendiga, kuid iga sõlm sisaldab viidet nii järjestuse järgmisele kui ka eelmisele sõlmele. See võimaldab tõhusat liikumist mõlemas suunas. Pythonis topeltlingitud loendi loomiseks tehke järgmist.

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

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

Topeltlingitud loendi loomine

Topeltlingitud loendi loomiseks määratleme klassi Node, mis sisaldab väärtust, viidet järgmisele sõlmele ja viidet eelmisele sõlmele. Klass DoublyLinked List toimib sõlmede konteinerina, atribuut head osutab loendi esimesele sõlmele.

Sõlmede lisamine topeltlingitud loendisse

Sõlmede lisamine topeltlingitud loendisse hõlmab naabersõlmede viidete värskendamist. Siin on näide sõlme lisamisest loendi algusesse:

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

Sõlmede kustutamine topeltlingitud loendist

Sõlmede kustutamine topeltlingitud loendist nõuab naabersõlmede viidete värskendamist. Siin on näide konkreetse väärtusega sõlme kustutamisest.

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

Otsimine topeltlingitud loendist

Konkreetse väärtuse otsimine topeltlingitud loendist hõlmab loendi läbimist mõlemas suunas, kuni väärtus leitakse või loendi lõppu jõutakse. Siin on näide väärtuse otsimisest.

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

Topeltlingitud loendi ümberpööramine

Topeltlingitud loendi ümberpööramine nõuab iga sõlme viidete värskendamist, et vahetada järgmine ja eelmine osuti. Siin on näide topeltlingitud loendi ümberpööramisest:

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

Ringikujuline lingitud loend

Ringikujuline lingitud loend on üksikult lingitud loendi variatsioon, kus viimane sõlm osutab tagasi esimesele sõlmele, luues ringikujulise struktuuri. See võimaldab tõhusat läbimist loendi mis tahes sõlmest. Pythonis saate ümmarguse lingitud loendi luua järgmiselt.

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

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

Ringikujulise lingitud loendi loomine

Ringikujulise lingitud loendi loomiseks määratleme klassi Node, mis sisaldab väärtust ja viidet järgmisele sõlmele. Klass CircularLinked List toimib sõlmede konteinerina, atribuut head osutab loendi esimesele sõlmele. Lisaks määratakse viimase sõlme järgmine viide peale, luues ringikujulise struktuuri.

Sõlmede lisamine ringikujulisse lingitud loendisse

Sõlmede lisamine ringikujulisse lingitud loendisse hõlmab naabersõlmede viidete värskendamist. Siin on näide sõlme lisamisest loendi algusesse:

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

Sõlmede kustutamine ringikujulisest lingitud loendist

Sõlmede kustutamiseks ringikujulisest lingitud loendist on vaja värskendada naabersõlmede viiteid. Siin on näide konkreetse väärtusega sõlme kustutamisest:

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

Otsimine ringikujulises lingitud loendis

Konkreetse väärtuse otsimine ringikujulisest lingitud loendist hõlmab loendi läbimist, kuni väärtus leitakse või kogu loend on läbitud. Siin on näide väärtuse otsimisest.

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

Ringikujulise lingitud loendi ümberpööramine

Ringikujulise lingitud loendi ümberpööramine nõuab ringikujulise struktuuri ümberpööramiseks iga sõlme viidete värskendamist. Siin on näide ringikujulise lingitud loendi ümberpööramisest:

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

Ühised toimingud lingitud loendites

Lingitud loendid toetavad mitmesuguseid tavalisi toiminguid, mida saab elementidega teha. Uurime mõnda neist toimingutest:

Juurdepääs lingitud loendi elementidele

Lingitud loendi elementidele juurde pääsemiseks saame loendi läbida alates peasõlmest ja liikuda järgmise sõlme juurde, kuni jõuame soovitud positsiooni. Siin on näide konkreetse indeksi elemendile juurdepääsust:

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

Lingitud loendi elementide muutmine

Lingitud loendi elementide muutmine hõlmab loendi läbimist soovitud elemendi leidmiseks ja selle väärtuse värskendamist. Siin on näide konkreetse indeksi elemendi muutmisest:

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

Lingitud loendi pikkuse leidmine

Lingitud loendi pikkuse leidmiseks saame loendit läbida ja sõlmede arvu kokku lugeda. Siin on näide lingitud loendi pikkuse leidmiseks.

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

Kontrollige, kas lingitud loend on tühi

Kontrollimaks, kas lingitud loend on tühi, saame lihtsalt kontrollida, kas peasõlm on Puudub. Siin on näide, kuidas kontrollida, kas lingitud loend on tühi:

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

Lingitud loendite ühendamine

Kahe lingitud loendi ühendamiseks võime läbida esimese loendi, et leida viimane sõlm, ja värskendada selle järgmist viidet teise loendi peale. Siin on näide kahe lingitud loendi ühendamisest:

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

Lingitud loend vs massiiv

Lingitud loendid ja massiivid on mõlemad sageli kasutatavad andmestruktuurid, kuid neil on erinevad omadused, mis muudavad need erinevate stsenaariumide jaoks sobivaks. Võrdleme lingitud loendeid ja massiive mälu tõhususe, sisestamise ja kustutamise tõhususe ning juhusliku juurdepääsu tõhususe osas.

Mälu efektiivsus

Lingitud loendid on mälutõhusamad kui massiivid, kuna need ei vaja külgnevat mälu eraldamist. Lingitud loendi iga sõlm peab salvestama ainult väärtuse ja viite järgmisele sõlmele, samas kui massiivid peavad eraldama mälu kõigi elementide jaoks, isegi kui neid ei kasutata.

Sisestamise ja kustutamise tõhusus

Lingitud loendid paistavad silma sisestus- ja kustutamistoimingutes, eriti kui elemente lisatakse sageli või loendi keskelt eemaldatakse. Lingitud loendisse elemendi lisamine või kustutamine nõuab ainult naabersõlmede viidete värskendamist, samas kui massiivid võivad vajada muudatuste kohandamiseks elementide nihutamist.

Juhusjuurdepääsu tõhusus

Massiivid pakuvad tõhusat juhuslikku juurdepääsu elementidele nende indeksite alusel, kuna need võimaldavad otsest mäluaadressi. Seevastu lingitud loendid nõuavad loendi algusest läbimist, et pääseda juurde konkreetse indeksi elemendile, mille tulemuseks on juhusliku juurdepääsu toimingute aeglasem jõudlus.

Õige andmestruktuuri valimine

Lingitud loendite ja massiivide valik sõltub rakenduse spetsiifilistest nõuetest. Kui eeldatakse sagedasi muudatusi ja dünaamilist suuruse muutmist, on lingitud loendid parem valik. Teisest küljest, kui juhuslik juurdepääs ja mälu tõhusus on üliolulised, on massiivid sobivamad.

Lingitud loendirakendused

Nüüd, kui mõistame lingitud loendeid ja nende toimimist hästi, uurime mõnda praktilist rakendust, kus lingitud loendeid saab tõhusalt kasutada.

Võite registreeruda ka meie Tasuta kursused Täna!

Virnade ja järjekordade rakendamine

Üks lingitud loendite levinumaid rakendusi on virnade ja järjekordade rakendamine. Nii virnad kui ka järjekorrad on abstraktsed andmetüübid, mida saab hõlpsasti rakendada lingitud loendite abil.

Virn on andmestruktuur, mis järgib põhimõtet Last-in-First-Out (LIFO). Elemendid lisatakse ja eemaldatakse samast otsast, mida nimetatakse virna ülaosaks. Lingitud loendid pakuvad tõhusat viisi virnade rakendamiseks, kuna saame loendi päises elemente lihtsalt lisada või sealt eemaldada.

Siin on näide virna rakendamisest Pythonis lingitud loendi abil:

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

Järjekord seevastu järgib FIFO (First-In-First-Out) põhimõtet. Elemendid lisatakse ühte otsa, mida nimetatakse tagumiseks, ja eemaldatakse teisest otsast, mida nimetatakse esiosaks. Lingitud loendeid saab kasutada ka järjekordade tõhusaks juurutamiseks.

Siin on näide Pythonis lingitud loendi abil järjekorra rakendamisest:

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

Suurte andmekogumite käsitlemine

Lingitud loendid on kasulikud ka suurte andmekogumite käsitlemisel. Erinevalt massiividest ei vaja lingitud loendid külgnevat mälu eraldamist. See tähendab, et lingitud loendid saavad tõhusalt käsitleda erineva suurusega andmekogumeid, ilma et oleks vaja suurust või ümberjaotamist.

Oletame näiteks, et meil on miljonitest kirjetest koosnev andmekogum ja me peame tegema selliseid toiminguid nagu sisestamine, kustutamine või läbimine. Massiivi kasutamine selle ülesande jaoks võib olla ebaefektiivne, kuna see nõuab lisamisel või kustutamisel elemente nihutada. Lingitud loendi abil saame aga lihtsalt viiteid värskendades elemente lisada või kustutada, mille tulemuseks on kiiremad toimingud.

Graafiku läbimise algoritmid

Graafiku läbimise algoritme, nagu laius-eesotsing (BFS) ja sügavus-eesotsing (DFS), saab rakendada ka lingitud loendite abil. Graafi läbimisel külastame graafi iga tippu või sõlme kindlas järjekorras.

Lingitud loendeid saab kasutada graafiku külgnemisloendi esitamiseks, kus iga lingitud loendi sõlm esindab tippu ja selle külgnevad tipud salvestatakse lingitud loendi sõlmedena. See esitus võimaldab graafiku tõhusat läbimist ja uurimist.

Polünoomiline esitus

Lingitud loendeid saab kasutada polünoomide tõhusaks esitamiseks. Matemaatikas on polünoomid avaldised, mis koosnevad muutujatest ja kordajatest. Iga polünoomi liiget saab esitada lingitud loendi sõlmena, kus koefitsient ja eksponent salvestatakse andmetena.

Lingitud loendeid kasutades saame polünoomidega hõlpsasti sooritada toiminguid, nagu liitmine, lahutamine ja korrutamine. Sõlme saab nende toimingute tegemiseks manipuleerida, mille tulemuseks on polünoomide lühike ja tõhus esitus.

Muusika ja video esitusloendid

Lingitud loendeid kasutatakse tavaliselt esitusloendite rakendamiseks muusika- ja videopleierites. Iga lugu või videot saab esitada lingitud loendis sõlmena, kus andmed sisaldavad teavet meediumifaili kohta ja kursor osutab esitusloendi järgmisele loole või videole.

Lingitud loendite kasutamine esitusloendite jaoks võimaldab lugude või videote vahel hõlpsat navigeerimist. Saame hõlpsasti esitusloendisse laule lisada või sealt eemaldada, värskendades viiteid, pakkudes sujuvat kasutuskogemust.

Järeldus

Kokkuvõtteks võib öelda, et lingitud loendid on mitmekülgsed andmestruktuurid, mis leiavad rakendusi erinevates valdkondades. Neid saab kasutada virnade ja järjekordade juurutamiseks, suurte andmekogumite haldamiseks, graafiku läbimiseks, polünoomide esitamiseks ja esitusloendite loomiseks. Lingitud loendid pakuvad nendele probleemidele tõhusaid lahendusi, võimendades nende dünaamilist mälujaotust ja hõlpsat sõlmede manipuleerimist.

Kui mõistame lingitud loendite rakendusi, saame teha oma programmide andmestruktuuride valimisel teadlikke otsuseid. Olgu selleks andmete haldamine, algoritmide juurutamine või kasutajasõbralike liideste loomine, lingitud loendid pakuvad programmeerija tööriistakomplektis väärtuslikku tööriista.

Seega kaaluge järgmisel korral, kui teil tekib probleem, mis nõuab tõhusat sisestamist, kustutamist või läbimist, lingitud loendite kasutamist, et oma lahendust lihtsustada ja koodi optimeerida.

Siit saate lugeda ka rohkem Pythoni loenditega seotud artikleid:

Korduma kippuvad küsimused

Q1: Mis on lingitud loend?

V: Lingitud loend on sõlmedest koosnev andmestruktuur, kus iga sõlm sisaldab väärtust ja viidet (või linki) jada järgmisele sõlmele.

Q2: Millised on lingitud loendite kasutamise eelised?

V: Lingitud loendid pakuvad tõhusaid sisestamis- ja kustutamistoiminguid, dünaamilist suuruse muutmist ega vaja külgnevat mälu eraldamist.

K3: Millised on lingitud loendite puudused?

V: Lingitud loenditel puudub juhuslik juurdepääs, mis nõuab elemendile juurdepääsuks läbimist. Samuti kulutavad nad lisamälu viidete salvestamiseks, mis võib väikeste andmehulkade puhul olla ebaefektiivne.

Q4: Millised on Pythonis lingitud loendite peamised tüübid?

V: Lingitud loendite peamised tüübid on üksikult lingitud loend, topeltlingitud loend ja ringikujuline lingitud loend.

K5. Millistel stsenaariumidel on lingitud loendid mälutõhusamad kui massiivid?

V: Lingitud loendid on dünaamilise suuruse muutmise ja sagedase sisestamise või kustutamise korral mälutõhusamad kui massiivid, kuna need ei nõua külgnevat mälu eraldamist.