python 鏈表
鏈表是一系列數(shù)據(jù)元素，通過鏈接連接在一起。每個(gè)數(shù)據(jù)元素都以指針的形式包含到另一個(gè)數(shù)據(jù)元素的連接。python在其標(biāo)準(zhǔn)庫中沒有鏈接列表。我們使用前一章討論過的節(jié)點(diǎn)概念來實(shí)現(xiàn)鏈表的概念。我們已經(jīng)看到了我們?nèi)绾蝿?chuàng)建節(jié)點(diǎn)類以及如何遍歷節(jié)點(diǎn)的元素。在本章中，我們將研究被稱為單鏈表的鏈表的類型。在這種類型的數(shù)據(jù)結(jié)構(gòu)中，任何兩個(gè)數(shù)據(jù)元素之間只有一個(gè)鏈接。我們創(chuàng)建這樣一個(gè)列表并創(chuàng)建其他方法來插入，更新和從列表中移除元素。
創(chuàng)建鏈接列表
鏈表通過使用我們在上一章中研究的節(jié)點(diǎn)類創(chuàng)建。我們創(chuàng)建一個(gè)node對象并創(chuàng)建另一個(gè)類來使用這個(gè)ode對象。我們通過節(jié)點(diǎn)對象傳遞適當(dāng)?shù)闹祦碇赶蛳乱粋€(gè)數(shù)據(jù)元素。下面的程序使用三個(gè)數(shù)據(jù)元素創(chuàng)建鏈接列表。在下一節(jié)中，我們將看到如何遍歷鏈表。
class node:
def __init__(self, dataval=none):
self.dataval = dataval
self.nextval = none
class slinkedlist:
def __init__(self):
self.headval = none
list1 = slinkedlist()
list1.headval = node("mon")
e2 = node("tue")
e3 = node("wed")
# link first node to second node
list1.headval.nextval = e2
# link second node to third node
e2.nextval = e3
遍歷鏈接列表
從第一個(gè)數(shù)據(jù)元素開始，單向鏈表只能在forwrad方向上遍歷。我們只需通過將下一個(gè)節(jié)點(diǎn)的指針指向當(dāng)前數(shù)據(jù)元素來打印下一個(gè)數(shù)據(jù)元素的值。
class node:
def __init__(self, dataval=none):
self.dataval = dataval
self.nextval = none
class slinkedlist:
def __init__(self):
self.headval = none
def listprint(self):
printval = self.headval
while printval is not none:
print (printval.dataval)
printval = printval.nextval
list = slinkedlist()
list.headval = node("mon")
e2 = node("tue")
e3 = node("wed")
# link first node to second node
list.headval.nextval = e2
# link second node to third node
e2.nextval = e3
list.listprint()
當(dāng)上面的代碼被執(zhí)行時(shí)，它會產(chǎn)生以下結(jié)果：
mon tue wed
插入鏈接列表中
在鏈表中插入元素涉及將指針從現(xiàn)有節(jié)點(diǎn)重新分配給新插入的節(jié)點(diǎn)。取決于新數(shù)據(jù)元素是在鏈表的開始位置還是在中間位置或末尾插入，我們有以下方案。
在鏈接列表的開頭插入
這涉及到將新數(shù)據(jù)節(jié)點(diǎn)的下一個(gè)指針指向鏈表的當(dāng)前頭部。因此，鏈表的當(dāng)前頭成為第二個(gè)數(shù)據(jù)元素，新節(jié)點(diǎn)成為鏈表的頭部。
class node:
def __init__(self, dataval=none):
self.dataval = dataval
self.nextval = none
class slinkedlist:
def __init__(self):
self.headval = none
# print the linked list
def listprint(self):
printval = self.headval
while printval is not none:
print (printval.dataval)
printval = printval.nextval
def atbegining(self,newdata):
newnode = node(newdata)
# update the new nodes next val to existing node
newnode.nextval = self.headval
self.headval = newnode
list = slinkedlist()
list.headval = node("mon")
e2 = node("tue")
e3 = node("wed")
list.headval.nextval = e2
e2.nextval = e3
list.atbegining("sun")
list.listprint()
當(dāng)上面的代碼被執(zhí)行時(shí)，它會產(chǎn)生以下結(jié)果：
sun mon tue wed
在鏈接列表的末尾插入
這包括將鏈表的當(dāng)前最后一個(gè)節(jié)點(diǎn)的下一個(gè)指針指向新的數(shù)據(jù)節(jié)點(diǎn)。因此鏈表的當(dāng)前最后一個(gè)節(jié)點(diǎn)成為倒數(shù)第二個(gè)數(shù)據(jù)節(jié)點(diǎn)，新節(jié)點(diǎn)成為鏈表的最后一個(gè)節(jié)點(diǎn)。
class node:
def __init__(self, dataval=none):
self.dataval = dataval
self.nextval = none
class slinkedlist:
def __init__(self):
self.headval = none
# function to add newnode
def atend(self, newdata):
newnode = node(newdata)
if self.headval is none:
self.headval = newnode
return
laste = self.headval
while(laste.nextval):
laste = laste.nextval
laste.nextval=newnode
# print the linked list
def listprint(self):
printval = self.headval
while printval is not none:
print (printval.dataval)
printval = printval.nextval
list = slinkedlist()
list.headval = node("mon")
e2 = node("tue")
e3 = node("wed")
list.headval.nextval = e2
e2.nextval = e3
list.atend("thu")
list.listprint()
當(dāng)上面的代碼被執(zhí)行時(shí)，它會產(chǎn)生以下結(jié)果：
mon tue wed thu
插入兩個(gè)數(shù)據(jù)節(jié)點(diǎn)之間
這涉及到將指定節(jié)點(diǎn)的指針指向新節(jié)點(diǎn)。這可以通過傳入新節(jié)點(diǎn)和現(xiàn)有節(jié)點(diǎn)，然后插入新節(jié)點(diǎn)。所以我們定義一個(gè)額外的類，將新節(jié)點(diǎn)的下一個(gè)指針改變?yōu)橹虚g節(jié)點(diǎn)的下一個(gè)指針。然后將新節(jié)點(diǎn)分配給中間節(jié)點(diǎn)的下一個(gè)指針。
class node:
def __init__(self, dataval=none):
self.dataval = dataval
self.nextval = none
class slinkedlist:
def __init__(self):
self.headval = none
# function to add node
def inbetween(self,middle_node,newdata):
if middle_node is none:
print("the mentioned node is absent")
return
newnode = node(newdata)
newnode.nextval = middle_node.nextval
middle_node.nextval = newnode
# print the linked list
def listprint(self):
printval = self.headval
while printval is not none:
print (printval.dataval)
printval = printval.nextval
list = slinkedlist()
list.headval = node("mon")
e2 = node("tue")
e3 = node("thu")
list.headval.nextval = e2
e2.nextval = e3
list.inbetween(list.headval.nextval,"fri")
list.listprint()
當(dāng)上面的代碼被執(zhí)行時(shí)，它會產(chǎn)生以下結(jié)果：
mon tue fri thu
從喜好列表中刪除項(xiàng)目
我們可以使用該節(jié)點(diǎn)的密鑰刪除現(xiàn)有節(jié)點(diǎn)。在下面的程序中，我們找到要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。然后將該節(jié)點(diǎn)的下一個(gè)指針指向要?jiǎng)h除的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。
class node:
def __init__(self, data=none):
self.data = data
self.next = none
class slinkedlist:
def __init__(self):
self.head = none
def atbegining(self, data_in):
newnode = node(data_in)
newnode.next = self.head
self.head = newnode
# function to remove node
def removenode(self, removekey):
headval = self.head
if (headval is not none):
if (headval.data == removekey):
self.head = headval.next
headval = none
return
while (headval is not none):
if headval.data == removekey:
break
prev = headval
headval = headval.next
if (headval == none):
return
prev.next = headval.next
headval = none
def llistprint(self):
printval = self.head
while (printval):
print(printval.data),
printval = printval.next
llist = slinkedlist()
llist.atbegining("mon")
llist.atbegining("tue")
llist.atbegining("wed")
llist.atbegining("thu")
llist.removenode("tue")
llist.llistprint()
當(dāng)上面的代碼被執(zhí)行時(shí)，它會產(chǎn)生以下結(jié)果：
thu wed mon
Python基礎(chǔ)