五分钟搞懂链表实现：Python数据结构与算法

链表是一种由节点组成的线性数据结构，每个节点包含一个数据元素和一个指向下一个节点的指针。

1.链表的基本概念

(1)节点定义

链表中的每一个元素都是一个节点，每个节点通常包含两部分：数据和下一个节点的引用。

class Node:
    def __init__(self, data):
        self.data = data  # 节点存储的数据
        self.next = None  # 默认下一个节点为空

(2)链表定义

链表通常有一个头节点来表示链表的开始。尾节点是链表中的最后一个节点，它的下一个节点引用为None。

class LinkedList:
    def __init__(self):
        self.head = None  # 初始链表为空

2.向链表中添加元素

(1)在链表的开头添加元素

def add_first(self, data):
    new_node = Node(data)   # 创建新的节点
    new_node.next = self.head  # 将新节点指向当前的头节点
    self.head = new_node    # 更新头节点为新节点

LinkedList.add_first = add_first

(2)在链表的结尾添加元素

def add_last(self, data):
    new_node = Node(data)
    if self.head is None:  # 若链表为空，则直接将新节点设置为头节点
        self.head = new_node
        return
    last_node = self.head  # 遍历到链表的尾部
    while last_node.next:
        last_node = last_node.next
    last_node.next = new_node  # 在链表尾部添加新节点

LinkedList.add_last = add_last

3.从链表中删除元素

(1)删除链表的第一个元素

def remove_first(self):
    if self.head:
        self.head = self.head.next  # 更新头节点为下一个节点

LinkedList.remove_first = remove_first

(2)删除链表的最后一个元素

def remove_last(self):
    if self.head is None:  # 若链表为空，直接返回
        return
    if self.head.next is None:  # 若链表只有一个元素，将头节点设置为空
        self.head = None
        return
    second_to_last = self.head  # 找到倒数第二个节点
    while second_to_last.next.next:
        second_to_last = second_to_last.next
    second_to_last.next = None  # 将倒数第二个节点的next设置为空，从而删除最后一个节点

LinkedList.remove_last = remove_last

4.遍历链表

def print_list(self):
    current_node = self.head  # 从头节点开始遍历
    while current_node:
        print(current_node.data, end=" -> ")
        current_node = current_node.next  # 移动到下一个节点
    print("None")

LinkedList.print_list = print_list

5.查找链表中的元素

def search(self, target):
    current_node = self.head  # 从头节点开始遍历
    while current_node:
        if current_node.data == target:  # 若找到目标数据，返回True
            return True
        current_node = current_node.next  # 移动到下一个节点
    return False  # 遍历完链表后，未找到目标数据，返回False

LinkedList.search = search

6.实战案例：反转链表
一个常见的面试问题是如何反转链表。我们可以使用迭代的方法来解决这个问题。

def reverse(self):
    prev = None  # 上一个节点
    current = self.head  # 当前节点
    while current:
        next_node = current.next  # 记录下一个节点
        current.next = prev  # 将当前节点指向上一个节点
        prev = current  # 更新上一个节点为当前节点
        current = next_node  # 移动到下一个节点
    self.head = prev  # 更新头节点

LinkedList.reverse = reverse

# 使用示例
ll = LinkedList()
ll.add_last(1)
ll.add_last(2)
ll.add_last(3)
ll.print_list()  # 输出：1 -> 2 -> 3 -> None
ll.reverse()
ll.print_list()  # 输出：3 -> 2 -> 1 -> None

小结

链表提供了一种在内存中存储有序元素的方法，它的主要优势在于插入和删除操作的效率高，不需要移动其他元素。不过，链表的随机访问速度比数组慢，因为需要从头节点开始遍历。理解链表的结构和常用操作是计算机科学基础，也经常用于面试中。