Python3数据结构02 - 单向链表

原创

Madman

10383 次阅读

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