[数据结构与算法]python实现链表（一）

单链表，是一种链式存储的数据结构，每个数据中除了有保存的元素本身的数据，还有一个指针，这个指针指向链表里的下一个元素。

class nodes:
    # 初始化链表时，传入参数，这里第一个参数是链表的值，也可以说是保存的数据，可以是一个，也可以是多个
    def __init__(self, node_no: int, node_name):
        # 下一个节点
        self.next = None
        self.node_no = node_no
        self.node_name = node_name

这里每个节点有三个数据，一个是指针，一个是节点编号和节点姓名。

# 单向链表的实现，管理链表里的元素
class single_linked_list:
    # 初始化一个头节点,传入的索引为空
    __head = nodes(0, '')

这里的单向链表有一个头结点，这个头结点是用来指向下一个节点的，本身不保存任何信息。

接下来，添加节点，我这里实现了两种添加方式，一种是无序添加，一种是按照node_no的大小添加。

无序添加节点

# 首先，找到最后一个节点
# 第二，将最后一个节点的索引指向新的节点
# 无序添加元素
def add(self, node: nodes):
    head = self.__head
    while True:
        # 如果链表索引为空，则退出循环
        if head.next == None:
            break
        head = head.next
    # 为链表尾部的索引赋值
    head.next = node

有序添加节点

# 根据第一个参数的大小来添加元素
def add_by_order(self, node: nodes):
    temp = self.__head
    # 判断添加的节点是否存在
    flag = False
    while True:
        if temp.next == None:
            break
        # 找到位置，在temp的后端插入
        if temp.next.node_no > node.node_no:
            break
        elif temp.next.node_no == node.node_no:
            flag = True  # 说明编号存在
            break
        temp = temp.next
    if flag:
        print('编号已经存在：' + str(temp.next.node_no))

    else:
        # 先将传入的node里的索引指向temp.next，然后将temp.next里的索引指向node
        node.next = temp.next
        temp.next = node

那么，添加元素就结束了，测试一下，写一个展示链表所有元素的方法

# 显示链表，遍历一次
def show_list(self):
    if self.__head.next == None:
        print('链表为空。。。')
        return
    temp = self.__head.next
    while True:
        # 判断链表是否到尾部
        if temp == None:
            break
        print(temp.node_no, temp.node_name)
        temp = temp.next

node1 = nodes(1, '徐一')
node2 = nodes(2, '刘二')
node3 = nodes(3, '张三')
node4 = nodes(4, '李四')

无序添加元素

#不按顺序添加
linklist.add(node1)
linklist.add(node4)
linklist.add(node3)
linklist.add(node2)
linklist.show_list()

输出

1 徐一
4 李四
3 张三
2 刘二

Process finished with exit code 0

再测试一下按no添加

linklist.add_by_order(node1)
linklist.add_by_order(node4)
linklist.add_by_order(node3)
linklist.add_by_order(node2)
linklist.add_by_order(node2)
linklist.show_list()

编号已经存在：2
1 徐一
2 刘二
3 张三
4 李四

没问题，接下来继续，显示一下头部元素

# 显示头部元素数据
def show_head(self):
    if self.__head.next == None:
        print('链表为空。。。')
    # 注意，头结点是没有数据的，仅用来指向链表里的第一个元素
    print(self.__head.next.node_no, self.__head.next.node_name)

修改和删除元素也要加上

# 修改链表元素
def update_node(self, node_no: int, node_name):
    temp = self.__head
    flag = False
    if temp.next == None:
        print('链表为空')
        return
    while True:
        if temp.next == None:
            break
        elif temp.node_no == node_no:
            flag = True
            break
        temp = temp.next
    if flag:
        temp.node_name = node_name
    else:
        print('没有找到此编号的人物')

# 根据编号删除节点操作
def remove_node(self, node_no: int):
    temp = self.__head
    flag = False
    if temp.next == None:
        print('链表为空')
        return
    while True:
        if temp.next == None:
            break
        # 查找下一个节点是否和传入的节点相同
        elif temp.next.node_no == node_no:
            flag = True
            break
        temp = temp.next
    if flag:
        # 将后面的数据删除
        temp.next = temp.next.next
    else:
        print('没有找到节点')

测试

# 修改编号2姓名为胡歌
linklist.update_node(2, '胡歌')
linklist.update_node(5,'一眼丁真')
linklist.show_list()
# 删除node2
print('删除node2')
linklist.remove_node(2)
linklist.show_list()
print(linklist.link_length())
print('再次添加node2')
linklist.add_by_order(node2)
linklist.show_list()
print(linklist.link_length())

输出

删除node2
1 徐一
3 张三
4 李四
再次添加node2
1 徐一
2 胡歌
3 张三
4 李四

Process finished with exit code 0
没有问题，结束