链表 | 知识

刷题跟随carl代码随想录，牛客刷题总结

理论知识

链表是一种通过指针串联在一起的线性结构【链表都是线性结构】，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针）【增加了存储空间】，最后一个节点的指针域指向null（空指针的意思）。

链接的入口节点称为链表的头结点也就是head。

单链表

单链表中的指针域只能指向节点的下一个节点。

双链表

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

循环链表

链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

链表的存储方式

链表在内存中可不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表是通过指针域的指针链接在内存中各个节点。

这个链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。

链表的代码定义

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

链表的操作

删除节点、添加节点、获取数值 | 链表 | leecode刷题笔记| leecode刷题笔记

删除节点

删除D节点，如图所示：

只要将C节点的next指针 指向E节点就可以了。

D节点不是依然存留在内存里么？只不过是没有在这个链表里而已。确实是这样，所以在C 里最好是再手动释放这个D节点，释放这块内存。
.
其他语言例如Java、Python，就有自己的内存回收机制，就不用自己手动释放了。

添加节点

可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。
📝但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

性能分析

链表的一些题目

1. 时间复杂度
   • 以链表方式存储时，访问第i位置元素的时间复杂性为O(n)【从head开始向后找】【不是O(i)！！所花时间≠时间复杂度】
   • 在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是O（n）。
   • 将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度釆用大O形式表示应该是（O(m)）。

     先遍历m链表，再用尾部指针指向n链表的头结点。因为m链表无尾指针，如果有的话是O(1)。

   •  
2. 插入、删除元素的操作不需要移动元素结点。
   • 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是静态链表。
   • 当静态链表采用数组实现时，插入与删除操作仍需移动元素❌【静态链表采用数组实现链表的存储，用空间换取时间，删除与插入需要改的是游标】
   •  
3. 所需要的存储空间与线性表的长度成正比。
4. 不必事先估计存储空间大小。
5. 对于链式存储的线性表，查找结点和删除结点的时间复杂度为O(n)，O(n)【链式删除和查找都要从开头遍历】
6. 从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较（(n 1)/2）个结点，最少1次，最多n次。
7. 某一系统功能，需要一次性加载N（N在1000左右）个随机数，后续只对该集合进行遍历。最宜采用链表结构存放。【链表适合遍历，不适合随机访问】【hash表用空间换时间，适合查询】
8. 可用来构造链表的结构类型是struct bb{ int a；bb * b；}；
9. 线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的。
10.  

单链表的一些题目

1. 一个单向链表队列中有一个指针p，现要将指针r插入到p之后，该进行的操作是r->next=p->next;p->next=r。

2. 带头结点的单链表，在表的第一个元素之前插入一个新元素与链表长度无关。

3. • 带头结点的单链表，判定链表为空表的条件是Head->next==NULL;。
   • 不带头结点的单链表，head为空的判定条件是head==NULL
   •  
4. • 在一个长度为 n （ n>1 ）的单链表上，设有头和尾两个指针，执行（删除单链表中的最后一个元素）操作与链表的长度有关。【由于不是双向链表，所以要从头指针开始，一直遍历直到倒数第二个元素，将倒数第二个元素（结点）指向NULL，释放原末端元素（结点）空间后，将尾指针等于新的末端元素（结点）】
   • 当删除单链表中的第一个元素时只需要将头指针指向第二个元素，然后释放第一个元素储存空间申请的内存。与链表长度无关。
   • 在单链表第一个元素前插入一个新元素时，只需要把新的元素（结点）指向原来的第一个元素（结点），然后使头指针指向新的元素（结点）。与链表长度无关。
   • 在单链表最后一个元素后插入一个新元素时，只需先将新结点指向NULL，然后将尾指针指向的原末端结点指向新的元素（结点），最后将尾指针指向新的元素（结点）。与链表长度无关。

5. 将两个长度为 len1 和 len2 的升序链表，合并为一个长度为 len1 len2 的降序列表，采用 归并算法，在最坏情况下，比较操作的次数与（len1 len2）最接近。

   归并排序采用分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
   len2的最大序列和len1的最大序列相互比较，较大的一个放到新链表中（假设len2的元素）
   然后对比len2序列剩余元素的最大值继续和len1的最大值做比较，将较大的放入新链表中
   依次类推，最坏的情况就是len2中的每个元素都要和len1做比较，而且len1相互之间再做比较，即len1 len2

6. 某单链表有5个元素，设单链表的节点结构为(data,next)，5个元素的data依次为（1、2、3、4、5），已知指针q指向节点3，指针p指向节点4，那么下面操作能将链表变为data依次为（1、2、3、5）的是temp = p->next; p->next=temp->next; p->data=temp->data; delete temp;temp=NULL;。（其中temp为节点类型指针，默认指向NULL）

7. 单链表的存储密度小于1【存储密度=单链表数据项所占空间/结点所占空间。结点所占空间由数据项所占空间和存放后继结点地址的链域，所以，存储密度小于1】

8. 单链表结点的数据元素只能是哪一种？（任何数据类型）。

