荐 python3实现单向链表图文详解_Python

任何复杂的数据结构都是由int、char、float这些基本数据结构组合而成，不同的组合方式在进行不同操作时有着差异巨大的时间或空间复杂度，例如python中的list就是由基本数据类型按照顺序表的方式去排列而实现的新数据结构。但是python中没有用链表结构实现的数据类型，那我们就试着自己来造一下车轮子。这一节就来实现最简单的单向链表。

文章目录

单向链表
python3实现

结点类
单向链表类

构造函数
isEmpty
length
travel
append
shift
insert
remove
exist

完整代码
时间复杂度

单向链表

如下图所示，单向链表中每一个数据结点，除了保存当前结点的基本数据值，还要保存后面相邻节点的地址，从而形成从头到尾的一个单向指针结构。而整个单向链表的变量名，存储的是第一个结点的地址。

简单描述下这种结构的特点

因为结点的内存地址不需要连续，所以相比顺序表，对于内存的利用更高效
同时管理器只需要存储第一个结点的地址即可，对于后续结点，也只需要前一个结点有指针即可
根据下标的查询操作只能从第一个结点依次往后进行
越靠近头部的操作时间复杂度越低，越靠近尾部的时间复杂度越高

python3实现

下面根据上面的结构特点来实现单向链表类，不过首先得搞定单个结点类。

结点类

单个结点只需要存储两个值，在构造函数中赋值即可。默认情况下一个结点的地址放None，等有需要时再进行赋值

class Node(object):
    def __init__(self, value):
        self.value = value
        self.next = None

单向链表类

根据上面的分析，该类只需要保存一个对象属性即可

属性	说明	类型
__head	指向第一个结点的地址	对象属性，仅内部使用

该类实现以后，要实现对里面保存数据的增删改查方法，从最基本的开始，先实现如下几个功能

方法	说明	类型
isEmpty	链表长度为0返回True，否则返回False	对象方法
length	返回链表数据的长度	对象方法
travel	遍历整个链表，依次打印每个结点的值	对象方法
append	在链表尾端添加结点	对象方法
shift	在链表头部添加结点	对象方法
insert	在指定下标添加结点	对象方法
remove	删除第一次出现的某个值	对象方法
exist	检查某个值是否在链表中	对象方法

下面一个个地来。

构造函数

允许用户直接构造空的链表或者传一个后续结点进来

class SingleLinkedList(object):
    def __init__(self, node=None):
        self.__head = node

不带任何参数就是空链表，self.__head为None，否则就是node的地址。

要理解这里的变量赋值以及后面的很多游标和地址的赋值运算，必须要搞清楚python和很多其他语言不一样，其中的变量都不存储具体值，而只是存放值的地址。所以python的变量名表示的就是地址，将变量赋值给另一个变量，就是将另一个变量也指向前一个变量指向的地址。可以参考另一篇博客《python3中各类变量的内存堆栈分配和函数传参区别实例详解》

isEmpty

这个比较容易，只需要判断self.__head是否为None即可达到目的

def isEmpty(self):
	return self.__head == None

pep8中建议用is去和None做判断，不过用双等号也可以

length

如下图所示

因为是单向链表，只要是遍历都只能从头开始操作。可以创建一个游标cur，或者叫指针，从第一个结点依次找到最后一个结点，每增加一个结点，将中间变量count的值加1，最后count就是结点的总数，也就是链表的长度。当然加一减一的偏差需要慢慢去比对了

def length(self):
    # cur is current position
    cur = self.__head
    count = 0
    while cur != None:
        cur = cur.next
        count += 1
    return count

先通用再特殊，下面考虑下特殊情况，就是链表为空的时候，也就是self.__head为None，赋值给cur，无法进入循环，返回0，也能达到目的。

travel

遍历链表和上面求长度思路基本一样，直接看代码

def travel(self):
    # cur is current position
    cur = self.__head
    while cur != None:
        print(cur.value, end=" ")
        cur = cur.next
    print('')

python3中如果要打印不换行，用end=" "，最后再打印一次是为了换行，因为默认不管打印什么都会换行。

append

前面说过，因为必须要先遍历一遍链表到最后，所以在末尾添加结点的时间复杂度是很高的。

先看看通用情况

def append(self, value):
	node = Node(value)
	cur = self.__head
	while cur.next != None:
		cur = cur.next
	cur.next = node

注意这里不能等到cur == None退出循环，而是cur.next == None，这样才好通过游标对最后一个结点进行操作。

但是这段代码不能满足特殊情况，就是链表为空的情况，因为此时cur为None，但是None没有next属性，会报错，于是修改下

def append(self, value):
    node = Node(value)
    if self.isEmpty():
        self.__head = node
    else:
        cur = self.__head
        while cur.next != None:
            cur = cur.next
        cur.next = node

如果链表为空，直接将新的结点赋值给self.__head即可。

shift

从头添加就比较容易了，但是要注意，在中间插入必须先建立连接再断开原有连接。也就是说先将后一个结点的地址赋值给插入的结点的next，再将原先的前一个结点的next修改为插入的节点地址。因为一旦先断开，后面的所有节点的地址都会找不到了

def shift(self, value):
    node = Node(value)
    node.next = self.__head
    self.__head = node

如果是空链表的特殊情况也是可以达到目的的。

insert

和shift一样，注意先连接再断开，稍微复杂的是这里要进行位置判断。

