Start | lankadlista
 

Länkad lista



En länkad lista är en datastruktur där varje nod, som också bär information av något slag, har en pekare (referens) till nästa nod i listan.

Egenskaper

Operatorer


Typiska operatorer på en lista är...

- InsertFirst (lägg till nod i början av listan)
- InsertLast (lägg till nod i slutet
- Insert på ett visst index (lägg till nod vid ett visst index
- Find, sök efter visst värde
- Sortering
- Utskrift

Fördel


- Kan växa och krympa efter behov.
- Element kan läggas till och tas bort var som helst.

Nackdel


- För att hitta nod n tar det O(N) tid. Det kan jämföras med andra datastrukturer där det tar O(log N) tid för att hitta ett värde, t.ex. binärträd.

Länkade Noder

Varje länk kan bära eller vara referens till annan information, t.ex. en siffra, eller komplex information, tex alla karaktärer i ett dataspel eller uppkopplade datorer eller vad som helst. Det har ingen betydelse för själva konceptet. Här låter vi för enkelhetens skull data vara en siffra. Men du kan föreställa dig att denna data i verkligheten är vad som helst.

Länk av noder


Konceptet är att vi skapar en Node och denna bär dels lite data och dels en pekare till nästa Nod i listan.
class Node: def __init__(self, data): self.data = data self.next = None
Så vi får en länkad lista där föregående pekar på nästa länk i listan. Den sista länken perkar på None och på så vis vet vi att listan är slut. Vi måste också hålla reda på en pekare till första länken.



Vi kan skapa en enkel class som är denna Node. Det intressanta i denna node är pekaren, next.

När vi bygger ihop en sådan här lista, dvs lägger till nya Noder, så måste vi koppla ihop noderna med varandra, genom att sätta rätt next -värden så att de bildar en länk.
class Node: def __init__(self, data): self.data = data self.next = None nynode1 = Node(45) nynode2 = Node(88) nynode3 = Node(99) nynode1.next = nynode2 nynode2.next = nynode3 node = nynode1 while(node): print(node.data) node = node.next
Har vi gjort så, då kan vi också traversera listan från början till slut och skriva ut alla värden. Notera hur vi vandrar från node till node, genom att använda next.

Traversera listan


Kan exemplifieras med en snurra som printar listan. Först printar vi första noden, det är där node pekar (node = nynode1).



Sen gör vi node = node.next och då är nya noden plötsligt nästa nod och vi printar således andra noden.


Sen gör vi node = node.next igen och printar tredje andra noden.


Sen gör vi node = node.next igen och då är node = None och vi hoppar ur loopen.

class LinkedList


Vi kan konstatera att vi behöver en klass som håller reda på själva länkade listan. I denna klass placerar vi alla metoder som har med länkade listan att göra. Vi kan börja med att stoppa in vår printfunktion. Det är också centralt att hålla koll på referensen som pekar på själva listans början. Det kommer vi behöva i alla andra metoder.
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def printList(self): temp = self.head while temp: print(temp.data) temp = temp.next lst = LinkedList() nynode1 = Node(45) nynode2 = Node(88) nynode3 = Node(99) nynode1.next = nynode2 nynode2.next = nynode3 lst.head = nynode1 lst.printList()

insertFirst


Nu behöver vi fler metoder förstås. LinkedList håller reda på head och det ser alltså ut som nedan.



För att stoppa in en ny Nod i början så behöver vi 1) skapa Noden och 2) ställa om pekarna så att den nya noden blir nya head och det gamla head blir länk nummer 2 i listan.


class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def insertFirst(self, data): temp = self.head self.head = Node(data) self.head.next = temp def printList(self): temp = self.head while temp: print(temp.data) temp = temp.next lst = LinkedList() lst.insertFirst(99) lst.insertFirst(88) lst.insertFirst(45) lst.printList()

insertLast


