数据结构之链表

MeteoAI

发布于 2019-09-24 13:21:35

5650

发布于 2019-09-24 13:21:35

文章被收录于专栏：MeteoAI

数据结构是一种分析、存储、组织数据的方法与逻辑，它考虑了数据之间的特性与相互关系，简单地说，数据结构就是对数据与算法的研究。数据结构分为8类有：数组、栈、队列、链表、树、散列表、堆、图。

对我们个人而言，掌握数据结构是码农进入大厂的敲门砖，也是我们非计算机专业进入大厂的拦路虎。掌握数据结构能够锻炼我们的抽象能力，分析能力，逻辑推理能力。工作时虽然可能用不到，但是面试大厂时考察数据结构是逃不掉的。

俗话说，亡羊补牢，为时不晚，我们的能力没有比计算机专业的差多少，只是暂时没有学相关的课程罢了。

即使我们不进入互联网行业，学习数据结构也对我们大有脾益，锻炼我们的coding能力。

下面不废话了，直接上'链表'吧！

链表（Linked List）是由许多相同数据类型的数据按照特定顺序排列而成的线性表 [1]，特性是各个数据项在计算机内存中的位置是不连续且随机的，优点是插入和删除都相当方便，有新数据加入就向系统申请一块内存空间，而数据被删除后，就可以把这块内存还给系统，加入和删除都不需要移动大量的数据。其缺点是设计数据结构时较为麻烦，在查找数据时，无法像静态数据（如数组）那样可以随时读取数据，必须按照顺序查找到该数据为止。从图中我们看到，链表与我们熟悉的数组相对比，数组需要一块连续的内存空间来存储，一经声明就要占用整块连续内存空间，对内存的要求比较高，如果声明的数组过大，系统可能没有足够的连续空间分配给它。而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。

数组与链表的区别（图片来自《极客时间》某付费课程）

单向链表

在动态分配内存空间时，最常用的就是’单向链表‘。一个单向链表的节点由数据字段和指针组成，其中指针将会指向下一个元素在内存中的位置。

在单向列表中，第一个节点也称为头节点[3]，其存储的位置叫做链表头指针，

指向最后一个节点的指针设置为None,表示链表尾，不指向任何地方。

链表头指针非常重要，因为所有节点只知道自身的下一个节点的地址。只有知道链表头指针，才可以循环整个链表。

你可以把链表想象成一个队伍，队伍中的每个人都只知道自己后面的人是谁，所以当我们希望知道排在第 k 位的人是谁的时候，我们就需要从第一个人开始，一个一个地往下数。

也可以想象我们有一辆特别的火车，火车有火车头（头指针），车箱（节点数据）和挂钩（指针），且每个车箱后面的挂钩只能挂住唯一的一个后面的车厢，最后一节车厢的挂钩不挂任何东西，也就是没有。

Python实现单向链表

首先我们要用'类'定义一个节点，这个节点要包含数据和后继指针（记录下个结点地址的指针）。init() 方法是一种特殊的方法，被称为类的构造函数或初始化方法，当创建了这个类的实例时就会调用该方法。

self 代表类的实例，self 在定义类的方法时是必须有的，虽然在调用时不必传入相应的参数。

class Node: # 创建类    def __init__(self, data: int, next_node = None):#构造函数，根据类创建对象时自动执行        self.data = data # 类变量        self._next = next_node

我们尝试实例化这个Node

my_node_1 = Node(9)print('第一个节点为：',my_node_1)print('第一个节点内的数据为：',my_node_1.data)

第一个节点为：<__main__.Node object at 0x000002044FE07E10>第一个节点内的数据为：9

此时只有一个节点，所以my_node_1的后继指针为空

print('下一个节点为空：',my_node_1._next)

下一个节点为空：None

我们再产生一个节点，并和第一个节点连接起来,此时，第一个节点的后继节点就不为空了

my_node_2 = Node(66)my_node_1._next=my_node_2print(my_node_1._next.data)

下面再定义一个单向链表的类

from typing import Optionalclass SinglyLinkedList:    def __init__(self): # 定义头节点，实例化时自动执行        self._head = None

再定义链表的如下方法（method）:

