2 单链表

程技 python
发布时间 :
字数:1.3k 阅读 :
  1. 2.1 定义节点类
  2. 2.2 获取链表的长度
  3. 2.3 头插元素
  4. 2.4 尾插元素
  5. 2.5 指定位置插元素
  6. 2.6 删除节点
  7. 2.7 查找节点
  8. 2.8 打印链表
  9. 2.9 测试代码
  10. 2.10 完整代码

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

链表的基本元素有：

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

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

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

2.1 定义节点类

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 节点类
class Node(object):

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

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

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

2.2 获取链表的长度

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

2.3 头插元素

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

2.4 尾插元素

1
2
3
4
5
6
7
8
9
10
11
12
# 尾部添加元素
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 指定位置插元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 在指定位置添加元素
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 删除节点

1
2
3
4
5
6
7
8
9
10
11
12
# 删除指定节点
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 查找节点

1
2
3
4
5
6
7
8
9
# 查找节点
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 打印链表

1
2
3
4
5
6
7
8
9
10
11
12
# 遍历 打印链表
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 测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
# 测试
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()

结果图：

结果图

2.10 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#!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.data


class 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指向尾结点
            cur.next = node

    # 在指定位置添加元素
    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

    # 删除指定节点
    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

    # 查找节点
    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

    # 遍历 打印链表
    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))

# 测试
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()
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 richffan@outlook.com

文章标题:2 单链表

字数:1.3k

本文作者:Rich Fan

发布时间:2023-09-25, 00:00:00

最后更新:2024-02-27, 08:17:39

原始链接:http://fanrich.github.io/2023/09/24/python/Python%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/2-%E5%8D%95%E9%93%BE%E8%A1%A8/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

©2020-2024 RichFan

Built with Hexo and 3-hexo theme