链表
链表（Linked List）
链表是一种常见的数据结构，它由一系列节点（Node）组成，每个节点包含数据和指向下一个节点的引用（指针）。链表的主要优点是插入和删除操作的时间复杂度为O(1)，但访问特定元素的时间复杂度为O(n)。
单链表（Singly Linked List）
单链表是最简单的链表形式，每个节点只有一个指向下一个节点的引用。
节点类（Node Class）
首先，我们需要定义一个节点类，每个节点包含数据和指向下一个节点的引用。
class Node:
def __init__(self, data):
self.data = data
self.next = None
链表类（Linked List Class）
接下来，我们定义一个链表类，包含链表的头节点和一些基本操作。
class LinkedList:
def __init__(self):
self.head = None
def is_empty(self):
return self.head is None
def append(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def delete(self, key):
current = self.head
previous = None
while current and current.data != key:
previous = current
current = current.next
if current is None:
return
if previous is None:
self.head = current.next
else:
previous.next = current.next
def search(self, key):
current = self.head
while current and current.data != key:
current = current.next
return current is not None
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
使用链表类
我们可以创建一个链表实例并进行一些操作。
# 创建链表实例
llist = LinkedList()
# 添加元素
llist.append(1)
llist.append(2)
llist.append(3)
# 显示链表
llist.display() # 输出: 1 -> 2 -> 3 -> None
# 在头部添加元素
llist.prepend(0)
llist.display() # 输出: 0 -> 1 -> 2 -> 3 -> None
# 删除元素
llist.delete(2)
llist.display() # 输出: 0 -> 1 -> 3 -> None
# 搜索元素
print(llist.search(1)) # 输出: True
print(llist.search(2)) # 输出: False
不用类的方法实现链表
虽然使用类的方法实现链表更加面向对象和模块化，但我们也可以不使用类的方法来实现链表。这种方法通常用于简单的脚本或小规模的数据处理。
实现单链表
我们可以使用函数和字典来实现链表。
def create_node(data):
return {"data": data, "next": None}
def append_node(head, data):
new_node = create_node(data)
if head is None:
return new_node
current = head
while current["next"]:
current = current["next"]
current["next"] = new_node
return head
def prepend_node(head, data):
new_node = create_node(data)
new_node["next"] = head
return new_node
def delete_node(head, key):
current = head
previous = None
while current and current["data"] != key:
previous = current
current = current["next"]
if current is None:
return head
if previous is None:
head = current["next"]
else:
previous["next"] = current["next"]
return head
def search_node(head, key):
current = head
while current and current["data"] != key:
current = current["next"]
return current is not None
def display_list(head):
current = head
while current:
print(current["data"], end=" -> ")
current = current["next"]
print("None")
使用函数实现链表
我们可以使用这些函数来创建和操作链表。
# 创建链表
head = None
# 添加元素
head = append_node(head, 1)
head = append_node(head, 2)
head = append_node(head, 3)
# 显示链表
display_list(head) # 输出: 1 -> 2 -> 3 -> None
# 在头部添加元素
head = prepend_node(head, 0)
display_list(head) # 输出: 0 -> 1 -> 2 -> 3 -> None
# 删除元素
head = delete_node(head, 2)
display_list(head) # 输出: 0 -> 1 -> 3 -> None
# 搜索元素
print(search_node(head, 1)) # 输出: True
print(search_node(head, 2)) # 输出: False
具体讲解
类的方法实现链表
Node类
class Node:
def __init__(self, data):
self.data = data
self.next = None
__init__方法：这是Node类的构造方法，用于初始化节点的数据和指向下一个节点的引用。
LinkedList类
class LinkedList:
def __init__(self):
self.head = None
__init__方法：这是LinkedList类的构造方法，用于初始化链表的头节点。
def is_empty(self):
return self.head is None
is_empty方法：这个方法用于检查链表是否为空。如果头节点为None，则链表为空。
def append(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
append方法：这个方法用于在链表的末尾添加一个新节点。如果链表为空，则新节点成为头节点；否则，遍历链表直到找到最后一个节点，然后将新节点添加到其后面。
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
prepend方法：这个方法用于在链表的头部添加一个新节点。新节点的next指针指向当前的头节点，然后新节点成为新的头节点。
def delete(self, key):
current = self.head
previous = None
while current and current.data != key:
previous = current
current = current.next
if current is None:
return
if previous is None:
self.head = current.next
else:
previous.next = current.next
delete方法：这个方法用于删除链表中第一个值为key的节点。遍历链表，找到值为key的节点，然后将其从链表中移除。如果节点是头节点，则更新头节点；否则，更新前一个节点的next指针。
def search(self, key):
current = self.head
while current and current.data != key:
current = current.next
return current is not None
search方法：这个方法用于检查链表中是否存在值为key的节点。遍历链表，找到值为key的节点，如果找到则返回True，否则返回False。
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
display方法：这个方法用于显示链表中的所有节点。遍历链表，打印每个节点的数据，最后打印"None"表示链表结束。
不用类的方法实现链表
创建节点
def create_node(data):
return {"data": data, "next": None}
create_node函数：这个函数用于创建一个新节点，返回一个包含数据和next指针的字典。
添加节点
def append_node(head, data):
new_node = create_node(data)
if head is None:
return new_node
current = head
while current["next"]:
current = current["next"]
current["next"] = new_node
return head
append_node函数：这个函数用于在链表的末尾添加一个新节点。如果链表为空，则新节点成为头节点；否则，遍历链表直到找到最后一个节点，然后将新节点添加到其后面。
def prepend_node(head, data):
new_node = create_node(data)
new_node["next"] = head
return new_node
prepend_node函数：这个函数用于在链表的头部添加一个新节点。新节点的next指针指向当前的头节点，然后新节点成为新的头节点。
删除节点
def delete_node(head, key):
current = head
previous = None
while current and current["data"] != key:
previous = current
current = current["next"]
if current is None:
return head
if previous is None:
head = current["next"]
else:
previous["next"] = current["next"]
return head
delete_node函数：这个函数用于删除链表中第一个值为key的节点。遍历链表，找到值为key的节点，然后将其从链表中移除。如果节点是头节点，则更新头节点；否则，更新前一个节点的next指针。
搜索节点
def search_node(head, key):
current = head
while current and current["data"] != key:
current = current["next"]
return current is not None
search_node函数：这个函数用于检查链表中是否存在值为key的节点。遍历链表，找到值为key的节点，如果找到则返回True，否则返回False。
显示链表
def display_list(head):
current = head
while current:
print(current["data"], end=" -> ")
current = current["next"]
print("None")
display_list函数：这个函数用于显示链表中的所有节点。遍历链表，打印每个节点的数据，最后打印"None"表示链表结束。
通过这些方法和函数，我们可以实现链表的基本操作，包括添加、删除、搜索和显示节点。
总结
链表是一种重要的数据结构，适用于需要频繁插入和删除操作的场景。通过类的方法实现链表可以使代码更加模块化和面向对象，而不用类的方法实现链表则更加简单和直接。选择哪种方法取决于具体的应用场景和个人偏好。