单链表

和线性结构不同,链式结构内存不连续的,而是一个个串起来的,这个时候就需要每个链接表的节点保存一个指向下一个节点的指针。 这里不能混淆了列表和链表(它们的中文发音类似,但是列表 list 底层其实还是线性结构,链表才是真的通过指针关联的链式结构)。 看到指针你也不用怕,这里我们用的 python,你只需要一个简单赋值操作就能实现,不用担心 c 语言里复杂的指针。

单链表可以视为一辆火车,每节车厢是一个节点(node),有自己的货(value),同时也记录了下一节车厢(next)。车厢物理上可以打散乱放,但逻辑上是按顺序连在一起的。
火车头就叫做root,是入口但不装货,只装头节点的位置。要找某一节车厢只能从头找.

定义一个Node

首先我们需要定义一个链接表的节点,刚才说到有一个指针保存下一个节点的位置,我们叫它 next, 当然还需要一个 value 属性保存值

class Node(object):
    def __init__(self, value=None, next=None):   # 这里我们 root 节点默认都是 None,所以都给了默认值
        self.value = value
        self.next = next

时间复杂度

链表操作平均时间复杂度
linked_list.append(value)O(1)
linked_list.appendleft(value)O(1)
linked_list.find(value)O(n)
linked_list.remove(value)O(n)

最后给出完整的实现代码

class Node(object):
    def __init__(self, value=None, next=None):   # 这里我们 root 节点默认都是 None,所以都给了默认值
        self.value = value
        self.next = next

    def __str__(self):
        """方便你打出来调试,复杂的代码可能需要断点调试"""
        return '<Node: value: {}, next={}>'.format(self.value, self.next)

    __repr__ = __str__


class LinkedList(object):
    """ 链接表 ADT
    [root] -> [node0] -> [node1] -> [node2]
    """

    def __init__(self, maxsize=None):
        """
        :param maxsize: int or None, 如果是 None,无限扩充
        """
        self.maxsize = maxsize
        self.root = Node()     # 默认 root 节点指向 None
        self.tailnode = None
        self.length = 0

    def __len__(self):
        return self.length

    def append(self, value):    # O(1)
        if self.maxsize is not None and len(self) >= self.maxsize:
            raise Exception('LinkedList is Full')
        node = Node(value)    # 构造节点
        tailnode = self.tailnode
        if tailnode is None:    # 还没有 append 过,length = 0, 追加到 root 后
            self.root.next = node
        else:     # 否则追加到最后一个节点的后边,并更新最后一个节点是 append 的节点
            tailnode.next = node
        self.tailnode = node
        self.length += 1

    def appendleft(self, value):
        if self.maxsize is not None and len(self) >= self.maxsize:
            raise Exception('LinkedList is Full')
        node = Node(value)
        if self.tailnode is None:  # 如果原链表为空,插入第一个元素需要设置 tailnode
            self.tailnode = node

        headnode = self.root.next
        self.root.next = node
        node.next = headnode
        self.length += 1

    def __iter__(self):
        for node in self.iter_node():
            yield node.value

    def iter_node(self):
        """遍历 从 head 节点到 tail 节点"""
        curnode = self.root.next
        while curnode is not self.tailnode:    # 从第一个节点开始遍历
            yield curnode
            curnode = curnode.next    # 移动到下一个节点
        if curnode is not None:
            yield curnode

    def remove(self, value):    # O(n)
        """ 删除包含值的一个节点,将其前一个节点的 next 指向被查询节点的下一个即可
        :param value:
        """
        prevnode = self.root    #
        for curnode in self.iter_node():
            if curnode.value == value:
                prevnode.next = curnode.next
                if curnode is self.tailnode:  # NOTE: 注意更新 tailnode
                    self.tailnode = prevnode
                del curnode
                self.length -= 1
                return 1  # 表明删除成功
            else:
                prevnode = curnode
        return -1  # 表明删除失败

    def find(self, value):    # O(n)
        """ 查找一个节点,返回序号,从 0 开始
        :param value:
        """
        index = 0
        for node in self.iter_node():   # 我们定义了 __iter__,这里就可以用 for 遍历它了
            if node.value == value:
                return index
            index += 1
        return -1    # 没找到

    def popleft(self):    # O(1)
        """ 删除第一个链表节点
        """
        if self.root.next is None:
            raise Exception('pop from empty LinkedList')
        headnode = self.root.next
        self.root.next = headnode.next
        self.length -= 1
        value = headnode.value

        if self.tailnode is headnode:
            self.tailnode = None
        del headnode
        return value

    def clear(self):
        for node in self.iter_node():
            del node
        self.root.next = None
        self.length = 0
        self.tailnode = None

    def reverse(self):
        """反转链表"""
        curnode = self.root.next
        self.tailnode = curnode
        prevnode = None

        while curnode:
            nextnode = curnode.next
            curnode.next = prevnode

            if nextnode is None:
                self.root.next = curnode

            prevnode = curnode
            curnode = nextnode


def test_linked_list():
    ll = LinkedList()

    ll.append(0)
    ll.append(1)
    ll.append(2)
    ll.append(3)

    assert len(ll) == 4
    assert ll.find(2) == 2
    assert ll.find(-1) == -1

    assert ll.remove(0) == 1
    assert ll.remove(10) == -1
    assert ll.remove(2) == 1
    assert len(ll) == 2
    assert list(ll) == [1, 3]
    assert ll.find(0) == -1

    ll.appendleft(0)
    assert list(ll) == [0, 1, 3]
    assert len(ll) == 3

    headvalue = ll.popleft()
    assert headvalue == 0
    assert len(ll) == 2
    assert list(ll) == [1, 3]

    assert ll.popleft() == 1
    assert list(ll) == [3]
    ll.popleft()
    assert len(ll) == 0
    assert ll.tailnode is None

    ll.clear()
    assert len(ll) == 0
    assert list(ll) == []