通用代码如下

def insert(self, pos, value):
    node = Node(value)
    cur = self.__head
    count = 0
    while count < pos - 1:
        cur = cur.next
        count += 1
    node.next = cur.next
    cur.next = node

但是因为pos参数是用户传递进来的，还需要进行特殊值的判断，这里规定0或负值都是在头部插入，如果大于长度就在尾部插入

def insert(self, pos, value):
    if pos <= 0:
        self.shift(value)
    elif pos > (self.length() - 1):
        self.append(value)
    else:
        node = Node(value)
        cur = self.__head
        count = 0
        while count < pos - 1:
        	cur = cur.next
            count += 1
        node.next = cur.next
        cur.next = node

remove

删除结点应该算是所有方法中的难点和重点，因为删除以后要将删除结点的前后连接起来，所以游标必须停留在说删除结点的前一个结点，这样才能对前一个结点的next做赋值操作。此时就得考虑很多种特殊情况，例如只有一个结点时，空链表时

通用代码如下

def remove(self, value):
    cur = self.__head
    while cur.next != None:
        if cur.next.value == value:
            cur.next = cur.next.next
            return value
        else:
            cur = cur.next
    return

如果加上特殊情况，如下

def remove(self, value):
    cur = self.__head
    if cur.value == value:
        self.__head = cur.next
        return value
    elif self.__head is None:
        return
    else:
        while cur.next != None:
            if cur.next.value == value:
                cur.next = cur.next.next
                return value
            else:
                cur = cur.next
        return

exist

这个也是遍历链表，检查每个结点的值，比较简单，直接给出代码

def exist(self, value):
    cur = self.__head
    while cur != None:
        if cur.value == value:
            return True
        else:
            cur = cur.next
    return False

所有的方法实现了，下面开始测试

if __name__ == "__main__":
    sll = SingleLinkedList()
    
    print(sll.exist(10))  # False
    print(sll.length())  # 0
    print(sll.isEmpty()) # True

    sll.append(1)
    print(sll.length())  # 1
    print(sll.isEmpty())  # False

    sll.append(2)
    sll.append(3)
    sll.append(4)
    sll.append(5)
    sll.append(6)
    sll.shift(8)  # 8123456
    sll.insert(2, 9)  # 81923456
    sll.insert(-2, 10)  # 10 81923456
    sll.insert(100, 11)  # 10 81923456 11   
    sll.travel()  # 10 8 1 9 2 3 4 5 6 11
    print(sll.length())  # 10
    print(sll.isEmpty())  # False
    print(sll.exist(100))  # False
    print(sll.exist(6))  # True

    sll.remove(6)
    sll.remove(10)
    sll.remove(11)
    print(sll.exist(6))  # False
    
    sll.travel()  # 8 1 9 2 3 4 5

最后打印的结果和上面的一样

False
0
True
1
False
10 8 1 9 2 3 4 5 6 11 
10
False
False
True
False
8 1 9 2 3 4 5

完整代码

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time: 2020-Jul-06
# @Author: xiaofu

class Node(object):
    def __init__(self, value):
        self.value = value
        self.next = None


class SingleLinkedList(object):
    def __init__(self, node=None):
        self.__head = node

    def isEmpty(self):
        """check if the list is empty"""
        return self.__head == None

    def length(self):
        """length of the list"""
        # cur is current position
        cur = self.__head
        count = 0
        while cur != None:
            cur = cur.next
            count += 1
        return count

    def travel(self):
        """traverse through the list"""
        # cur is current position
        cur = self.__head
        while cur != None:
            print(cur.value, end=" ")
            cur = cur.next
        print('')

    def shift(self, value):
        """add a node to the start"""
        node = Node(value)
        # link before break
        node.next = self.__head
        self.__head = node

    def append(self, value):
        """add a node to the end"""
        node = Node(value)
        if self.isEmpty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, value):
        """insert a node at specific position"""
        if pos <= 0:
            self.shift(value)
        elif pos > (self.length() - 1):
            self.append(value)
        else:
            node = Node(value)
            cur = self.__head
            count = 0
            while count < pos - 1:
                cur = cur.next
                count += 1
            node.next = cur.next
            cur.next = node

    def remove(self, value):
        """remove a node from list when a value first appears"""
        cur = self.__head
        if cur.value == value:
            self.__head = cur.next
            return value
        elif self.__head is None:
            return
        else:
            while cur.next != None:
                if cur.next.value == value:
                    cur.next = cur.next.next
                    return value
                else:
                    cur = cur.next
            return

    def exist(self, value):
        """whether a node exists in list"""
        cur = self.__head
        while cur != None:
            if cur.value == value:
                return True
            else:
                cur = cur.next
        return False

时间复杂度

最后看看各种操作的时间复杂度

访问元素 - 因为必须要遍历，所以时间复杂度为O(n)
头部插入/删除元素 - O(1)
尾部插入/删除元素 - O(n)
中间插入/删除元素 - 最坏情况也是要遍历所有元素，所以是O(n)

我是T型人小付，一位坚持终身学习的互联网从业者。喜欢我的博客欢迎在csdn上关注我，如果有问题欢迎在底下的评论区交流，谢谢。

本文地址：https://blog.csdn.net/Victor2code/article/details/107170807

您可能感兴趣的文章:

如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！

荐 python3实现单向链表图文详解

2020年07月08日 | 移动技术网IT编程 | 我要评论