Python3数据结构02 - 单向链表

  • 原创
  • Madman
  • /
  • 2018-09-03 14:00
  • /
  • 0
  • 184 次阅读

Synopsis: 链表也是线性表的一种,链表可以合理利用不连续的内存区,可以相对灵活地使用存储空间。但是,它的每个节点增加了指针域,所以空间开销也比较大。另外,它失去了顺序表的快速读取任意元素 O(1) 的优点

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

1. 链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁,所以使用起来并不是很灵活。

链表(Linked list)不像顺序表一样连续存储数据,而是在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址),它可以充分利用计算机内存空间,实现灵活的内存动态管理

2. 单向链表

单向链表(Singly linked list)也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个指针域(内存地址),这个链接指向链表中的下一个节点,而最后一个节点则指向一个空值

单向链表只可向一个方向遍历,一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点,一直访问到需要的位置

2.1 Python实现

接下来我们使用Python 3来构建单链表数据结构,首先需要定义一个节点类:

class Node:
    '''单链表的节点'''
    def __init__(self, value):
        self.value = value  # 节点的信息域
        self.next = None    # 节点的指针域

    def __repr__(self):
        return 'Node({!r})'.format(self.value)

然后定义单链表类:

class SinglyLinkedList:
    def __init__(self, node=None):
        '''创建一个单链表对象时,如果不传入头节点,则创建空链表'''
        self.__head = node

(1) 判断是否空链表

只需要判断单链表的__head属性是否为None即可,如果是None表示没有头节点,则是空链表

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

(2) 求链表的长度

定义一个游标cur,用来表示遍历到的当前节点,初始时等于链表的头节点(即cur = self.__head)。count变量用于统计已遍历了多少个节点,初始时等于0。当cur移动到尾节点时,cur.next == None,此时再将cur往后移动时,需要退出while循环

该方法最后返回count即可

def length(self):
    '''求链表的长度'''
    cur = self.__head  # 游标,用来表示当前节点
    count = 0  # 用来统计已遍历的节点数目

    # 1. 如果是空链表,self.__head为None,则cur为None,不会进入循环体,最后返回 count = 0,符合
    # 2. 如果不是空链表,当cur移动到尾节点时,cur.next 是None,循环体中的 cur = cur.next 会让 cur = None,继续往后移动时会退出循环
    while cur is not None:
        count += 1
        cur = cur.next  # 向后移动游标

    return count

(3) 遍历链表

逻辑跟求长度一样,注意,这里使用生成器语法,将每个节点的值产出供客户代码使用

def travel(self):
    '''遍历整个链表'''
    cur = self.__head  # 游标,用来表示当前节点
    while cur is not None:
        yield cur.value  # 生成当前节点的值
        cur = cur.next  # 向后移动游标

(4) 在尾部添加元素

首先需要找到尾节点,方法是定义cur游标(指示当前节点)遍历链表,当cur.next是None时,就表示找到了尾节点。然后,将cur.next指向新添加的节点即可

def append(self, value):
    '''在链表的尾部添加节点。注意:传入的 value 是节点的值'''
    node = Node(value)

    if self.is_empty():  # 如果是空链表
        self.__head = node
    else:
        cur = self.__head  # 游标,用来表示当前节点
        # 遍历链表,直到找到了尾节点后,退出循环
        while cur.next is not None:
            cur = cur.next
        # 此时,cur 表示尾节点,将它的 next 指向新增的节点即可
        cur.next = node

(5) 在头部插入元素

需要先将新添加的节点的next指向原来的头节点,再将链表对象的__head属性重新指向新添加的节点,顺序不能倒置,否则将丢失之前所有节点

def head_add(self, value):
    '''在链表的头部添加节点,也适合空链表的情况'''
    node = Node(value)
    node.next = self.__head  # 将新增节点的 next 指向原来的头节点
    self.__head = node  # 再将链表的 __head 属性指向新增节点即可

(6) 在指定位置插入元素

