一、鏈表的定義

鏈表：其中的各對象按線性順序排列，其順序有各個對象里的指針決定，為動態(tài)集合提供了一種簡單而靈活的表示方法。

雙向鏈表：每一個元素都是一個對象，每個對象有一個關(guān)鍵字key和兩個指針：next和prev。如果元素x沒有前驅(qū)，所以是鏈表的第一個元素head,若元素x沒有后繼，因此是鏈表的最后一個元素tail。如果L.hand=NIL,則鏈表為空。

二、代碼實現(xiàn)

#首先定義節(jié)點類Node

class LinkNode(object):

#1. __init__初始化結(jié)點信息

def __init__(self, data, pnext = None):

'''

data:節(jié)點保存的數(shù)據(jù)

'''

self.data = data

self._next = pnext

#2. 用于定義Node的字符輸出

def __repr__(self):

'''

用于定義Node的字符輸出，

print為輸出data

'''

return str(self.data)

#初始化鏈表的類

class LinkList(object):

#1. 初始化鏈表

def __init__(self):

#屬性：鏈表頭head,鏈表長度length

self.head = None

self.length = 0

#2. 鏈表初始化函數(shù)，尾插法，插入data

def initlist_tail(self, data):

#創(chuàng)建頭結(jié)點，其實是第一個有值節(jié)點

self.head = LinkNode(data[0])

pnext = self.head

for i in data[1:]:

node = LinkNode(i)

pnext .next = node

pnext = pnext .next

#3. 判斷鏈表是否為空

def isEmpty(self):

return (self.length == 0)

#4. 增加一個節(jié)點（在鏈為添加）

def append(self, dataOrNode):

'''在鏈表尾添加'''

item = None

if isinstance(dataOrNode, LinkNode):

item = dataOrNode

else:

item = Node(dataOrNode)

if not self.head:

self.head = item

self.length += 1

else:

node = self.head

while node._next:

node = node._next

node._next = item

self.length += 1

#5. 刪除一個節(jié)點： delete()

def delete(self, index):

'''

刪除一個節(jié)點，需要把鏈表長度減一

'''

if self.isEmpty():

print("this linked list is empty.")

return

if index < 0 or index >= self.length:

print('error: out of index')

return

'''

要注意刪除第一個節(jié)點的情況

'''

if index == 0:

self.head = self.head._next

self.length -= 1

return

'''

prev為保存前導(dǎo)節(jié)點

node為保存當(dāng)前節(jié)點

'''

j = 0

node = self.head

prev = self.head

while node._next and j < index:

prev = node

node = node._next

j += 1

if j == index:

prev.next = node._next

self.length -= 1

#6. 修改一個節(jié)點： update()

def update(self, index, data):

'''修改一個節(jié)點'''

if self.isEmpty() or index < 0 or index >= self.length:

print("error: out of index")

return

j = 0

node = self.head

while node.next and j < index:

node = node._next

j += 1

if j == index:

node.data = data

#7. 查找一個節(jié)點: getItem()

def getItem(self, index):

'''查找節(jié)點'''

if self.isEmpty() or index < 0 or index >= self.length:

print("error: out of index")

return

j = 0

node = self.head

while node._next and j < index:

node = node._next

j += 1

return node.data

#8. 查找一個節(jié)點的索引： getIndex()

def getIndex(self, data):

'''查找索引'''

j = 0

if self.isEmpty():

print("this linked list is empty")

return

node = self.head

while node:

if node.data == data:

return j

node = node._next

j += 1

if j == self.length:

print("%s not found" %str(data))

return

#9. 查找一個節(jié)點：insert()

def insert(self, index, dataOrNode):

if self.isEmpty():

print("this linked list is empty")

return

if index < 0 or index >= self.length:

print("error: out of index")

return

item = None

if isinstance(dataOrNode, Node):

item = dataOrNode

else:

item = Node(dataOrNode)

if index == 0:

item._next = self.head

self.head = item

self.length += 1

return

j = 0

node = self.head

prev = self.head

while node._next and j < index:

prev = node

node = node._next

j += 1

if j == index:

item._next = node

prev._next = item

self.length += 1

#10. 清空鏈表

def clear(self):

'''清空鏈表'''

self.head = None

self.length = 0

#11. 取鏈表長度

def getLength(self):

return self.length

#12. 在索引值為 index 的結(jié)點后插入結(jié)點key

def insertElem(self, key, index):

pnext= self.head

j = 1

while pnext and j < index:

pnext = pnext.next

j += 1

if(pnext == 0 or j > index): #若出錯則退出

exit(0)

print('insert error')

node = LinkNode(key)

node.next = pnext.next

pnext.next = node

print('inserted LinkList:')

self.ReadList()

#13. 刪除第 index個 結(jié)點后的那一個節(jié)點

def deleteElem(self, index):

pnext = self.head

j = 1

while pnext and j < index:

pnext = pnext.next

j += 1

if(pnext == 0 or j > index): #若出錯則退出

exit(0)

print('insert error')

q = pnext.next

pnext.next = q.next

print('deleted LinkList:')

self.ReadList()

#14. 鏈表逆序

def reverseList(self):

pnext = self.head

def __repr__(self):

if self.isEmpty():

return "empty chain table"

node = self.head

nlist = ''

while node:

nlist += str(node.data) + ' '

node = node._next

return nlist

def __getitem__(self, ind):

if self.isEmpty() or ind < 0 or ind >= self.length:

print "error: out of index"

return

return self.getItem(ind)

def __setitem__(self, ind, val):

if self.isEmpty() or ind < 0 or ind >= self.length:

print "error: out of index"

return

self.update(ind, val)

def __len__(self):

return self.length

總結(jié)

以上是生活随笔為你收集整理的python3 链表_Python3链表实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。