python 标准库并没有实现链表,所以我们得自己实现链表。
什么是链表
链表是计算机科学中最常用的数据结构之一。它也是最简单的结构之一，也是更高层结构（如堆栈、循环缓冲区和队列）的基础。
一般来说，列表是通过引用连接的单个数据元素的集合。C程序员知道这是指针。例如，数据元素可以由地址数据、地理数据、几何数据、路由信息或事务细节组成。通常，链接列表的每个元素都具有特定于列表的相同数据类型
单个列表元素称为节点。节点不同于顺序存储在内存中的数组。相反，它可能会在不同的内存段中找到它们，您可以通过跟踪从一个节点到下一个节点的指针找到这些内存段。通常使用nil元素标记列表的结尾，该元素由python等效的None表示。
链表类型
- 单链表
有两种列表-单链接列表和双链接列表。单个链接列表中的节点只指向列表中的下一个元素，而双链接列表中的节点也指向上一个节点。数据结构占用更多的空间，因为您需要一个额外的变量来存储链表的引用。
@单链列表
- 双链表
一个链表可以从头到尾遍历，而反向遍历则比较难。相反，双链接列表允许以相同的成本在两个方向上遍历节点，无论从哪个节点开始。此外，添加和删除节点以及拆分单个链接列表的步骤不超过两个。在双链接列表中，必须更改四个指针。（详情可见添加删除方法）
@双链表
这篇博文，我们将一步步建立自己的链表。首先，我们为节点创建一个对应的数据结构。其次，您将学习如何实现和使用一个单链接列表，最后是一个双链接列表。
Step 1: Node as a Data Structure
我们建立一个Node 的节点类。该类有两个属性变量存储数据的data和指向下一个节点的引用next。
-
__init_(): 初始化节点的方法 -
self.data: 储存在节点中的数据 -
self.next: 下个节点的引用 -
has_value(): 是否包含这个值的节点
# 1。__init_(): initialize the node with the data
# 2。self.data: the value stored in the node
# 3。self.next: the reference pointer to the next node
# 4。 has_value(): compare a value with the node value
class Node:
def __init__(self, data):
"constructor to initiate this object"
# store data
self.data = data
# store reference (next item)
self.next = None
return
def has_value(self, value):
"method to compare the value with the node data"
if self.data == value:
return True
else:
return False
Step 2: Creating a Class for a Single-Linked List
这一步我们建立一个叫 SingleLinkedList 的类。该类包含一下方法
-
__init__(): 初始化方法
list_length():返回节点数 -
output_list(): 打印方法 -
add_list_item(): 添加一个节点到list 中 -
unordered_search(): 在列表中查找具有指定值的节点 -
remove_list_item_by_id(): 通过节点id 移除节点
初始化方法
定 head 和tail属性
class SingleLinkedList:
def __init__(self):
"constructor to initiate this object"
self.head = None
self.tail = None
return
添加
def add_list_item(self, item):
"add an item at the end of the list"
#如果不是 Node，构建为Node
if not isinstance(item, Node):
item = Node(item)
#如果头节点是空，则当前节点就是 item
if self.head is None:
self.head = item
else:
#如果已经有头节点，则加到尾部
self.tail.next = item
#尾部就是当前绩点item了
self.tail = item
return
定义返回节点长度方法
def list_length(self):
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
定义输出方法
def output_list(self):
"outputs the list (the value of the node, actually)"
current_node = self.head
while current_node is not None:
print(current_node.data)
# jump to the linked node
current_node = current_node.next
return
查询
查询列表，返回指定值的node 位置list
def unordered_search(self, value):
"search the linked list for the node that has this value"
# define current_node
current_node = self.head
# define position
node_id = 1
# define list of results
results = []
while current_node is not None:
if current_node.has_value(value):
results.append(node_id)
# jump to the linked node
current_node = current_node.next
node_id = node_id + 1
return results
删除
def remove_list_item_by_id(self, item_id):
"remove the list item with the item id"
current_id = 1
current_node = self.head
previous_node = None
while current_node is not None:
#当前这个node 就是需要移除的node
if current_id == item_id:
# if this is the first node (head)
#如果这个node 前面还有node ，那需要把前面node 的next，指向当前node 的下一个node（原来前一个node 的next 是当前node）。
# 就已经从这个链路里移除了，因为没有node 指向它了。
if previous_node is not None:
previous_node.next = current_node.next
else:
#需要移除的是第一个node，只要把当前的head 指向下一个node 即可
self.head = current_node.next
# we don't have to look any further
return
# needed for the next iteration
# 如果还不是当前node，上一个node 变成当前node
# 当前node 变成当前node 的下一个。当然id 要加1
previous_node = current_node
current_node = current_node.next
current_id = current_id + 1
return
测试以上方法
我们使用一下代码，测试下以上方法。
# create three single nodes
node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")
node4 = ListNode(15)
track = DoubleLinkedList()
print("track length: %i" % track.list_length())
for current_node in [node1, node2, node3, node4]:
track.add_list_item(current_node)
print("track length: %i" % track.list_length())
track.output_list()
results = track.unordered_search(15)
print(results)
track.remove_list_item_by_id(4)
track.output_list()
Step 3: Creating a Double-Linked List
本来我们可以通过继承的方式，复用 Node 方法。但为了更清晰。我们再建立一个Node2 作为基本节点。
class Node2:
def __init__(self, data):
"constructor class to initiate this object"
# store data
self.data = data
# store reference (next item)
self.next = None
# store reference (previous item)
self.previous = None
return
def has_value(self, value):
"method to compare the value with the node data"
if self.data == value:
return True
else:
return False
建立 DoubleLinkedList
from Add_Two_Numbers.Node2 import Node2
class DoubleLinkedList:
def __init__(self):
"constructor to initiate this object"
self.head = None
self.tail = None
return
def list_length(self):
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
def output_list(self):
"outputs the list (the value of the node, actually)"
current_node = self.head
while current_node is not None:
print(current_node.data)
# jump to the linked node
current_node = current_node.next
return
def unordered_search (self, value):
"search the linked list for the node that has this value"
# define current_node
current_node = self.head
# define position
node_id = 1
# define list of results
results = []
while current_node is not None:
if current_node.has_value(value):
results.append(node_id)
# jump to the linked node
current_node = current_node.next
node_id = node_id + 1
return results
#略有不同
def add_list_item(self, item):
"add an item at the end of the list"
if isinstance(item, Node2):
#如果还没有Node，则首尾都是item，而且该node 的前一个没有，后一个也没有
if self.head is None:
self.head = item
item.previous = None
item.next = None
self.tail = item
else:
#如果有Node 元素了，则当前尾部的node的下一个node 就是item，item的前一个元素就是当前的tail node。现在把item 放到尾部。
self.tail.next = item
item.previous = self.tail
self.tail = item
return
#根据node id 移除node
def remove_list_item_by_id(self, item_id):
"remove the list item with the item id"
current_id = 1
current_node = self.head
#当前node 不为空
while current_node is not None:
previous_node = current_node.previous
next_node = current_node.next
#当前node 就是需要移除的node
if current_id == item_id:
# if this is the first node (head)
#当前node 不是第一个head node
if previous_node is not None:
#前一个node的 next 指向 下个node
previous_node.next = next_node
# 如果当前node 不是tail node
if next_node is not None:
# next_node 前一个node 指向 当前node 的前一个node（原来next_node 的前一个node 是 当前node）
next_node.previous = previous_node
else:
#如果需要移除的是head node，则把head 指向 next_node
self.head = next_node
# 如果 head node 不是最后一个node ，则还要把下一个node 的 previous 指向为None（原来为当前node）
if next_node is not None:
next_node.previous = None
# we don't have to look any further
return
# needed for the next iteration
current_node = next_node
current_id = current_id + 1
return
总结
链表作为数据结构易于实现，并且提供了很大的使用灵活性。这是用几行代码完成的。作为改进，您可以添加一个节点计数器（count），它只保存列表中节点的数量。这样可以把查询列表长度复杂度降低到 O(1)，您不必遍历整个列表。
