链表脑图

我们常见的数据结构，不管是队列，栈等线性结构，还是树，图等非线性结构，从底层来看都是数组和链表。
数组在内存中是连续的存储：

而链表是随心所欲的存在内存中的，不一定连续：

数组通常大小也是固定的，通过下标就可以随机访问到某一个元素。
链表不一定连续，一般链表通过一个next的指针来查找下个元素。链表的结构一般是这样：

interface ListNode<T>
{
    data: T;
    next: ListNode<T>;
}

因为链表结构增删起来非常容易，所以非常适合增删频繁且需要一定顺序的场景。

通常情况下，链表只有一个后驱节点next,如果是双向链表还会有一个前驱节点pre.二叉树就是一个双向链表。

链表的基本操作

刷链表类的算法题，必须首先了解下链表的一些基本操作，以及对应的复杂度。

• 插入
  只需要考虑插入位置的前驱节点和后继节点（双向链表的情况下需要更新后继节点）即可，其它节点不受影响，因此在给定指针进行插入的情况下时间复杂度是O(1).这里的给定指针，指的是插入位置的前驱节点。
  伪代码：

temp = 待插入位置的前驱节点.next;
待插入位置的前驱节点.next = 待插入指针；
待插入指针.next = temp;

如果没有给出节点指针，我们第一步要先进行遍历找到插入位置，这个时候的时间复杂度是O(n).
PS：
提示1：要考虑头尾指针的情况
提示2：新手建议先画图，再写代码。熟练后自然无需画图。

• 删除
  只需把待删除节点的前序节点的next指针改为指向其下下个节点即可，删除时要注意边界条件。
  伪代码：

待删除节点的前驱节点.next = 待删除节点的前驱节点.next.next;

PS:
提示1：考虑头尾指针的情况
提示2：新手建议先画图，再写代码。熟练后自然无需画图。

• 遍历
  遍历直接上伪代码(迭代)：

当前指针 = 头指针；
while(当前指针 != Null)
{
    print(当前节点);
    当前指针 = 当前指针.next;
}

伪代码(迭代)：

dfs(当前指针)
{
    if(当前指针 == null) return;
    print(当前节点)；
    return dfs(当前指针.next)
}

数组和链表在算法题中的差异

数组的遍历：

for(int i = 0; i < arr.size(); i++)
{
    print(arr[i]);
}

链表的遍历：

for(ListNode cur = head; cur != null; cur = cur.next)
{
    print(cur.val);
}

看起来是非常的相似，只在细微的操作有不同。
数组是索引++
链表是cur = cur.next

如果我们需要做一个逆序遍历呢？
数组：

for(int i = arr.size() - 1; i >= 0; i--)
{
    print(arr[i]);
}

链表：

for(ListNode cur = tail; cur != null; cur = cur.pre)
{
    print(cur.val);
}

这里需要链表有前序指针，这种双向链表在力扣中的题目很少，大多数情况下你无法拿到前序指针，所以有时候需要自行记录一个 前驱节点。

如果给末尾加一个元素：
数组：

arr.push(1);

链表的话，很多语言没有内置的类型，比如力扣中就常用如下的类来模拟：

public class ListNode
{
    int val;
    ListNode next;
    ListNode(){};
    ListNode(int val) {this.val = val};
    ListNode(int val, ListNode next){ this.val = val; this.next = next;}
}

在链表中，我们是无法直接调用push的，那么给链表的尾部增加一个元素,可以这样：

tail.next = new ListNode(‘tailNew’）;
tail = tail.next;

经过上述操作，tail仍然指向了链表尾部。如果有需要你新建或复制一个数组的时候，这个方法就派上了用场。

数组的push方法，底层的实现可能也是类似的办法：

arr.len = arr.len + 1;
arr[len - 1] = 'tailNew'

通过以上的介绍，可以总结出，数组和链表在逻辑上有很多相似之处，更多不同的是一些使用场景和操作细节。对于做题而言，我们通常关注的是操作细节，下面我们将会更细一步的介绍。
链表有它自己独特的意义，所以在做题时，能用链表的地方，尽量不要用数组去代替。