02_数据结构与算法之链表

深碍√TFBOYSˉ_ 2022-09-10 13:26 202阅读 0赞

## 1、什么是链表 ##

链表（linked list）是一种在物理上**非连续**、非顺序的数据结构，由若干**节点**（node）所组成。

链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。（百度百科）

常见的链表包括：**单链表、双向链表、循环链表**

**1）单链表**  
单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next  
![在这里插入图片描述][95c1e5a8f47d4e24873d9b3723dfecd0.png]

Node{ 
            int data;
            Node next;
    }

**2）双向链表**  
双向链表的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。  
![在这里插入图片描述][64892187d73b4b14a7c982299bb631dc.png]

Node{ 
        int data; 
        Node next; 
        Node prev; 
    }

**3）循环链表**  
链表的尾节点指向头节点形成一个环，称为循环链表  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16]

## 2、存储原理 ##

数组在内存中的存储方式是顺序存储（连续存储），链表在内存中的存储方式则是**随机存储**（链式存储）。  
链表的每一个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
链表的第1个节点被称为头节点（3），没有任何节点的next指针指向它，或者说它的前置节点为空头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表链表的最后1个节点被称为尾节点（2），它指向的next为空

## 3、操作 ##

#### 1）查找节点 ####

在查找元素时，链表只能从头节点开始向后一个一个节点逐一查找。  
![在这里插入图片描述][ea791cacadd2449abbc55dbe243802e1.png]

#### 2）更新节点 ####

找到要更新的节点，然后把旧数据替换成新数据  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 2]

#### 3）插入节点 ####

*  **尾部插入**  
    把最后一个节点的next指针指向新插入的节点即可  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 3]
 *  **头部插入**  
    第1步，把新节点的next指针指向原先的头节点  
    第2步，把新节点变为链表的头节点  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 4]
 *  **中间插入**  
    第1步，新节点的next指针，指向插入位置的节点  
    第2步，插入位置前置节点的next指针，指向新节点  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
    只要内存空间允许，能够插入链表的元素是无限的，不需要像数组那样考虑扩容的问题

#### 4）删除节点 ####

*  **尾部删除**  
    把倒数第2个节点的next指针指向空即可  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 6]
 *  **头部删除**  
    把链表的头节点设为原先头节点的next指针即可  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 7]
 *  **中间删除**  
    把要删除节点的前置节点的next指针，指向要删除元素的下一个节点即可  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 8]

## 5、时间复杂度 ##

查找节点： O(n)  
插入节点：O(1)  
更新节点：O(1)  
删除节点：O(1)

## 6、优缺点 ##

*  优势  
    插入、删除、更新效率高  
    省空间
 *  劣势  
    查询效率较低，不能随机访问

## 7、应用 ##

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

## 8、数组与链表的对比 ##

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

*  数组的优势在于能够快速定位元素，对于读操作多、写操作少的场景来说，用数组更合适一些
 *  链表的优势在于能够灵活地进行插入和删除操作，如果需要在尾部频繁插入、删除元素，用链表更合适  
    一些
 *  数组和链表是线性数据存储的物理存储结构：即顺序存储和链式存储。

[95c1e5a8f47d4e24873d9b3723dfecd0.png]: /images/20220829/79d836a956c344efb476f3286e67fdd3.png
[64892187d73b4b14a7c982299bb631dc.png]: /images/20220829/829175b03c2142589837f390f1668313.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/899f881db8bb4e83b377b1a92aa17843.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/8c9d5d855186467aa7a8380583297273.png
[ea791cacadd2449abbc55dbe243802e1.png]: /images/20220829/55ea464e5886485084711ba509cbc312.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/04a31826737445f180d3eacfcc028324.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/07c22776edc7458fb61e7d4e009ee616.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/23ec52c4bf314f21ae9c76ef27cb955c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220829/da0cf7d700b34e048ddfa052ceea5e6b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220829/4dcb272e800149dd943e60acf6ef9295.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220829/ccd36db895ff473ca5bbd64bb765d1e1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220829/4b06c12b030648269a6c7d74f68c177c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220829/0bf14517b34349078686ee1ae1bb8d89.png