数据结构-双向链表（Python实现）
2019-07-21 本文已影响0人
绿萝呀
数据结构在编程世界中一直是非常重要的一环，不管是开发还是算法，哪怕是单纯为了面试，数据结构都是必修课，今天我们介绍链表中的一种——双向链表的代码实现。
好了，话不多说直接上代码。
双向链表
首先，我们定义一个节点类：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
好，我们定义了节点类，并实现了获取、修改节点数据、获取上一个/下一个节点的方法。
通过node = Node(10)就可以实例化一个节点啦。
接下来我们来定义链表类：
class TwoWayList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
好，我们定义了一个链表类，并设置三个属性，head表示头节点，tail表示尾节点，length表示链表长度，接下来，我们给链表类添加一些方法。
- 判断链表是否为空：
def isEmpty(self):
return self.head == None
- 在链表尾部添加节点：
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
添加节点的时候，我们首先要判断链表是否为空，另外要注意给原本的尾节点设置next属性，新的尾节点设置prev属性，更新链表的tail和length属性。
- 链表中插入节点：
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
插入节点时候，我们参数为下标index和数据item，我们默认在指定下标的后面插入新节点。
在这里我们同样要特殊考虑头节点和尾结点的情况。
在执行插入时先将新节点的next、prev属性指向相应节点，在将前后节点的next和prev指向新节点，同时注意更新链表的length属性。
- 根据节点数据获取链表上的节点
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
- 根据下标获取链表上的节点
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
- 更新指定下标节点的数据
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
- 删除指定下标的节点
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属性，如果删除头节点还要更新head属性，如果删除尾结点要更新tail属性。
- 链表翻转
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
链表翻转我们不光要更新tail和head属性，还要将每一个节点上的next和prev属性调换。
- 清空链表
def clear(self):
self.head = None
self.tail = None
self.length = 0
- 实现链表类的str方法，定义print()函数打印链表的方式
def __str__(self):
string = ''
node = self.head
for i in range(self.length):
string += str(node.data) + '/'
node = node.next
return string
这里我们让print()函数打印链表时，从头节点开始依次打印每个节点的数据，并用/符号分割。
好啦，一个双向链表我们就定义好了，并实现了一些操作链表的方法，我们了来测试一下我们定义的链表吧~
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)
执行上面的操作，检查一下你的输出吧，你还有什么关于链表的应用留言告诉我把。
