Python数据结构(二)·单链表

作者： Jam 发布时间： January 21, 2025 分类：技术 No Comments

单链表是一种链式的数据结构，链表中的数据用结点表示，保持了数据之间的逻辑关系，但存储空间不一定是按照顺序存储。

链表的基本元素有：

节点：包括数据域和指针域，数据域存放数据，指针域存放指向下一个元素的指针
head：头结点
tail：尾结点
None：链表最后一个结点的指针域为None

Python中没有显式的指针，但是有引用啊，所以我们可以通过定义节点类和引用来实现链表！

链表分为单链表和单循环链表，双向链表和双向循环链表，本篇先讲一下单链表：

2.1 定义节点类

节点类中包括节点数据和下一个节点地址，即引用

# 节点类class Node(object):

    # 单个节点 初始化 输入一个值data，将值变为一个节点
    def __init__(self, data):
        self.data = data
        self.next = None

    # 打印对象中具体的属性值
    def __str__(self):
        # 测试基本功能，输出data
        return self.data# 输出dataprint(Node('data'))

这里的__str__可以不用写，这里是在进行测试，在后面的具体实现部分可以不用这个，str函数可以方便我们打印对象中具体的属性值，也是很nice了！具体使用如上

2.2 获取链表的长度

# 获取链表的长度def length(self):    cur = self.head
    count = 0
    while cur is not None:
        count += 1
        cur = cur.next
    return count

2.3 头插元素

# 头部添加元素def add_fist(self, data):
    node = Node(data)
    node.next = self.head
    self.head = node

2.4 尾插元素

# 尾部添加元素def add_last(self, data):
    node = Node(data)    # 如果链表为空，需要特殊处理
    if self.is_empty():
        self.head = node    else:
        cur = self.head        while cur.next is not None:
            cur = cur.next
        # 退出循环的时候，curl指向尾结点
        cur.next = node

2.5 指定位置插元素

# 在指定位置添加元素def insert_node(self, index, data):
    node = Node(data)    if index < 0 or index > self.length():        return False
    elif index == 0:
        self.add_fist()    elif index == self.length():
        self.add_last()    else:
        cur = self.head
        count = 0
        while count < (index - 1):
            count += 1
            cur = cur.next
        # 退出循环的时候，cur指向index的前一个位置
        node.next = cur.next
        cur.next = node

2.6 删除节点

# 删除指定节点def remove_node(self, data):
    cur = self.head  # 指针指向的结点
    pre = None  # 指针指向结点的前一个
    if self.head == data:
        self.head.next = self.head    else:        while cur.data is not data:            # 不是要找的元素，移动游标
            pre = cur
            cur = cur.next
        pre.next = cur.next

2.7 查找节点

# 查找节点def search_node(self, data):
    cur = self.head    while cur is not None:        if cur.data == data:            return True
        else:
            cur = cur.next
    return False

2.8 打印链表

# 遍历 打印链表def traverse_to_print_node(self):
    # cur = self.head
    # while cur is not None:
    #     print(cur.data, end = " ")
    #     cur = cur.next
    print_list = []
    cur = self.head    while cur is not None:
        print_list.append(str(cur.data))
        cur = cur.next
    print('->'.join(print_list))

2.9 测试代码

# 测试if __name__ == '__main__':    list = SingleLinkedList()    list.add_fist(2)    list.add_fist(1)    list.add_last(4)    list.insert_node(2, 3)    list.traverse_to_print_node()    print(list.is_empty())    print(list.length())    list.remove_node(4)    print(list.search_node(3))    list.traverse_to_print_node()

结果图：

结果图

<br/>

2.10 完整代码

#!usr/bin/env python# encoding:utf-8# 节点类class Node(object):

    # 单个节点初始化输入一个值data，将值变为一个节点
    def __init__(self, data):
        self.data = data
        self.next = None

    # 打印对象中具体的属性值
    def __str__(self):
        # 测试基本功能，输出data
        return self.dataclass SingleLinkedList(object):

    # 创建一个单链表
    def __init__(self):
        self.head = None

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

    # 获取链表的长度
    def length(self):
        cur = self.head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count    # 头部添加元素
    def add_fist(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node    # 尾部添加元素
    def add_last(self, data):
        node = Node(data)        # 如果链表为空，需要特殊处理
        if self.is_empty():
            self.head = node        else:
            cur = self.head            while cur.next is not None:
                cur = cur.next
            # 退出循环的时候，curl指向尾结点