Java开发 - 双向链表不可怕

谁践踏了优雅 2023-09-30 18:17 7阅读 0赞

## 前言 ##

说起链表，那还是当初上学的时候学习的，印象里就觉得像锁链一样一环扣一环，后来工作后就几乎没实际接触过链表，每当遇到链表，总是不知道该怎么讲，因为对链表的本质一无所知。也是在学习了Java后，才明白了链表的运行机制，原来如此简单，这里将和大家一起来分享双向链表的一些知识。

## 什么是双向链表 ##

链表是一种数据结构，由若干个节点组成，每个结点又分为三部分：前驱节点，元素，后继节点。双向链表中的结点是以游离状态存在的，意思是非连续的，这让我们想到了数组，因为数组中的数据是连续存在的，在内存上也是如此。

![685aefe83ddc43d0a09abf5c3ceebfce.png][]

用一张图来表示双向链表的结构，第一个是头节点，最后一个是尾节点，头尾不能相连，否则就是另一种数据结构，后面再说。

## 双向链表在Java中的使用 ##

### LinkedList ###

在上面的图中，我们认为中间部分保存的是对象，但实际上保存的是对象的地址。

为了便于说明，后面我们将针对LinkedList来进行讲解。

#### LinkedList的演化 ####

从JDK1.8开始，LinkedList的数据结构为双向链表  
在JDK1.8之前，LinkedList的数据结构是双向循环链表(头尾相接)，如下图

![c0d264e14a814a64be2fdaa44bd8124f.png][]

#### LinkedList的查询方式 ####

双向循环链表的查找过程与双向链表相同，都遵从下面的原则:

对半查询：

*  小于一半，则从header开始顺序查找；
 *  大于一半，则从header开始逆序查找，双向链表头尾不相连，则从尾部开始逆序查找。

### 增加元素 ###

//在链表尾部添加元素，创建一个新节点，并让新节点和上一个节点建立双向链表的关系
    add(E)
    //在指定位置插入元素，先断开对应位置的链，然后重新构建此位置前后链的关系
    add(int index,E e)

### 删除元素 ###

//删除指定位置的元素，实际上是断开对应位置链,
    //并将移除后的位置前后的元素重新构建链的过程
    remove(int index)

### 修改元素 ###

//将新元素替换指定位置的元素
    set(int index,E e)

### 查询元素 ###

//查询方式:对半查找
    //若查找的位置小于链表长度的一半，则从头结点开始顺序查找。否则，从尾结点开始逆序查找。
    get(int index)

### ArrayList和LinkedList的区别 ###

*  ArrayList底层实现是数组，而LinkedList底层是双向链表；
 *  数据结构不同，则性能不同；

为什么不直接说谁性能好呢？这个不好说，我们慢慢往下看。

#### 查询比较 ####

ArrayList是数组实现的，它有下标，查询效率非常高，时间复杂度为o(1)。

LinkedList我们已经看过它的数据结构，说讲它查询的方式：对半查找。所以查询头尾元素效率很高，若是中间元素，那么效率将取决于LinkedList的大小和元素所处位置是否靠近头尾，所以效率偏低。

**时间复杂度**：o(1) o(n) 用来衡量数据结构/算法效率的一个标志，n值越小，查询效率越高。

#### 增删比较 ####

ArrayList在尾部增删元素，效率会很高，若是在非尾部增删，则该位置之后的所有元素都需要中心排列。所以，其效率不高。

LinkedList在头尾进行增删元素，效率会很高，若是在靠近中间部分进行增删，效率则偏低，这是因为增删需要先查询，查询的效率低了，增删效率也会跟着低。

#### 对比总结 ####

ArrayList查询性能高于LinkedList，但若是首尾查询，LinkedList的效率也很高。

对于增删，头尾部增删，用LinkedList，其他部位增删，ArrayList和LinkedList半斤八两。

总的来说，ArrayList偏向于查询，所以我们在实际开发中用ArrayList更多。

## 结尾 ##

结尾附上[LinkedList源码][LinkedList]，感兴趣的小伙伴自行下载查看，另外，关于链表，在后面的二叉树部分还会有部分涉及，欢迎持续关注。

[685aefe83ddc43d0a09abf5c3ceebfce.png]: https://img-blog.csdnimg.cn/685aefe83ddc43d0a09abf5c3ceebfce.png
[c0d264e14a814a64be2fdaa44bd8124f.png]: https://img-blog.csdnimg.cn/c0d264e14a814a64be2fdaa44bd8124f.png
[LinkedList]: https://download.csdn.net/download/CodingFire/87353748