Java-数据结构（四）------链表

心已赠人 2023-02-12 11:23 40阅读 0赞

单链表  
双端链表  
有序链表  
双向链表

## 1、什么是链表 ##

链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（“links”）

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

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

## 2、单向链表 ##

![在这里插入图片描述][202005262141398.png]  
单向链表

> 每个结点中只包含一个指针域next，每个结点只有一个指向直接后继结点的指针，且最后一个节点存储地址的部分指向空值

**单向链表由两部分组成**

**data**:保存或者显示关于节点的信息  
**next**:存储下一个节点的地址

单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70]

**插入节点**

只能在链表头head插入，需要将当前插入的节点设置为头节点，next指向原头节点即可。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 1]  
**删除节点**

将被删除节点的上一个节点的next指向被删除节点的下一个节点。

（删除data:B)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 2]

## 三、双端链表 ##

对于单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点

双端链表区别与单向链表链表的不同之处在于：双端链表支持头部和尾部都能插入数据。

双端链表：从first头节点还指向了尾节点，从而可以使我们在尾端也能插入数据，就像从表头插入数据一样。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 3]  
**插入节点**

支持头部和尾部插入，与单链表插入节点一致

*  1、在表头插入
    
    与单链表一致
 *  2、在尾节点插入

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 4]

**删除节点**

双端链表并不能实现删除最后一个节点的功能，因为没有指向倒数第二个的引用

## 4、有序链表 ##

有序链表中，链结点按照关键值的升序（降序）排列

有序链表中插入需要O(N)的时间，因为必须找到正确的插入点，最小值连接点的删除需要O(1)的时间

一般在大多数需要使用有序数组的场合也可以使用有序链表。  
有序链表优于有序数组的地方是插入的速度（因为元素不需要移动），  
另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。

有序链表插入和删除某一项最多需要O(N)次比较（平均N/2）,因为必须沿着链表一步一步找到正确的位置，然而，可以在O(1)的时间内找到或删除最小的值，因为它是表头，如果一个应用频繁的存取最小项，且不需要快速的插入，那么有序链表是最有效的一个方案选择。

## 5、双向链表 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 5]

双向链表比上述的链表要灵活，因为他在每一个节点处增加了一个prev的引用，使链表在反向的方向也连接起来，这样反向也能遍历，插入，删除。

[202005262141398.png]: https://img-blog.csdnimg.cn/202005262141398.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020052621502263.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200526215230108.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200526215411513.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020052622052769.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200526220903264.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020052622322052.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTE0ODM3,size_16,color_FFFFFF,t_70