python实现双链表

本文实例为大家分享了python实现双链表的具体代码，供大家参考，具体内容如下

实现双链表需要注意的地方

1、如何插入元素，考虑特殊情况：头节点位置，尾节点位置；一般情况：中间位置
2、如何删除元素，考虑特殊情况：头结点位置，尾节点位置；一般情况：中间位置

代码实现

1.构造节点的类和链表类

class Node:
? ? def __init__(self, data):
? ? ? ? self.data = data
? ? ? ? self.next = None
? ? ? ? self.previous = None


class DoubleLinkList:
? ? '''双链表'''

? ? def __init__(self, node=None):
? ? ? ? self._head = node

以下方法均在链表类中实现

2. 判断链表是否为空

def is_empty(self):
? ? ? ? return self._head is None

3. 输出链表的长度

def length(self):
? ? ? ? count = 0
? ? ? ? if self.is_empty():
? ? ? ? ? ? return count
? ? ? ? else:
? ? ? ? ? ? current = self._head
? ? ? ? ? ? while current is not None:
? ? ? ? ? ? ? ? count += 1
? ? ? ? ? ? ? ? current = current.next
? ? ? ? return count

4. 遍历链表

def travel(self):
? ? ? ? current = self._head
? ? ? ? while current is not None:
? ? ? ? ? ? print("{0}".format(current.data), end=" ")
? ? ? ? ? ? current = current.next
? ? ? ? print("")

5.头插法增加新元素

def add(self, item):
? ? ? ? node = Node(item)

? ? ? ? # 如果链表为空，让头指针指向当前节点
? ? ? ? if self.is_empty():
? ? ? ? ? ? self._head = node

? ? ? ? # 注意插入的顺序，
? ? ? ? else:
? ? ? ? ? ? node.next = self._head
? ? ? ? ? ? self._head.previous = node
? ? ? ? ? ? self._head = node

6. 尾插法增加新元素

def append(self, item):
? ? ? ? node = Node(item)

? ? ? ? # 如果链表为空，则直接让头指针指向该节点
? ? ? ? if self.is_empty():
? ? ? ? ? ? self._head = node

? ? ? ? # 需要找到尾节点，然后让尾节点的与新的节点进行连接
? ? ? ? else:
? ? ? ? ? ? current = self._head
? ? ? ? ? ? while current.next is not None:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? ? ? current.next = node
? ? ? ? ? ? node.previous = current

7. 查找元素是否存在链表中

def search(self, item):
? ? ? ? current = self._head
? ? ? ? found = False
? ? ? ? while current is not None and not found:
? ? ? ? ? ? if current.data == item:
? ? ? ? ? ? ? ? found = True
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? return found

8. 在某个位置中插入元素

def insert(self, item, pos):

? ? ? ? # 特殊位置，在第一个位置的时候，头插法
? ? ? ? if pos <= 0:
? ? ? ? ? ? self.add(item)

? ? ? ? # 在尾部的时候，使用尾插法
? ? ? ? elif pos > self.length() - 1:
? ? ? ? ? ? self.append(item)

? ? ? ? # 中间位置
? ? ? ? else:
? ? ? ? ? ? node = Node(item)
? ? ? ? ? ? current = self._head
? ? ? ? ? ? count = 0
? ? ? ? ? ? while count < pos - 1:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? ? ? ? ? count += 1

? ? ? ? ? ? # 找到了要插入位置的前驱之后，进行如下操作
? ? ? ? ? ? node.previous = current
? ? ? ? ? ? node.next = current.next
? ? ? ? ? ? current.next.previous = node
? ? ? ? ? ? current.next = node

?# 换一个顺序也可以进行
def insert2(self, item, pos):
? ? ? ? if pos <= 0:
? ? ? ? ? ? self.add(item)
? ? ? ? elif pos > self.length() - 1:
? ? ? ? ? ? self.append(item)
? ? ? ? else:
? ? ? ? ? ? node = Node(item)
? ? ? ? ? ? current = self._head
? ? ? ? ? ? count = 0
? ? ? ? ? ? while count < pos:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? ? ? ? ? count += 1

