Python单链表原理与实现方法详解

什么是单链表

在计算机科学中，链表（Linked list）是一种常见的数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。由于不必须按顺序存储，链表在插入的时候可以达到 O(1)O(1) 的复杂度，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表相应的时间复杂度分别是 O(log n) 和 O(1)。

其中单链表是链表的一种，每个节点只有一个后继指针，即只能往一个方向移动。

单链表的实现

在Python中我们可以使用类来实现单链表的定义和操作。单链表的节点可以用一个类来表示，每个节点由两个部分组成，一个是存放数据的部分（存放我们要存储的值或数据对象），另一个是存放下一个节点的地址（指向下一个节点对象，在Python中表现为一个类的实例）。

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

首先，我们定义了一个Node的类，来实现单链表的每个节点。该类有两个属性：

• data：用于存储数据的属性
• next：该节点下一个节点的地址

具体的操作需要有一个LinkedList类来实现。该类将实现以下方法：

• init()：初始化链表。
• add(data)：向链表中添加一个节点。
• delete(data)：从链表中删除一个节点。
• is_empty()：链表是否为空。
• get_length()：返回链表的长度。
• search(data)：查找链表中是否存在数据data，如果存在返回True，否则返回False。
• traverse()：遍历整个链表，并打印每个节点的数据。

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

    #添加节点
    def add(self, data):
        new_node = Node(data)  #创建节点
        new_node.next = self.head  #将新节点的next连接到当前头部
        self.head = new_node  #将新节点作为新的头部

    #删除节点
    def delete(self, data):
        current_node = self.head
        previous_node = None
        while current_node:
            if current_node.data == data:
                if previous_node:
                    previous_node.next = current_node.next  
                else:
                    self.head = current_node.next
                return True
            previous_node = current_node
            current_node = current_node.next
        return False

    #判断链表是否为空
    def is_empty(self):
        return not bool(self.head)

    #获取链表长度
    def get_length(self):
        current_node = self.head
        count = 0
        while current_node:
            count += 1
            current_node = current_node.next
        return count

    #查找链表中是否存在某个数据
    def search(self, data):
        for node_data in self:
            if data == node_data:
                return True
        return False

    #遍历整个链表
    def traverse(self):
        current_node = self.head
        while current_node:
            yield current_node.data
            current_node = current_node.next

    #实现__iter__方法，方便遍历链表
    def __iter__(self):
        current_node = self.head
        while current_node:
            yield current_node.data
            current_node = current_node.next

单链表的示例应用

实例一：使用单链表操作一个简单的通讯录

#定义通讯录
contacts = LinkedList()

#添加联系人
contacts.add({'name': '张三', 'phone': '123456789'})
contacts.add({'name': '李四', 'phone': '987654321'})
contacts.add({'name': '王五', 'phone': '456789123'})

#获得通讯录长度
print('通讯录长度：', contacts.get_length())

#删除名为“李四”的联系人
contacts.delete({'name': '李四', 'phone': '987654321'})

#遍历通讯录
print('通讯录中的联系人：')
for contact in contacts.traverse():
    print(contact)

Output:

通讯录长度： 3
通讯录中的联系人：
{'name': '王五', 'phone': '456789123'}
{'name': '张三', 'phone': '123456789'}

实例二：使用单链表实现栈

#定义栈
class Stack:
    def __init__(self):
        self.container = LinkedList()

    #向栈中添加一个元素
    def push(self, data):
        self.container.add(data)

    #从栈中弹出一个元素
    def pop(self):
        if not self.is_empty():
            return self.container.head.data
        else:
            return None

    #判断栈是否为空
    def is_empty(self):
        return self.container.is_empty()

    #获得栈的长度
    def get_length(self):
        return self.container.get_length()

#创建栈
stack = Stack()

#向栈中添加元素
stack.push(1)
stack.push(2)
stack.push(3)

#从栈中弹出元素，并打印
while not stack.is_empty():
    print(stack.pop())

Output:

3
2
1

总结

通过这篇文章，我们学习了单链表的定义、实现方法和示例应用。在Python中，我们可以使用类来实现单链表，通过对节点的操作来实现链表的增删改等操作。同时我们还看到了两个具体的示例应用，一个是通讯录，一个是栈。单链表作为一种基本的数据结构，应用十分广泛。但是在实际应用中也需要我们具体问题具体分析，选择最合适的数据结构，以达到更好的效果。