9. 设指针变量 p 指向单链表中结点 A ，若删除单链表中结点 A ，则需要修改指针的操作序列为（q=p->next；p->data=q->data；p->next=q->next；free(q)；）。

10. • 如果两个单向链表相交，那他们的尾结点一定相同
    • 有环的单向链表跟无环的单向链表不可能相交
    • 两个单向链表之间相交可以存在环
11. • 单向链表中指向头结点的指针First，可用于单向链表的判空依据
    • 单向链表中指向头结点的指针First，可用于定位所有其他结点的位置
    • 单向链表允许在非表头进行插入或删除操作

12. 设指针变量p指向单链表的某中间结点，则删除该结点的后序结点需要的操作为（不能有内存问题）（t=p->next;p->next=t->next;free(t)）

13. 在一个长度为n的单链表的第i（0<=i<n）个元素后面插入一个元素时，需要向后移动0个元素。

14. 如果使用比较高效的算法判断单链表有没有环的算法中，至少需要2个指针。快慢指针是判断一个单向链表有没有环的一种方法。

15. 有一个单向链表，头指针和尾指针分别为p，q，以下哪项操作的复杂度不受队列长度的影响？删除头部元素、头部元素之前插入一个元素、尾部元素之后插入一个元素。【除尾部元素❌】

16.  

单循环链表

1. 单循环链表的主要优点是从表中任一结点出发都能扫描到整个链表

2. 需要头结点

   • 链表由头指针唯一确定，单链表可以用头指针的名字来命名。

3. 头节点和尾节点被连接在一起

   • 在一个以 h 为头指针的单循环链中，p 指针指向链尾结点的条件是(p->next==h)。
   • 设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（head->next==head）。
   • 带头结点head的单向循环链表为空的判断条件是（head->next==head）

4. 判断链表结束的条件是pTail == NULL❌【最后一个节点的指针总是指向链表头】

5. 在进行插入、删除操作时，能更好地保证链表不断开❌【不断开怎么插入或删除呢】

6. 已知某个结点的位置后，能够容易找到它的直接前趋❌【并不容易，需要遍历】

7. • 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用（仅有尾指针的单循环链表）存储方式最节省运算时间。【因为是循环单链表，如果只要知道尾指针p，则通过计算一次p->next就能获得头指针；插入和删除算法复杂度O(1) O(1)】
   • 在表头和表尾都可能有元素被插入的情况下，在单循环链表中设置尾指针比设置头指针好。
   •  

8. 双向链表和尾指针的单循环链表 在最后一个元素插入一个元素时间复杂度都是O（1） 添加完后都需要改变尾指针的指向。
   但是在删除第一个元素的时候，双向链表除了删除第一个元素还需要改变头指针的指向，而尾指针单循环链表不用改尾指针的指向。

9. 判断下列说法是否正确： 假设队列以不带头结点的单循环链表Q表示，只设一个指针Q->rear指向队尾元素结点(注意不设头指针)，且队列中元素个数大于1, 则出队时的操作是Q->rear->next = Q->rear->next->next

10.  

有序双向链表的题目

1. 在有序双向链表中定位删除一个元素的平均时间复杂度为O(N)【链表只能顺序查找。定位一个元素的时间为O(N)，删除一个元素的时间为O(1)】【链表不支持随机访问，所以管你双向还是双向循环 永远为O(n)】
2. 设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（s->left=p；s->right=p->right；p->right->left=s； p->right=s；）。
   
3.  

双向循环链表

1. 在循环双链表的 p 所指的结点之前插入 s 所指结点的操作是s->next = p；s->prior = p->prior；p->prior->next = s；p->prior = s。
2. 已知不带头结点的双向循环链表中的结点结构为(data,last,next) ,在指针p所指结点之后插入由指针s指向的新结点，相应操作为(s->last=p; s-> next=p-＞next; p-> next-> last=s; p-＞next=s)。
3. 对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为s->left=p;s->right=p->right;p->right->left=s;p->right=s;
4. • 双向链表的插入操作的方法：先确定插入结点的前驱与后继，再改变前驱结点与后继结点的指针。
   • 非空的双向循环链表中任何结点的前驱指针均不为空。
   • 头没有前驱，尾没有后继。
   • 存在这样的线性表：表中各结点都没有直接前趋和直接后继。【空表等】
   •  
5. 带头指针 L 的双向循环链表中，指针 p 指向双向循环链表的尾结点的条件是：（p->next == L&&L->prior==p）
6. 在双向链表存储结构中, 删除p所指的结点时需修改指针p->next->prior=p->prior;p->prior->next=p->next;
7. 从两个方向搜索双链表，比从一个方向搜索双链表的方差要小。

   如果链表数据是无序的，则单向搜索与双向搜索平均速度相同
   如果链表是有序的，而要搜索的数据距离最小值（最大值）较近，这种情况下双向搜索平均速度更快。
   因此双向搜索更稳定，方差更小

8. 除第一个元素和最后一个元素外,其余每个元素都有一个且仅有一个直接的前驱和直接后继

这篇好文章是转载于：学新通技术网