数据结构基础——链表

链表在比赛中是常考的，也是很基础的内容。

链表知识点

1. 单链表
2. 双向链表
3. 循环链表

链表用来干什么

首先，我们得知道什么是链表？然后，才能知道为什么要使用链表，链表拿来干啥？最后咱们才能学会使用链表。

What is 链表？

链表是线性表的链式存取的数据结构，是一种链式存取的数据结构，是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：数据域（数据元素的映象）+ 指针域（指示后继元素存储位置），数据域就是存储数据的存储单元，指针域就是连接每个结点的地址数据。 相比于线性表顺序结构，操作复杂。

从定义来看，可能有些难以理解，下面利用两张图来就对比一下数组，也就是线性表的顺序存储结构和链表在内存中存储 1-9 号元素的形式：

• 顺序存储
  
• 链式存储
  

链式存储的内存地址的是随机分配的，他们每个节点地址之间是没有任何关联的。而且在每个新的节点在产生之前，我们都是不知道他的地址的。

深入链表

如果光看原理，可能不是太理解是什么意思，由此，我们利用一个题例来加深一下理解。

小王子有一天迷上了排队的游戏，桌子上有标号为 1-10 按顺序摆放的 10 个玩具，现在小王子想将它们按自己的喜好进行摆放。小王子每次从中挑选一个好看的玩具放到所有玩具的最前面。已知他总共挑选了 M 次，每次选取标号为 X 的玩具放到最前面，求摆放完成后的玩具标号。

给出一组输入，M=8 共计排了 8 次，这 8 次的序列为 9，3，2，5，6，8，9，8。 求最终玩具的编号序列。

阅读完题目，题意还算比较好理解，下面开始解答一下：

1. 首先我们要开一个长度为 11 的数组，因为下标要从 1 开始所以 0 — 10 共计 11 个元素。

a[11] = {0,1,2,3,4,5,6,7,8,9,10}

2. 然后根据题意我们要写一个查找函数：

//伪代码形式
int Funciton 查找(X)
{
    range i in(1, 10) //循环从x位置到2号位置

        if data[i] == x : //找到X返回
                          return i
                              end if end range
}

简单描述一下这个过程:

首先是步进查找比如查找值为 5 元素的下标：

通过寻找函数，找到元素后返回下标，值为 5。然后进行下一步。

3. 最后我们找到元素后要进行插入操作

void Function 移动(L)
{ //移动函数

    //拿走了X,X在L位置,所以将L-1向后移动到L,依次向后移动空处最前面的位置
    temp = data[L]

        range i in(L, 2)      //循环从L位置到2号位置
        data[i] = data[i - 1] //向后移动
        end range

            data[i] = temp
}	

我们还是以 5 为例，要把 5 移到到首位，肯定不是把 5 放到第一位就行。

对于目前竞赛来说，我们暂且不考虑时间复杂度的问题，能做出来即可！

模拟计算过程

• 链表的初始序列：

head-> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> 9 -> 10

我们第一次移动，输入X=9，

• 先查询
  
  此时，已经定位找到X=9的位置，然后删除。
• 删除
  给 9 前面结点的指针赋值为 9 的指针，再将 9 删除。

head-> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8  -> 10

• 插入
  新建一个结点, data 部分为 9 ,将结点插入链表的首部

head-> 9 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> 10

Python代码实现

简单文字阐述一下整个实现过程：

1. 第一步，我们使用链表的话，要先给出结点的定义，上面讲到链表的形式。
   - 节点定义

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

2. 第二步，我们要先构成一个这样的链表：head-> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

def createLink():
    root = Node(0)
    tmp = root
    for i in range(1, 11):
        tmp.next = Node(i)
        tmp = tmp.next

    tmp.next = None
    return root

3. 第三步，我们要写一个插入函数

def insert(x, linkedroot):
    tmp = Node(x)
    tmp.next = root.next
    root.next = tmp

4. 第四步，我们要写一个删除函数，通过遍历链表删掉想要的数字

def delete(x, root):
    tmp = tmp1 = root

    while tmp != None:
        if tmp.value == x:
            tmp1.next = tmp.next

        tmp1 = tmp
        tmp = tmp.next

5. 第五步，我们写一个遍历输出函数，形式接近于删除函数

def show(root):
    tmp = root.next
    while tmp.next != None:
        print(tmp.value, end=" ")
        tmp = tmp.next
    print("")

6. 最后一步，我们编写主函数

if __name__ == '__main__':

    n = int(input())
    root = createLink()
    # show(root)

    for i in range(n):
        x = int(input())
        delete(x, root)
        insert(x, root)
        show(root)

带入示例的参数可得：

完整版Python代码

小道消息：

在比赛中我们常用 STL 中 link 容器而很少会去定义和使用，我们主要是学会链表的原理和使用，原理学会之后无论是什么样的链表都是可以设计出来的。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/3/6 19:57
# @Author  : 府学路18号车神
# @Email   ：yurz_control@163.com
# @File    : Day01.py

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


def createLink():
    root = Node(0)
    tmp = root
    for i in range(1, 11):
        tmp.next = Node(i)
        tmp = tmp.next

    tmp.next = None
    return root


def insert(x, linkedroot):
    tmp = Node(x)
    tmp.next = root.next
    root.next = tmp


def delete(x, root):
    tmp = tmp1 = root

    while tmp != None:
        if tmp.value == x:
            tmp1.next = tmp.next

        tmp1 = tmp
        tmp = tmp.next


def show(root):
    tmp = root.next
    while tmp.next != None:
        print(tmp.value, end=" ")
        tmp = tmp.next
    print("")


if __name__ == '__main__':

    n = int(input())
    root = createLink()
    # show(root)

    for i in range(n):
        x = int(input())
        delete(x, root)
        insert(x, root)
        show(root)

头结点： 如果链表有头节点，则链式结构中的第一个节点称为头结点，其数据域可以存储一些附加信息，如链表长度；其指针域指向链表中的第一个节点。 经过上面对小王子这个题的讲解，相信大家都对这个链表的有点有了一个初步的认识，我们看到链表的使用确实很方便，在我们不需要随机访线性表里面的元素时，使用链表确实要方便很多，无论是时间复杂度还是空间复杂度都十分优秀。下面我们对线性表的两种存储方式的对比。

写在最后

车神哥也是第一次参赛——研究生组。不知道难度如何，所以尽力准备就好啦！重要的不是结果，而是那段你孤勇奋战的日子，这样的日子，我相信每个人在人生中都很珍贵。或许是高考，或许是考研，或许是为了仅有的一次升职加薪机会等等。

有梦想，每个人都很了不起！

官方刷题练习系统：http://lx.lanqiao.cn/