基于python实现双向链表

目录 一、构建链表节点 二、实现链表类 三、测试逻辑

在一些面试或者力扣题中都要求用双向链表来实现，下面是基于python的双向链表实现。

一、构建链表节点

class Node:

? ? def __init__(self, key, value):
? ? ? ? """
? ? ? ? 初始化方法
? ? ? ? :param key:
? ? ? ? :param value:
? ? ? ? """
? ? ? ? self.key = key
? ? ? ? self.value = value
? ? ? ? self.prev = None
? ? ? ? self.next = None

? ? def __str__(self):
? ? ? ? val = '{%s: %s}' % (self.key, self.value)
? ? ? ? return val

? ? def __repr__(self):
? ? ? ? val = '{%s: %s}' % (self.key, self.value)
? ? ? ? return val

除了一些节点的基础属性外还有__str__方法用于自定义print(node)的字符串描述(类似Java的toString())，__repr__用于自定义直接调用Node类时的字符串描述

二、实现链表类

具体逻辑主要包括头部添加、尾部添加、头部删除、尾部删除和任意节点的删除，所有对双向链表的操作都是基于这几个方法实现的，具体流程都写在注释中了

class DoubleLinkedList:

? ? def __init__(self, capacity=0xffffffff):
? ? ? ? """
? ? ? ? 双向链表
? ? ? ? :param capacity: 链表容量 初始化为int的最大值2^32-1
? ? ? ? :return:
? ? ? ? """
? ? ? ? self.capacity = capacity
? ? ? ? self.size = 0
? ? ? ? self.head = None
? ? ? ? self.tail = None

? ? def __add_head(self, node):
? ? ? ? """
? ? ? ? 向链表头部添加节点
? ? ? ? ? ? 头部节点不存在 新添加节点为头部和尾部节点
? ? ? ? ? ? 头部节点已存在 新添加的节点为新的头部节点
? ? ? ? :param node: 要添加的节点
? ? ? ? :return: 已添加的节点
? ? ? ? """
? ? ? ? # 头部节点为空
? ? ? ? if not self.head:
? ? ? ? ? ? self.head = node
? ? ? ? ? ? self.tail = node
? ? ? ? ? ? self.head.next = None
? ? ? ? ? ? self.tail.prev = None
? ? ? ? # 头部节点不为空
? ? ? ? else:
? ? ? ? ? ? node.next = self.head
? ? ? ? ? ? self.head.prev = node
? ? ? ? ? ? self.head = node
? ? ? ? ? ? self.head.prev = None
? ? ? ? self.size += 1

? ? ? ? return node

? ? def __add_tail(self, node):
? ? ? ? """
? ? ? ? 向链表尾部添加节点
? ? ? ? ? ? 尾部节点不存在 新添加的节点为头部和尾部节点
? ? ? ? ? ? 尾部节点已存在 新添加的节点为新的尾部节点
? ? ? ? :param node: 添加的节点
? ? ? ? :return: 已添加的节点
? ? ? ? """
? ? ? ? # 尾部节点为空
? ? ? ? if not self.tail:
? ? ? ? ? ? self.tail = node
? ? ? ? ? ? self.head = node
? ? ? ? ? ? self.head.next = None
? ? ? ? ? ? self.tail.prev = None
? ? ? ? # 尾部节点不为空
? ? ? ? else:
? ? ? ? ? ? node.prev = self.tail
? ? ? ? ? ? self.tail.next = node
? ? ? ? ? ? self.tail = node
? ? ? ? ? ? self.tail.next = None
? ? ? ? self.size += 1

? ? ? ? return node

? ? def __remove_head(self):
? ? ? ? """
? ? ? ? 删除头部节点
? ? ? ? ? ? 头部节点不存在 返回None
? ? ? ? ? ? 头部节点已存在 判断链表节点数量 删除头部节点
? ? ? ? :return: 头部节点
? ? ? ? """
? ? ? ? # 头部节点不存在
? ? ? ? if not self.head:
? ? ? ? ? ? return None

? ? ? ? # 链表至少存在两个节点
? ? ? ? head = self.head
? ? ? ? if head.next:
? ? ? ? ? ? head.next.prev = None
? ? ? ? ? ? self.head = head.next
? ? ? ? # 只存在头部节点
? ? ? ? else:
? ? ? ? ? ? self.head = self.tail = None
? ? ? ? self.size -= 1