Vi kan skapa en funktion insertLast som lägger till på slutet. Det är ganska enkelt, så vi behöver kanske ingen bild utan koden förklarar sig bättre. Om listan är helt tom, så kan vi anropa insertFirst. Annars traverserar vi listan precis som vi gjorde i utskriftsfunktionen, fast med twisten denna gång att när vi kommer till slutet så skapar vi en ny nod. Job done. Case closed!
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def insertFirst(self, data): temp = self.head self.head = Node(data) self.head.next = temp def insertLast(self, data): temp = self.head if(temp == None): self.insertFirst(data) else: while temp.next: temp = temp.next temp.next = Node(data) def printList(self): temp = self.head while temp: print(temp.data) temp = temp.next lst = LinkedList() lst.insertLast(99) lst.insertLast(88) lst.insertLast(45) lst.printList()
Notera nu att siffrorna kommer i rätt ordning om vi lägger till dem på slutet, medans det blev omvänd ordning om vi lade till dem i början.

insertIndex


Vi vill ha en funktion med vilken vi kan stoppa in en ny länk någonstans inne i listan, på en viss position, dvs ett visst index. 0 = första.

Som vanligt behöver vi skapa vår node och sätta om lite pekare. För att hitta position X i listan, så kan vi snurra i en loop som vi gjorde med utskriften, fast stoppa efter X varv. Det borde väl fungera? Position 0 är alltså i början, dvs samma sak som insertFirst().



När vi kommer fram till vår node där vi vill stoppa in en länk, så behövs en referens till länken innan. Så jag skapar här en eftersläpande referens jag kallar prev som pekar på länken innan där vi skall stoppa in vår länk. Dessutom vill jag i min länkade lista att index 0 eller lägre skall avse position 0 och index längre än listan skall avse att lägga till på slutet.

class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def insertFirst(self, data): temp = self.head self.head = Node(data) self.head.next = temp def insertLast(self, data): temp = self.head if(temp == None): self.insertFirst(data) else: while temp.next: temp = temp.next temp.next = Node(data) def insertIndex(self, data, index): i = 0 prev = temp = self.head if(temp==None or index<=0): self.insertFirst(data) else: while(temp and i < index): prev = temp temp = temp.next i = i + 1 if(temp): ny = Node(data) prev.next = ny ny.next = temp else: self.insertLast(data) def printList(self): temp = self.head while temp: print(temp.data) temp = temp.next lst = LinkedList() lst.insertLast(99) lst.insertLast(88) lst.insertLast(45) lst.insertIndex(7777,-1) lst.insertIndex(3333,2) lst.printList()


deleteIndex


Vi behöver en funktion för att radera en node på position X också!



class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def insertFirst(self, data): temp = self.head self.head = Node(data) self.head.next = temp def insertLast(self, data): temp = self.head if(temp == None): self.insertFirst(data) else: while temp.next: temp = temp.next temp.next = Node(data) def insertIndex(self, data, index): i = 0 prev = temp = self.head if(temp==None or index<=0): self.insertFirst(data) else: while(temp and i < index): prev = temp temp = temp.next i = i + 1 if(temp): ny = Node(data) prev.next = ny ny.next = temp else: self.insertLast(data) def deleteIndex(self, index): i = 0 prev = temp = self.head if(self.head!=None and index==0): self.head = self.head.next else: while(temp and i < index): prev = temp temp = temp.next i = i + 1 if(prev and prev.next): prev.next = prev.next.next def printList(self): temp = self.head while temp: print(temp.data) temp = temp.next lst = LinkedList() lst.insertLast(99) lst.insertLast(88) lst.insertLast(45) lst.insertIndex(7777,-1) lst.insertIndex(3333,2) print() lst.printList() lst.deleteIndex(3) print() lst.printList()

Sortering


Byta plats på 2 Noder/länkar i listan handlar om att flytta pekarna, så att länkarna helt enkelt kommer i omvänd ordning. Man kan lätt bli tokig på hur pekarna ska flyttas, trots att det borde vara rätt så enkelt. Men, säg att vi döper 3 konsekutiva länkar till a, b, a.



Det normala är då

a.next = b
b.next = c

