数组与链表

数组与链表，由于逻辑结构上的相同，往往被相提并论，统称线性表。并且这两者的实现方式将是后面所有数据结构实现的基础，至关重要。

数组

数组是一种能存储多个对象的容器对象，又称顺序表。从物理结构(内存排布)来看，紧凑连续。由于这种物理结构使得数组能够通过简单的加法计算，算出任何一个储存的任何一个对象的内存地址，所以数组读写任何一个存储的对象的时间复杂度都是O(1)。不过我们想在数组中间删除、增加一个元素，需要移动其后的所有元素，这意味插入或者删除操作的时间复杂度会是O(n)。

也因为这种物理结构，导致数组在使用之前必须要申请足够的内存用于将要存储的对象。当申请的内存满了之后，还要增加对象进去就只能重新申请内存，然后将原本储存好的对象移动过去。所以每次申请多少内存是一个哲学问题——你不能一次申请太多，不然会浪费，因为申请的内存在数组被销毁之前是绝对不会给其他东西用的；但又不能一次申请太少，否则多次的申请新内存消耗的资源也很多。

好在Python替我们实现了这些复杂的东西，我们只需要使用List这个内置类型就可以获得数组。

不过值得注意的是，Python在申请数组的可用内存这一点，也没有太好的办法。所以如果我们要储存的对象有大幅度的数量波动，链表或许是一个更好的选择。

链表

相信见过锁链的人都知道，一个铁链子由很多个相同的节点连接而成。而链表，顾名思义，也同样如此。

每个节点都由两部分组成，一是该节点所携带的数据，一是这个节点指向的下个节点。

class Node:
    """
    链表节点
    """

    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next = next_node

    def __str__(self):
        return f"[{self.data}]"

将任意整数个节点通过它们的next顺序连接，就组成了链表。

可以轻易的知道，链表的存储是不连续的，它没有到底要申请多少内存才合适的烦恼。在储存的对象数量变化很大时，链表的优势将会十分明显。当一个节点不再有用时，可以直接释放掉它。

但相比于数组而言，链表无法在O(1)的时间复杂度下找到任意位置的元素。并且相同数量的储存对象，链表所占的内存会更大一些。

class NormalLinkList:
    def __init__(self):
        self.node = None
        self.length = 0

    def __str__(self):
        point = self.node
        s = f"LinkList: {point}"
        if point is not None:
            while point.next is not None:
                point = point.next
                s += f" -> {point}"
        return s

    def insert(self, node: Node, index: int):
        if index > self.length:
            raise IndexError("超出了链表长度")
        if index == 0:
            node.next = self.node
            self.node = node
        else:
            point = self.node
            for _ in range(index-1):
                point = point.next
            point.next = node
        self.length += 1

    def remove(self, index: int):
        if index > self.length - 1:
            raise IndexError("超出了链表长度")
        if index == 0:
            self.node = self.node.next
        else:
            point = self.node
            for _ in range(index-1):
                point = point.next
            point.next = point.next.next
        self.length -= 1

以上是一个很简单的链表类，实现了插入和删除。

此时我们注意到这种链表实现稍微有点不够顺畅，我们总是要特殊的考虑链表中头节点的状态。并且如果我只是想操作链表最后一个元素的时候，每次都要遍历到最后，有些不够优雅。

如何解决这些问题呢？

带头节点的链表

为了更加简单的对列表进行操作，便有了带头节点的链表。

这种链表相比于普通的链表，只多了一个头节点。头节点不属于链表储存内容，它只作为一个占位节点而存在。正由于这个头结点的存在，使得链表操作变得简单起来。

看看下面的代码，并与上面的NormalLinkList作比较。

class HeadLinkList:
    """
    带头节点的链表
    """

    def __init__(self):
        self.head = Node()
        self.length = 0

    def __str__(self):
        point = self.head
        s = "LinkList: [head]"
        while point.next is not None:
            point = point.next
            s += f" -> {point}"
        return s

    def insert(self, node: Node, index: int):
        if index > self.length:
            raise IndexError("超出了链表长度")
        point = self.head
        for _ in range(index):
            point = point.next
        node.next = point.next
        point.next = node
        self.length += 1

    def remove(self, index: int):
        if index > self.length - 1:
            raise IndexError("超出了链表长度")
        point = self.head
        for _ in range(index):
            point = point.next
        point.next = point.next.next
        self.length -= 1

双向链表

前面提到了一个问题，那就是“如果我只是想操作链表最后一个元素的时候，每次都要遍历到最后”。可以对于带头节点的链表做一个扩展来解决这个问题。

双向链表的每个节点都有分别指向前一个节点和后一个节点的两个值，并且有头节点和尾节点。当我们需要操作对应位置的元素时，可以先判断这个元素离头节点近还是尾节点近，有效的减少遍历的次数。

由于双向链表的节点拥有两个固定节点，所以为了避免两个固定节点之间的循环引用导致链表无法被回收。我们需要特殊定义一下(如果不记得weakref的，可以看看前置知识：Python对象的管理)

class DoublyNode:
    """
    双向链表节点
    """

    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next: DoublyNode = next_node
        self.__pre = None

    @property
    def pre(self):
        return self.__pre

    @pre.setter
    def pre(self, node):
        self.__pre = weakref.ref(node)

    @pre.getter
    def pre(self):
        return self.__pre()

    def __str__(self):
        return f"[{self.data}]"

如此定义之后，就可以避免头尾节点互相引用导致的内存泄漏。接下来看具体的双向链表定义

class DoublyLinkedList:
    """
    双向链表
    """

    def __init__(self):
        self.head = DoublyNode()
        self.tail = DoublyNode()
        self.head.next = self.tail
        self.tail.pre = self.head
        self.length = 0

    def __str__(self):
        point = self.head
        s = "DoublyLinkList: [head]"
        for _ in range(self.length):
            point = point.next
            s += f" <-> {point}"
        s += " <-> [tail]"
        return s

    def insert(self, node: DoublyNode, index: int):
        if index > self.length:
            raise IndexError("超出了链表长度")
        if index >= self.length // 2:
            point = self.tail
            for _ in range(self.length-index+1):
                point = point.pre
        else:
            point = self.head
            for _ in range(index):
                point = point.next
        node.next = point.next
        point.next = node
        node.pre = point
        if node.next is not None:
            node.next.pre = node
        self.length += 1

    def remove(self, index: int):
        if index > self.length - 1:
            raise IndexError("超出了链表长度")
        if index >= self.length // 2:
            point = self.tail
            for _ in range(self.length-index+1):
                point = point.pre
        else:
            point = self.head
            for _ in range(index):
                point = point.next
        point.next = point.next.next
        point.next.pre = point
        self.length -= 1

看起来很完美。我们每次插入或者删除，最坏的情况也只需要遍历n/2次。当然，双向链表的妙用不止于此。