? ? ? ? ? ? node.next = current
? ? ? ? ? ? node.previous = current.previous
? ? ? ? ? ? current.previous.next = node
? ? ? ? ? ? current.previous = node

9. 删除元素

def remove(self, item):
? ? ? ? current = self._head
? ? ? ? if self.is_empty():
? ? ? ? ? ? return
? ? ? ? elif current.data == item:
? ? ? ? ? ? # 第一个节点就是目标节点，那么需要将下一个节点的前驱改为None 然后再将head指向下一个节点
? ? ? ? ? ? current.next.previous = None
? ? ? ? ? ? self._head = current.next
? ? ? ? else:

? ? ? ? ? ? # 找到要删除的元素节点
? ? ? ? ? ? while current is not None and current.data != item:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? ? ? if current is None:
? ? ? ? ? ? ? ? print("not found {0}".format(item))

? ? ? ? ? ? # 如果尾节点是目标节点，让前驱节点指向None
? ? ? ? ? ? elif current.next is None:
? ? ? ? ? ? ? ? current.previous.next = None

? ? ? ? ? ? # 中间位置，因为是双链表，可以用前驱指针操作
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? current.previous.next = current.next
? ? ? ? ? ? ? ? current.next.previous = current.previous

# 第二种写法
? ? def remove2(self, item):
? ? ? ? """删除元素"""
? ? ? ? if self.is_empty():
? ? ? ? ? ? return
? ? ? ? else:
? ? ? ? ? ? cur = self._head
? ? ? ? ? ? if cur.data == item:
? ? ? ? ? ? ? ? # 如果首节点的元素即是要删除的元素
? ? ? ? ? ? ? ? if cur.next is None:
? ? ? ? ? ? ? ? ? ? # 如果链表只有这一个节点
? ? ? ? ? ? ? ? ? ? self._head = None
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? # 将第二个节点的prev设置为None
? ? ? ? ? ? ? ? ? ? cur.next.prev = None
? ? ? ? ? ? ? ? ? ? # 将_head指向第二个节点
? ? ? ? ? ? ? ? ? ? self._head = cur.next
? ? ? ? ? ? ? ? return
? ? ? ? ? ? while cur is not None:
? ? ? ? ? ? ? ? if cur.data == item:
? ? ? ? ? ? ? ? ? ? # 将cur的前一个节点的next指向cur的后一个节点
? ? ? ? ? ? ? ? ? ? cur.prev.next = cur.next
? ? ? ? ? ? ? ? ? ? # 将cur的后一个节点的prev指向cur的前一个节点
? ? ? ? ? ? ? ? ? ? cur.next.prev = cur.prev
? ? ? ? ? ? ? ? ? ? break
? ? ? ? ? ? ? ? cur = cur.next

10. 演示

my_list = DoubleLinkList()


print("add操作")
my_list.add(98)
my_list.add(99)
my_list.add(100)
my_list.travel()
print("{:#^50}".format(""))

print("append操作")
my_list.append(86)
my_list.append(85)
my_list.append(88)
my_list.travel()
print("{:#^50}".format(""))

print("insert2操作")
my_list.insert2(66, 3)
my_list.insert2(77, 0)
my_list.insert2(55, 10)
my_list.travel()
print("{:#^50}".format(""))


print("insert操作")
my_list.insert(90, 4)
my_list.insert(123, 5)
my_list.travel()
print("{:#^50}".format(""))

print("search操作")
print(my_list.search(100))
print(my_list.search(1998))
print("{:#^50}".format(""))

print("remove操作")
my_list.remove(56)
my_list.remove(123)
my_list.remove(77)
my_list.remove(55)
my_list.travel()
print("{:#^50}".format(""))

print("remove2操作")
my_list.travel()
my_list.remove2(100)
my_list.remove2(99)
my_list.remove2(98)
my_list.travel()

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

查看更多关于python实现双链表的详细内容...