入门数据结构和算法-链表

大学时期学习的计算机相关的一些基础知识都已经忘记了，能记起来的只有一些模糊的名字，最近在刷leetcode，碰到一些数据结构相关的题是必须的，所有开始把忘记的东西再捡起来

前置知识： 指针、时间复杂度、空间复杂度

什么是链表

在计算机科学中，链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（”links”）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的访问和操作。程序语言或面向对象语言，如C/C++和Java依靠易变工具来生成链表。

（以上内容是是从维基百科Copy来的）

种类

1. 单向链表
2. 双向链表
3. 循环链表
4. 块状链表
5. 其它扩展

其实最常见到的也就是单向、双向。

单向链表

这个是最简单，也是最容易的理解的，链表中的数据是以结点来表示的，每个结点由元素和指针构成，每一个结点的指针指向了下一个元素。

代码：

type Node struct {
    Value any
    Next &Node
}

n1 := Node{
    Value:"n1",
    Next:&n2,
}

n2 := Node{
    Value:"n2",
    Next:&n3,
}

n3 := Node{
    Value:"n3",
    Next:nil,
}

n1、n2、n3就组成了一个链表，n1是头， n3是尾（n2没有指向任何节点了）

效率

这应该技术是所有算法的核心了吧， 都是为了提高效率而提炼出来的

单链表插入和删除算法，是由两部分组成：

遍历查找第 i 个节点
插入和删除节点。
时间复杂度都是 O (n)；

从第 i 个位置，插入 10 个节点：
顺序存储结构：每一次插入都需要移动 n-1 个节点，每次都是 O (n)。
单链表：需要在第一次时，找到第 i 个位置的指针，通过赋值移动指针，时间复杂度都是 O (1)。

对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

使用场景

作为一个三流码农，每天写业务，貌似很少遇到，尴尬！