何谓链表？

链表(Linked list) 是一种基础的数据结构，是一种线性表。链表的每个节点由一个数据内容 和一个指针组成，指针的作用就是指向下一个数据内容存放的地址。因此，链表在存储上并不会按顺序存储。而是通过指针的互相关联之间的关系。

链表的特点

因为链表在设计上是通过指指针来关联的，所以链表有以下的性质：

  1. 查找的时间复杂度为O(n)
  2. 插入的时间复杂度为O(1)
  3. 删除的时间复杂度为O(1)

因为链表的这个特性，特别适合在查找少，插入和删除多的时候使用。
查找的时间复杂度为O(n)的原因是链表的存储结构造成的。链表的存储结构克服了数组需要预先知道数据大小的缺点，利用指针的存在来充分利用计算机的内存空间，实现了灵活的内存的动态管理。但因为链表不是按顺序存储的，所以不能像数组一样，通过下标来直接访问元素，只能从头开始，一个个通过指针来查找元素，所以时间复杂度上为O(n)。同时也因为指针的存在，存储相同大小的数据，链表比数组要花费更多的空间。
插入和删除的时间复杂度为O(1)，也是因为在链表中插入和删除的时候，不需要移动链表中的数据，只需要修改指针指向即可。
链表最明显的好处就是常规数组排列关联项目的方式可能不同于这些项目在记忆体或磁盘上的顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

结构

单向链表

单向链表是所有的链表中最简单的，它只包含有两个域：信息域和指针域。链表元素之间通过指针域中的指针的相关关联。除了最后一个节点外，每个节点的指针都指向下一个节点，而最近一个节点把向一个空值。因为在单向链表中只保存指向下一个节点的指针，所以在单向链表中，只可以通过一个方向遍历链表。下面是一个单向链表的示例：
image.png
TypeScript代码示例：

  1. class LinkedList<T> {
  2.   value: T;
  4.   next: LinkedList<T> | null;
  6.   constructor(v: T) {
  7.     this.value = v;
  8.     this.next = null;
  9.   }
  10. }

Java代码示例：

  1. public class LinkedList<T> {
  2.     T value;
  3.     LinkedList<T> next;
  5.     LinkedList(T v){
  6.         value = v;
  7.         next = null;
  8.     }
  9. }
  1. Kotlin代码示例：
  1. class LinkedList<T> {
  2.     var value: T;
  3.     var next: LinkedList<T>?;
  5.     constructor(v: T) {
  6.         this.value = v;
  7.         this.next = null;
  8.     }
  9. }

单向链表的操作