该方法需要传入下标pos和元素的值,为了跟列表等一样,这里规定pos从0开始计数,即头节点的pos为0

在指定位置pos插入元素,我们只需要找到pos - 1所在位置的节点,这里用pre游标来表示它。然后让新添加的节点的next指向pre.next,再让pre.next指向新添加的节点即可,注意,这里和在头部插入元素一样,顺序不能倒置

def insert(self, pos, value):
    '''在指定位置添加节点。 pos 表示节点的下标,为了跟列表等一样,这里规定 pos 从0开始计数,即头节点的 pos 为0'''
    if pos <= 0:  # 暂时不支持负数的下标。如果传入负数或者0,统一在头部插入
        self.head_add(value)
    elif pos > self.length() - 1:  # 如果传入的下标大于链表的长度减去1,默认使用在尾部插入
        self.append(value)
    else:
        pre = self.__head  # 游标,用来表示 pos - 1 位置的节点
        count = 0
        while count < pos - 1:  # 当count = pos - 1时,表示已经找到了 pos - 1 的节点,退出循环
            count += 1
            pre = pre.next  # 向后移动游标
        # 退出循环后,pre 指向 pos - 1 所在的节点
        node = Node(value)
        node.next = pre.next  # 将新增节点的 next 指向 pre 的下一节点
        pre.next = node  # 再将 pre 的 next 重新指向新增的节点即可

(7) 查看元素是否在链表中

逻辑跟遍历链表类似,每遍历一个节点时,比较节点的值是否与要查找的元素相等,如果相等则直接返回True,否则继续向后遍历。注意,while循环条件不能遗忘尾节点

def search(self, value):
    '''查找指定的元素值是否在链表中,也适合空链表的情况'''
    cur = self.__head
    while cur is not None:
        if cur.value == value:
            return True
        else:
            cur = cur.next
    return False  # 遍历完整个链表也没找到时

(8) 在链表中删除指定元素值

使用cur游标指示遍历过程中的当前节点,如果cur.value与要删除的元素值相等时,表示找到了要删除的节点。此时,我们需要将cur的前驱节点的next重新指向cur的后继节点,所以还需要定义pre游标来指示遍历过程中的前驱节点

def remove(self, value):
    '''在链表中删除指定元素值,跟列表中的 remove() 类似,也是删除第一个遇到的元素'''
    pre = None
    cur = self.__head

    while cur is not None:  # 遍历整个链表
        if cur.value == value:  # 表示找到了要删除的节点
            # 特殊情况1: 如果要删除的节点是头节点时
            # 特殊情况2: 链表只有一个节点,刚好它就是要删除的节点,其实跟特殊情况1一样,因为它也是头节点
            if cur == self.__head:
                self.__head = cur.next
            else:  # 此时,cur 指向要删除的节点,pre 指向要删除的节点的前一节点
                pre.next = cur.next  # 特殊情况3: 如果要删除的节点是尾节点时,也适合
            # 当找到要删除的节点时,需要退出 while 循环
            break
        else:
            pre = cur  # 先让 pre 指向当前节点
            cur = cur.next  # 再让 cur 向后移动

2.2 链表与顺序表的对比

首先看一下时间复杂度:

操作 链表 顺序表
在头部插入/删除元素 O(1) O(n)
在尾部插入/删除元素 O(n) O(1)
在指定位置插入/删除元素 O(n) O(n)
访问元素 O(n) O(1)

链表要找到指定元素,必须从头开始遍历,所以访问元素的时间复杂度是O(n),而顺序表可以通过偏移量一次计算出指定元素的内存地址,时间复杂度是O(1)

在指定位置插入/删除元素时,它们的时间复杂度虽然都是O(n),但是链表的耗时操作是因为遍历查找,而顺序表是数据搬迁(保序)

链表可以合理利用不连续的内存区,可以相对灵活地使用存储空间。但是,它的每个节点增加了指针域,所以空间开销也比较大。另外,它失去了顺序表的快速读取任意元素(O(1))的优点

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3数据结构02 - 单向链表

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录