? ? ? ? return head

? ? def __remove_tail(self):
? ? ? ? """
? ? ? ? 删除尾部节点
? ? ? ? ? ? 尾部节点不存在 返回None
? ? ? ? ? ? 尾部节点已存在 判断链表节点数量 删除尾部节点
? ? ? ? :return: 尾部节点
? ? ? ? """
? ? ? ? # 尾部节点不存在
? ? ? ? if not self.tail:
? ? ? ? ? ? return None

? ? ? ? # 链表至少存在两个节点
? ? ? ? tail = self.tail
? ? ? ? if tail.prev:
? ? ? ? ? ? tail.prev.next = None
? ? ? ? ? ? self.tail = tail.prev
? ? ? ? # 只存在尾部节点
? ? ? ? else:
? ? ? ? ? ? self.head = self.tail = None
? ? ? ? self.size -= 1

? ? ? ? return tail

? ? def __remove(self, node):
? ? ? ? """
? ? ? ? 删除任意节点
? ? ? ? ? ? 被删除的节点不存在 默认删除尾部节点
? ? ? ? ? ? 删除头部节点
? ? ? ? ? ? 删除尾部节点
? ? ? ? ? ? 删除其他节点
? ? ? ? :param node: 被删除的节点
? ? ? ? :return: 被删除的节点
? ? ? ? """
? ? ? ? # 被删除的节点不存在
? ? ? ? if not node:
? ? ? ? ? ? node = self.tail

? ? ? ? # 删除的是头部节点
? ? ? ? if node == self.head:
? ? ? ? ? ? self.__remove_head()
? ? ? ? # 删除的是尾部节点
? ? ? ? elif node == self.tail:
? ? ? ? ? ? self.__remove_tail()
? ? ? ? # 删除的既不是头部也不是尾部节点
? ? ? ? else:
? ? ? ? ? ? node.next.prev = node.prev
? ? ? ? ? ? node.prev.next = node.next
? ? ? ? ? ? self.size -= 1

? ? ? ? return node

? ? def pop(self):
? ? ? ? """
? ? ? ? 弹出头部节点
? ? ? ? :return: 头部节点
? ? ? ? """
? ? ? ? return self.__remove_head()

? ? def append(self, node):
? ? ? ? """
? ? ? ? 添加尾部节点
? ? ? ? :param node: 待追加的节点
? ? ? ? :return: 尾部节点
? ? ? ? """
? ? ? ? return self.__add_tail(node)

? ? def append_front(self, node):
? ? ? ? """
? ? ? ? 添加头部节点
? ? ? ? :param node: 待添加的节点
? ? ? ? :return: 已添加的节点
? ? ? ? """
? ? ? ? return self.__add_head(node)

? ? def remove(self, node=None):
? ? ? ? """
? ? ? ? 删除任意节点
? ? ? ? :param node: 待删除的节点
? ? ? ? :return: 已删除的节点
? ? ? ? """
? ? ? ? return self.__remove(node)

? ? def print(self):
? ? ? ? """
? ? ? ? 打印当前链表
? ? ? ? :return:
? ? ? ? """
? ? ? ? node = self.head
? ? ? ? line = ''
? ? ? ? while node:
? ? ? ? ? ? line += '%s' % node
? ? ? ? ? ? node = node.next
? ? ? ? ? ? if node:
? ? ? ? ? ? ? ? line += '=>'
? ? ? ? print(line)

三、测试逻辑

if __name__ == '__main__':
? ? double_linked_list = DoubleLinkedList(10)
? ? nodes = []
? ? # 构建十个节点的双向列表
? ? for i in range(10):
? ? ? ? node_item = Node(i, i)
? ? ? ? nodes.append(node_item)

? ? double_linked_list.append(nodes[0])
? ? double_linked_list.print()
? ? double_linked_list.append(nodes[1])
? ? double_linked_list.print()
? ? double_linked_list.pop()
? ? double_linked_list.print()
? ? double_linked_list.append_front(nodes[2])
? ? double_linked_list.print()
? ? double_linked_list.append(nodes[3])
? ? double_linked_list.print()
? ? double_linked_list.remove(nodes[3])
? ? double_linked_list.print()
? ? double_linked_list.remove()
? ? double_linked_list.print()

测试结果:

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

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