一、链表

1、定义

链表是由一系列结点组成，结点可运行时动态生成，通过指针链接实现逻辑顺序。

2、分类

（1）单链表

单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next

（2）双向链表

双向链表的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。

（3）循环链表

链表的尾节点指向头节点形成一个环，称为循环链表

（4）对比

双向链表要比单链表占用更多的内存空间。

虽然两个指针比较浪费存储空间，但可以支持双向遍历。

双向链表可以支持O(1)时间复杂度的情况下找到前驱结点，

使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

3、存储

数组在内存中的存储方式是顺序存储（连续存储），

链表在内存中的存储方式则是随机存储（链式存储）。

链表的每一个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎 片空间。

4、操作（增删改查）

public class Node {    int id;    String name;    Node next;    public Node(int id, String name) {        this.id = id;        this.name = name;    }    public Node(int id) {        this.id = id;        this.name = name;    }    @Override    public String toString() {        return "Node{" +                "id=" + id +                ", name='" + name + '\'' +                '}';    }}

（1）增加(时间复杂度：O(1))

【1】尾部插入

把最后一个节点的next指针指向新插入的节点

public void addNode(Node tailNode,Node addNode){    tailNode.next = addNode;}

【2】头部插入

第1步，把新节点的next指针指向原先的头节点

第2步，把新节点变为链表的头节点

public void addHeadNode(Node addNode){    //第一步    addNode.next = head;    //第二步    head = addNode;}

【3】中间插入

第1步，新节点的next指针，指向插入位置的节点

第2步，插入位置前置节点的next指针，指向新节点

public void addMiddleNode(Node addNode,Node preNode){    //第一步    addNode.next = preNode.next;    //第二步   preNode.next = addNode;}

只要内存空间允许，能够插入链表的元素是无限的，不需要像数组那样考虑扩容的问题。

（2）删除(时间复杂度：O(1))

【1】尾部删除

把倒数第2个节点的next指针指向空即可

public void deleteTail(Node secondToLastNode) {    //把倒数第2个节点的next指针指向空    secondToLastNode.next = null;}

【2】头部删除

把链表的头节点设为原先头节点的next指针

public void deleteHeadNode(){    head = head.next;}

【3】中间删除

把要删除节点的前置节点的next指针，指向要删除元素的下一个节点即可

public void deleteMiddleNode(Node preNode){    preNode.next = preNode.next.next;}

（3）更改(时间复杂度：O(1))

找到要更新的节点，然后把旧数据替换成新数据

public void updateNode(Node updateNode,String value){    updateNode.name = value;}

(4) 查询(时间复杂度：O(n))

在查找元素时，链表只能从头节点开始向后一个一个节点逐一查找

public Node getNode(int nodeId){    Node temp = head;    while (true){        if(temp == null){            return null;        }        if(nodeId == temp.id){            return temp;        }        temp = temp.next;    }}

5、优点

插入、删除、更新效率高

省空间

6、缺点

查询效率较低，不能随机访问

7、应用

（1）链表的应用也非常广泛，比如树、图、Redis的列表、LRU算法实现、消息队列等。

（2）

问题：

如何基于链表实现LRU（Least Recently Used最近最少使用）缓存淘汰算法？

思路：

缓存底层用链表实现，链表头结点存储最新访问的数据，尾结点存储最旧访问的数据。如果链表已满，则删除尾结点（最旧数据）。如果有新数据访问，则将新数据放到头部。

实现：

维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。

当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

【1】如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。

【2】如果此数据没有在缓存链表中，又可以分为两种情况：

{1} 如果此时缓存未满，则将此结点直接插入到链表的头部；

{2} 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

因为不管缓存有没有满，我们都需要遍历一遍链表，所以这种基于链表的实现思路，缓存访问的时间复杂度为O(n)。

实际上，我们可以继续优化这个实现思路，比如引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到O(1)。

8、数组链表对比

数组的优势在于能够快速定位元素，对于读操作多、写操作少的场景来说，用数组更合适一些。

链表的优势在于能够灵活地进行插入和删除操作，如果需要在尾部频繁插入、删除元素，用链表更合适一些。

链表在进行元素插入和删除时无需移动链表内的元素，但由于链表不是顺序存储结构，为寻找第i个元素，仍然需要遍历链表，因此时间复杂度为O(n)。

不过，数组和链表的对比，并不能局限于时间复杂度。而且，在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。

数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。

而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法有效预读。

数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。

如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。

链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。

你可能会说，我们Java中的ArrayList容器，也可以支持动态扩容啊？

当我们往支持动态扩容的数组中插入一个数据时，如果数组中没有空闲空间了，就会申请一个更大的空间，将数据拷贝过去，而数据拷贝的操作是非常耗时的。

我举一个稍微极端的例子。如果我们用ArrayList存储了了1GB大小的数据，这个时候已经没有空闲空间了，当我们再插入数据的时候，ArrayList会申请一个1.5GB大小的存储空间，并且把原来那1GB的数据拷贝到新申请的空间上。听起来是不是就很耗时？

除此之外，如果你的代码对内存的使用非常苛刻，那数组就更适合你。

因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，就有可能会导致频繁的GC（Garbage Collection，垃圾回收）。

所以，在我们实际的开发中，针对不同类型的项目，要根据具体情况，权衡究竟是选择数组还是链表。