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 行：这是程序知道何时停止的方式，这样它只遍历列表一次。
