DSA 链表类型
链表类型
链表有三种基本形式
- 单向链表
- 双向链表
- 循环链表
单向链表是最简单的链表类型。它占用的内存空间较少，因为每个节点只有一个指向下一个节点的地址，如下图所示。
双向链表的节点同时包含指向前一个节点和下一个节点的地址，如下图所示，因此占用的内存更多。但双向链表适合需要双向遍历列表的场景。
循环链表类似于单向或双向链表，但第一个节点（“头”）和最后一个节点（“尾”）相互连接。
在单向或双向链表中，我们可以通过检查链接是否为 null 来找到列表的开始和结束。但对于循环链表，在某些应用程序中需要更复杂的代码来显式检查开始和结束节点。
循环链表适用于需要连续循环遍历的列表。
下图是一个单向循环链表的例子
下图是一个双向循环链表的例子
注意：您需要的链表类型取决于您要解决的问题。
链表实现
以下是基本实现的
- 单向链表
- 双向链表
- 循环单向链表
- 循环双向链表
下一页将介绍链表可以执行的不同操作。
1. 单向链表实现
以下是此单向链表的实现
示例
Python 中的基本单向链表
(这是与上一页底部相同的示例。)
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.next = node3
node3.next = node4
currentNode = node1
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")2. 双向链表实现
以下是此双向链表的实现
示例
Python 中的基本双向链表
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3
print("\nTraversing forward:")
currentNode = node1
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
print("\nTraversing backward:")
currentNode = node4
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev
print("null")3. 循环单向链表实现
以下是此循环单向链表的实现
示例
Python 中的基本循环单向链表
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1
currentNode = node1
startNode = node1
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
while currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("...")第 14 行：这使得单向列表成为循环的。
第 17 行：程序通过此方式知道何时停止，以便它只遍历列表一次。
4. 循环双向链表实现
以下是此循环双向链表的实现
示例
Python 中的基本循环双向链表
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node1.prev = node4
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3
node4.next = node1
print("\nTraversing forward:")
currentNode = node1
startNode = node1
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
while currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("...")
print("\nTraversing backward:")
currentNode = node4
startNode = node4
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev
while currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev
print("...")第 13 行和第 22 行：这些链接使双向链表成为循环的。
第 26 行：程序通过此方式知道何时停止，以便它只遍历列表一次。
