Detta skapar en PDF som du sedan kan skriva ut. Du kan även spara ner PDFn och skriva ut senare.
Titel på utskriften?
Tack för ditt bidrag
Om vi kan använda det så lägger vi upp det på sidan. Nedan en länk till ditt bidrag om du vill spara det.
Spara som ...
Du sparar ditt skript under detta namn och kan sedan hämta tillbaka det med samma namn.
Läs in
Läs in ett tidigare sparat skript. Obs att du enbart kan läsa in skript i den webbläsare där du sparade skriptet. Vill du kunna läsa in och spara skript oberoende av webbläsare, så behöver du skaffa ett login (enkelt och gratis).
Skicka in bidrag
Föreslå rubrik
Beskriv vad din kod gör
Skapa kort länk
Använd en kort URL för att skicka länk till koden via SMS eller epost. När mottagaren klickar på länken, så öppnas denna webbsida, med din kod och din text. Länken rensas bort automatiskt om den inte används.
Rubrik (frivilligt)
Beskrivning (frivilligt)
Länk (kopiera hela)
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
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.
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.
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.
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!
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()
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()
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()
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)
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)