复习：链表面试基础笔记

叁歲伎倆 2023-03-02 05:10 18阅读 0赞

## 链表 ##

1.  查找麻烦
2.  插入和删除简单
3.  可以定点删除和插入
4.  物理存储空间可以是非连续的，内存利用率高，不会浪费内存（可以使用内存中细小的不连续空间（大于node节点的大小），并且在需要空间的时候才创建空间）
5.  无限定长度，容易扩展，灵活度高。
6.  节点一般是类 ，一些语言中是结构体
7.  删除是用指针指向其他节点
8.  他是线程不安全的
9.  查询效率不好 On
10. 头节点问题

> 链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。

这里有个地方要注意，就是对头指针概念的理解，这个很重要。“**链表中第一个结点的存储位置叫做头指针**”，如果链表有头结点，那么头指针就是指向头结点数据域的指针。头指针就是链表的名字。\*\*头指针仅仅是个指针而已。\*\*画一个图吧。  
![在这里插入图片描述][20200727215613652.png]  
**头结点是为了操作的统一与方便而设立的**，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。  
有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。  
**首元结点**也就是第一个元素的结点，**它是头结点后边的第一个结点**。  
**头结点不是链表所必需的。**  
在线性表的链式存储结构中，头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针。  
**头指针具有标识作用，故常用头指针冠以链表的名字。**  
无论链表是否为空，头指针均不为空。**头指针是链表的必要元素。**

单链表也可以没有头结点。如果没有头结点的话，那么单链表就会变成这样：  
![在这里插入图片描述][20200727220503933.png]  
**为了使空链表与非空链表处理一致，我们通常设一个头结点。**

1.  单链表  
    在单链表中，我们有一个数据域，还有一个指针域，负责向后连接，指向其直接后继。
2.  双向链表  
    在双向链表中，我们需要有两个指针域，一个负责向后连接，一个负责向前连接。即分别指向其直接前驱和直接后继。  
    **单链表和双链表的区别？**

> 单链表只有一个指向下一结点的指针，也就是只能next  
> 双链表除了有一个指向下一结点的指针外，还有一个指向前一结点的指针，可以通过prev()快速找到前一结点，顾名思义，单链表只能单向读取，而双链表可以双向读取

**1. 双向链表的优点：**

> 1、删除单链表中的某个结点时，一定要得到待删除结点的前驱，得到该前驱有两种方法，第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。第二种方法是在定位到待删除结点之后，重新从单链表表头开始来定位前驱。尽管通常会采用方法一。但其实这两种方法的效率是一样的，指针的总的移动操作都会有2\*i次。而如果用双向链表，则不需要定位前驱结点。因此指针总的移动操作为i次。  
> 2、查找时也一样，我们可以借用二分法的思路，从head（首节点）向后查找操作和last（尾节点）向前查找操作同步进行，这样双链表的效率可以提高一倍。

**为什么市场上单链表的使用 > 双链表呢？**

> 从存储结构来看，每个双链表的节点要比单链表的节点多一个指针，而长度为n就需要 n\*length（这个指针的length在32位系统中是4字节，在64位系统中是8个字节） 的空间，这在一些追求时间效率不高的应用下并不适应，因为它占用空间大于单链表所占用的空间；这时设计者就会采用以时间换空间的做法，这是一种工程总体上的衡量。

[20200727215613652.png]: /images/20230208/a9826a1e33c649819c83b89fa2f5dfe2.png
[20200727220503933.png]: /images/20230208/2336ced4785e436ba90f5aac3a359b85.png