def test_linked_list_remove():
    ll = LinkedList()
    ll.append(3)
    ll.append(4)
    ll.append(5)
    ll.append(6)
    ll.append(7)
    ll.remove(7)
    print(list(ll))


def test_linked_list_reverse():
    ll = LinkedList()
    n = 10
    for i in range(n):
        ll.append(i)
    ll.reverse()
    assert list(ll) == list(reversed(range(n)))


def test_linked_list_append():
    ll = LinkedList()
    ll.appendleft(1)
    ll.append(2)
    assert list(ll) == [1, 2]


if __name__ == '__main__':
    test_linked_list()
    test_linked_list_append()
    test_linked_list_reverse()

最后可以通过pytest,会自动跑test开头的函数

pytest linked_list.py
======================================================================================================== test session starts ========================================================================================================
platform win32 -- Python 3.6.5, pytest-4.4.1, py-1.8.0, pluggy-0.9.0
rootdir: E:\project\python\data-structure-and-algorithm\
collected 4 items                                                                                                                                                                                                                    

linked_list.py ....                                                                                                                                                                                                            [100%]

===================================================================================================== 4 passed in 0.05 seconds ======================================================================================================

循环双链表

单链表能看到很明显的问题,单链表虽然 append 是 O(1),但是它的 find 和 remove 都是 O(n)的, 因为删除你也需要先查找,而单链表查找只有一个方式就是从头找到尾,中间找到才退出。 这里我之前提到过如果要实现一个 lru 缓存(访问时间最久的踢出),我们需要在一个链表里能高效的删除元素, 并把它追加到访问表的最后一个位置,这个时候单链表就满足不了了, 因为缓存在 dict 里查找的时间是 O(1),你更新访问顺序就 O(n)了,缓存就没了优势。

这里就要使用到双链表了,相比单链表来说,每个节点既保存了指向下一个节点的指针,同时还保存了上一个节点的指针。

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

循环双端链表操作平均时间复杂度
cdll.append(value)O(1)
cdll.appendleft(value)O(1)
cdll.remove(node),注意这里参数是 nodeO(1)
cdll.headnode()O(1)
cdll.tailnode()O(1)

给出完整循环双链表测试代码

# coding:utf-8
"""
@author:Yang Fan
@个人网站:https://heroyf.club
"""


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


class CircualDoublelinkedlist(object):
    def __init__(self, maxsize=None):
        self.maxsize = maxsize
        node = Node()
        node.prev, node.next = node, node
        self.root = node
        self.length = 0

    def __len__(self):
        return self.length

    def headnode(self):
        return self.root.next

    def tailnode(self):
        return self.root.prev

    def append(self, value):
        if self.maxsize is not None and len(self) > self.maxsize:
            raise Exception("full")
        node = Node(value=value)
        tailnode = self.root.prev

        tailnode.next = node
        node.prev = tailnode
        node.next = self.root
        self.root.prev = node

        self.length += 1

    def appendleft(self, value):
        if self.maxsize is not None and len(self) > self.maxsize:
            raise Exception("full")
        node = Node(value=value)

        if self.root.next is self.root:  # empth double_linked_list
            node.next = self.root
            node.prev = self.root
            self.root.next = node
            self.root.prev = node
        else:
            node.prev = self.root
            headnode = self.root.next
            node.next = headnode
            headnode.prev = node
            self.root.next = node
        self.length += 1

    def remove(self, node):  # O(1)
        if node is self.root:
            return
        else:
            node.prev.next = node.next
            node.next.prev = node.prev
        self.length -= 1
        return node

    def iter_node(self):
        if self.root.next is self.root:
            return
        curnode = self.root.next
        while curnode.next is not self.root:
            yield curnode
            curnode = curnode.next
        yield curnode

    def __iter__(self):
        for node in self.iter_node():
            yield node.value

    def iter_node_reverse(self):
        if self.root.prev is self.root:
            return
        curnode = self.root.prev
        while curnode.prev is not self.root:
            yield curnode
            curnode = curnode.prev
        yield curnode


def test_double_linkedlist():
    dll = CircualDoublelinkedlist()
    assert len(dll) == 0
    dll.append(0)
    dll.append(1)
    dll.append(2)

    assert list(dll) == [0, 1, 2]

    assert [node.value for node in dll.iter_node()] == [0, 1, 2]
    assert [node.value for node in dll.iter_node_reverse()] == [2, 1, 0]

    headnode = dll.headnode()
    assert headnode.value == 0
    dll.remove(headnode)
    assert len(dll) == 2
    assert [node.value for node in dll.iter_node()] == [1, 2]

    dll.appendleft(0)
    assert [node.value for node in dll.iter_node()] == [0, 1, 2]

测试结果

pytest double_linked_list.py
================================================================================= test session starts =================================================================================
platform win32 -- Python 3.6.5, pytest-4.4.1, py-1.8.0, pluggy-0.9.0
rootdir: E:\project\python\data-structure-and-algorithm\
collected 1 item                                                                                                                                                                       

double_linked_list.py .                                                                                                                                                          [100%]

============================================================================== 1 passed in 0.03 seconds ===============================================================================

版权声明:本文为原创文章,版权归 heroyf 所有。
本文链接: https://heroyf.club/2019/04/python_linkedlist/


“苹果是给那些为了爱选择死亡的人的奖励”