數(shù)據(jù)結(jié)構(gòu)在編程世界中一直是非常重要的一環(huán)盯串，不管是開發(fā)還是算法抚垄，哪怕是單純?yōu)榱嗣嬖嚕瑪?shù)據(jù)結(jié)構(gòu)都是必修課氮采，今天我們介紹鏈表中的一種——雙向鏈表的代碼實現(xiàn)殷绍。
好了，話不多說直接上代碼鹊漠。
雙向鏈表
首先主到，我們定義一個節(jié)點類：Node
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
def getData(self):
return self.data
def setData(self, data):
self.data = data
def getNext(self):
return self.next
def getPrev(self):
return self.prev
好，我們定義了節(jié)點類躯概，并實現(xiàn)了獲取登钥、修改節(jié)點數(shù)據(jù)、獲取上一個/下一個節(jié)點的方法楞陷。
通過node = Node(10)就可以實例化一個節(jié)點啦怔鳖。
接下來我們來定義鏈表類：
class TwoWayList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
好茉唉，我們定義了一個鏈表類固蛾，并設(shè)置三個屬性结执，head表示頭節(jié)點，tail表示尾節(jié)點艾凯，length表示鏈表長度献幔，接下來，我們給鏈表類添加一些方法趾诗。
- 判斷鏈表是否為空：
def isEmpty(self):
return self.head == None
- 在鏈表尾部添加節(jié)點：
def append(self, item):
if self.length == 0:
node = Node(item)
self.head = node
self.tail = node
self.length = 1
return
node = Node(item)
tail = self.tail
tail.next = node
node.prev = tail
self.tail = node
self.length += 1
添加節(jié)點的時候蜡感，我們首先要判斷鏈表是否為空，另外要注意給原本的尾節(jié)點設(shè)置next屬性恃泪，新的尾節(jié)點設(shè)置prev屬性郑兴，更新鏈表的tail和length屬性。
- 鏈表中插入節(jié)點：
def insert(self, index, item):
length = self.length
if (index<0 and abs(index)>length) or (index>0 and index>=length):
return False
if index < 0:
index = index + length
if index == 0:
node = Node(item)
if self.head != None:
self.head.prev = node
else:
self.tail = node
node.next = self.head
self.head = node
self.length += 1
return True
if index == length - 1:
return self.append(item)
node1 = self.head
for i in range(0, index):
node1 = node1.next
node2 = node1.next
node = Node(item)
node.prex = node1
node.next = node2
node1.next = node
node2.prev = node
self.length += 1
return True
插入節(jié)點時候贝乎，我們參數(shù)為下標index和數(shù)據(jù)item情连，我們默認在指定下標的后面插入新節(jié)點。
在這里我們同樣要特殊考慮頭節(jié)點和尾結(jié)點的情況览效。
在執(zhí)行插入時先將新節(jié)點的next却舀、prev屬性指向相應(yīng)節(jié)點，在將前后節(jié)點的next和prev指向新節(jié)點锤灿，同時注意更新鏈表的length屬性挽拔。
- 根據(jù)節(jié)點數(shù)據(jù)獲取鏈表上的節(jié)點
def get(self, data):
node = self.head
for i in range(self.length):
if node.data == data:
return node
else:
node = node.next
else:
return False
- 根據(jù)下標獲取鏈表上的節(jié)點
def getByIndex(self, index):
if index >= self.length:
return False
if index == 0:
return self.head
now = self.head
for i in range(self.length):
if i == index:
return now
now = now.next
- 更新指定下標節(jié)點的數(shù)據(jù)
def setData(self, index, data):
if index >= self.length:
return False
if index == 0:
self.head.data = data
now = self.head
for i in range(self.length):
if i == index:
now.data = data
return True
now = now.next
- 刪除指定下標的節(jié)點
def remove(self, index):
if index >= self.length:
return False
if index == 0:
self.head = self.head.next
if self.length != 1:
self.head.prev = None
self.length -= 1
return True
if index == self.length-1:
self.tail = self.tail.prev
self.tail.next = None
self.length -= 1
return True
now = self.head
for i in range(self.length):
if i == index:
now.next.prev = now.prev
now.prev.next = now.next
self.length -= 1
return True
now = now.next
注意要更新length屬性，如果刪除頭節(jié)點還要更新head屬性但校，如果刪除尾結(jié)點要更新tail屬性螃诅。
- 鏈表翻轉(zhuǎn)
def reverse(self):
now = self.head
last = None
for i in range(self.length):
last = now
now = now.next
tmp = last.prev
last.prev = last.next
last.next = tmp
tmp = self.head
self.head = self.tail
self.tail = tmp
return True
鏈表翻轉(zhuǎn)我們不光要更新tail和head屬性，還要將每一個節(jié)點上的next和prev屬性調(diào)換始腾。
- 清空鏈表
def clear(self):
self.head = None
self.tail = None
self.length = 0
- 實現(xiàn)鏈表類的str方法州刽，定義print()函數(shù)打印鏈表的方式
def __str__(self):
string = ''
node = self.head
for i in range(self.length):
string += str(node.data) + '/'
node = node.next
return string
這里我們讓print()函數(shù)打印鏈表時，從頭節(jié)點開始依次打印每個節(jié)點的數(shù)據(jù)浪箭，并用/符號分割穗椅。
好啦，一個雙向鏈表我們就定義好了奶栖，并實現(xiàn)了一些操作鏈表的方法匹表，我們了來測試一下我們定義的鏈表吧~
li = TwoWayList()
li.isEmpty()
li.insert(0, 1)
li.getByIndex(0)
li.remove(0)
print(li)
li.append(1)
print(li)
li.append(2)
print(li)
li.append(4)
print(li)
li.insert(2,3)
print(li)
li.insert(3,4)
print(li)
li.remove(2)
print(li)
li.setData(2,10)
print(li)
li.reverse()
print(li)
print(li.get(2).data)
print(li.getByIndex(1).data)
執(zhí)行上面的操作，檢查一下你的輸出吧宣鄙，你還有什么關(guān)于鏈表的應(yīng)用留言告訴我把袍镀。