如果我们想在通过值（value）寻找节点，一定要从头节点开始遍历

    def find_by_value(self, value: int) -> Optional[Node]:                p = self._head # 从头开始遍历,直到节点的值等于要找的值                while p and p.data != value:                    p = p._next                return p # 最终返回符合要求的的p,即p.data 等于value 的节点

如果我们想通过索引来查找链表中的数据，则

    def find_by_index(self, index:int) ->Optional[Node]:            p = self._head            position = 0            while p and position != index:                p=p._next                position+=1            return p

如果我们从头部节点插入节点,要将链表的头节点赋值给新节点的后继指针，再把新节点赋值给头部节点:

    def insert_node_to_head(self, new_node:Node):            if new_node:                new_node._next = self._head #当前节点成了下一个节点，所以把当前头节点 赋值给 新节点指向的下个节点
                self._head = new_node       #新节点赋值给头节点，也就是新节点成了头节点

如果我们要直接在头部节点插入值，我们可以直接调用上面的insert_node_to_hea

    def insert_value_to_head(self, value :int):        new_node = Node(value)        self.insert_node_to_head(new_node)

如果我们要怎么某个节点之前插入新节点，需要考虑如下几个特殊情况

1 如果头节点或者目标节点或者新节点为空，则直接返回

2 如果头节点 == 目标节点，即目标节点就是头节点，则直接在头部插入，利用上面的insert_node_to_head方法.

3 上面两种都不是，令当前指针位置为头指针（current = self._head），从头节点开始遍历，直到当前节点的后继节点不为空且不为当前节点，就一直往下遍历。也就是说，当前节点的后继节点为目标节点时，遍历停止。

停止时，当前节点的后继节点若为空，则直接返回。如果不是空，则将目标节点赋值给新节点的后继指针，新节点赋值给当前节点的后继指针。如下图 :

    def insert_node_before(self, node: Node, new_node: Node):        if not self._head or not node or not new_node:            return        if self._head == node:            self.insert_node_to_head(new_node)            return        current = self._head        while current._next and current._next != node:            current = current._next        if not current._next:  # node is not even in the list            return        new_node._next = node        current._next = new_node

在某个目标节点之后插入新节点

需要考虑特殊情况，如果目标节点为空或者新节点为空，则直接返回。

def insert_node_after(self, node: Node, new_node: Node):        if not node or not new_node:            return        new_node._next = node._next        node._next = new_node

删除某个节点

首先判断如果self._head 为空或者节点node为空，则直接返回

如果不为空，则从头部开始遍历，直到目标节点的前一个节点处，此时的current._next需要重新赋值为node._nex。

    def delete_by_node(self, node: Node):        if not self._head or not node:            return        if node._next:            node.data = node._next.data            node._next = node._next._next            return
        current = self._head # 从头开始遍历        while current and current._next != node:            current = current._next        if not current:              return        current._next = node._next

以上代码总结为：

from typing import Optionalclass Node: # 定义节点    def __init__(self, data: int, next_node=None):        self.data = data        self._next = next_node

class SinglyLinkedList:  # 链表类
    def __init__(self): # 定义头        self._head = None
    def find_by_value(self, value: int) -> Optional[Node]:        p = self._head # 从头开始遍历        while p and p.data != value:             p = p._next        return p # 最终返回符合要求的的p,即p.data 等于value 的节点
    def find_by_index(self, index: int) -> Optional[Node]:        p = self._head        position = 0        while p and position != index:            p = p._next            position += 1        return p
    def insert_value_to_head(self, value: int):        new_node = Node(value)        self.insert_node_to_head(new_node)
    def insert_node_to_head(self, new_node: Node):        if new_node:            new_node._next = self._head            self._head = new_node
    def insert_value_after(self, node: Node, value: int):        new_node = Node(value)        self.insert_node_after(node, new_node)
    def insert_node_after(self, node: Node, new_node: Node):        if not node or not new_node:            return        new_node._next = node._next        node._next = new_node
    def insert_value_before(self, node: Node, value: int):        new_node = Node(value)        self.insert_node_before(node, new_node)
    def insert_node_before(self, node: Node, new_node: Node):        if not self._head or not node or not new_node:            return        if self._head == node:            self.insert_node_to_head(new_node)            return        current = self._head        while current._next and current._next != node:            current = current._next        if not current._next:  # node is not even in the list            return        new_node._next = node        current._next = new_node
    def delete_by_node(self, node: Node):        if not self._head or not node:            return        if node._next:            node.data = node._next.data            node._next = node._next._next            return        # node is the last one or not in the list        current = self._head        while current and current._next != node:            current = current._next        if not current:  # node not in the list            return        current._next = node._next
    def delete_by_value(self, value: int):        if not self._head or not value:            return        fake_head = Node(value + 1)        fake_head._next = self._head        prev, current = fake_head, self._head        while current:            if current.data != value:                prev._next = current                prev = prev._next            current = current._next        if prev._next:            prev._next = None        self._head = fake_head._next  # in case head.data == value