dvs

(a.next, b.next) = (b, c)


Det vi vill åstadkomma här, om vi vill byta plats på a och b, är alltså nedan (man får inte glömma ändra head -pekaren om det är första elementet som swappas!)



a.next = c
b.next = a

dvs 

(a.next, b.next) = (c, a)


Sorteringen görs enligt konceptet bubbelsort, fast i nedan loop är "färdigsorterat" -flaggan styrd på ett annat sätt om du tittar noga. Det är dock samma koncept, dvs vi håller på tills vi är färdiga!)
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def insertFirst(self, data): temp = self.head self.head = Node(data) self.head.next = temp def insertLast(self, data): temp = self.head if(temp == None): self.insertFirst(data) else: while temp.next: temp = temp.next temp.next = Node(data) def insertIndex(self, data, index): i = 0 prev = temp = self.head if(temp==None or index<=0): self.insertFirst(data) else: while(temp and i < index): prev = temp temp = temp.next i = i + 1 if(temp): ny = Node(data) prev.next = ny ny.next = temp else: self.insertLast(data) def deleteIndex(self, index): i = 0 prev = temp = self.head if(self.head!=None and index==0): self.head = self.head.next else: while(temp and i < index): prev = temp temp = temp.next i = i + 1 if(prev and prev.next): prev.next = prev.next.next def sort(self): sorted = False while(not sorted): sorted = True i = 0 prev = temp = self.head while(temp): if(temp and temp.next): if(temp.data > temp.next.data): sorted = False a = self.head b = temp.next c = temp.next.next if (i==0): a = self.head self.head = b else: a = prev.next prev.next = b (a.next,b.next)=(c,a) i = i + 1 prev = temp temp=temp.next def printList(self): temp = self.head while temp: print(temp.data) temp = temp.next lst = LinkedList() lst.insertLast(1) lst.insertLast(7) lst.insertLast(6) lst.insertLast(50) lst.insertLast(400) lst.insertLast(3) lst.insertLast(1) lst.sort() print() lst.printList()

find()


Slutligen kan vi implementera find. Vi gör samtidigt en liten ändring i print -funktionen, så att man, som frivilligt argument, kan lägga till en referens till en nod inne i listan (dvs en annan än head). Så vi kan leta reda på en punkt i listan med find() och sedan skriva ut listan därifrån. Se koden.
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def insertFirst(self, data): temp = self.head self.head = Node(data) self.head.next = temp def insertLast(self, data): temp = self.head if(temp == None): self.insertFirst(data) else: while temp.next: temp = temp.next temp.next = Node(data) def insertIndex(self, data, index): i = 0 prev = temp = self.head if(temp==None or index<=0): self.insertFirst(data) else: while(temp and i < index): prev = temp temp = temp.next i = i + 1 if(temp): ny = Node(data) prev.next = ny ny.next = temp else: self.insertLast(data) def deleteIndex(self, index): i = 0 prev = temp = self.head if(self.head!=None and index==0): self.head = self.head.next else: while(temp and i < index): prev = temp temp = temp.next i = i + 1 if(prev and prev.next): prev.next = prev.next.next def find(self, d): temp = self.head while(temp): if(temp.data == d): return(temp) temp = temp.next def sort(self): sorted = False while(not sorted): sorted = True i = 0 prev = temp = self.head while(temp): if(temp and temp.next): if(temp.data > temp.next.data): sorted = False a = self.head b = temp.next c = temp.next.next if (i==0): a = self.head self.head = b else: a = prev.next prev.next = b (a.next,b.next)=(c,a) i = i + 1 prev = temp temp=temp.next def printList(self, temp=None): if(temp==None): temp = self.head while temp: print(temp.data) temp = temp.next lst = LinkedList() lst.insertLast(1) lst.insertLast(7) lst.insertLast(6) lst.insertLast(50) lst.insertLast(400) lst.insertLast(3) lst.insertLast(1) lst.sort() node = lst.find(6) lst.printList(node)
15.25092124939 ms