链表反转

思想是建立2个变量，新的反向头节点reservsed_head, 当前节点current, 从head开始，每次循环将相邻两个结点的方向反转。当整个链表循环遍历过一遍之后，链表的方向就被反转过来了。

其中 reservsed_head = current 是为了保存当前节点,防止丢失

reservsed_head._next = reservsed_head 是为了将方向反转

current = current._next 是为了依次往前遍历。

from typing import Optionalclass Node:    def __init__(self, data: int, next=None):        self.data = data        self._next = next# Reverse singly-linked list# 单链表反转# Note that the input is assumed to be a Node, not a linked list.def reverse(head: Node) -> Optional[Node]:    reversed_head = None    current = head    while current:        reversed_head, reversed_head._next, current = current, reversed_head, current._next    return reversed_head
if __name__ == '__main__':    print('链表反转')    link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))
    p = reverse(link)  # 输出链表 4->3->2->1->None    while p:        print(p.data)        p = p._next

链表反转987654321

检测环

新建一个快指针和一个慢指针，慢指针每次移动一个节点，快指针每次移动两个节点。如果快指针到打了尾部时，快指针和慢指针相等，则存在环。

例如链表A->B->C->D->B->C->D，两个指针最初都指向节点A，进入第一轮循环，指针1移动到了节点B，指针2移动到了C。第二轮循环，指针1移动到了节点C，指针2移动到了节点B。第三轮循环，指针1移动到了节点D，指针2移动到了节点D，此时两指针指向同一节点，判断出链表有环。

def has_cycle(head: Node) -> bool:    slow, fast = head, head    while fast and fast._next:        slow = slow._next        fast = fast._next._next        if slow == fast:            return True    return False

link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))print(has_cycle(link))

false

删除倒数第N个节点

设置2个指针（fast和slow）同时指向第一个节点 [2]，让第一个指针fast向前移动n次，之后第二个指针slow和指针fast开始一起移动，直到fast为空或者fast->next为空，此时指针slow指向要删除节点的前一个节点（如果要删除的不是第一个节点）。

# 删除倒数第n个节点。假设n大于0def remove_nth_from_end(head: Node, n: int) -> Optional[Node]:    fast = head #第一个指针    count = 0    while fast and count < n:# 移动n次        fast = fast._next        count += 1    if not fast and count < n:  # not that many nodes        return head    if not fast and count == n: # 如果节点正好有n个，删除倒数n个就是删除第一个，所以返回head._next        return head._next
    slow = head    while fast._next: # 一起移动，直到fast._next为空        fast, slow = fast._next, slow._next    slow._next = slow._next._next#对指针slow跳过下个节点，重新指向第二个节点    return head
##测试上述代码，发现已经成功删除倒数第三个值 7link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))pp=remove_nth_from_end(link, 3)while pp:    print(pp.data)    pp = pp._next

12345689

找到链表中间节点

设置一个快指针，一个慢指针，并且快指针的步长为慢指针的两倍，当快指针到达结尾时，慢指针一定在中间。

def find_middle_node(head: Node) -> Optional[Node]:    slow, fast = head, head    fast = fast._next if fast else None    while fast and fast._next:        slow, fast = slow._next, fast._next._next    return slow
link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))print(find_middle_node(link).data)

本文代码已上传GitHub： https://github.com/deepwindlee/My-data-structure/blob/master/0918%E9%93%BE%E8%A1%A8%20linked%20list.ipynb