对于大量的输入数据,链表的线性访问时间太慢,不宜使用。
链表
Linked List
基本概念
- A linked list consists of a sequence of links.
- Each link (also called a node) stores
- data(储存的对象)
- link to the next node(对下一个节点的引用)
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F156d5555-7277-47b3-9ac9-16fe0d9cf7bb%2FUntitled.png?table=block&id=6ec9be11-8706-4973-8b5a-5f2a25e85161&t=6ec9be11-8706-4973-8b5a-5f2a25e85161&width=384&cache=v2)
- The main problem with arrays is that in order to move an item from one slot to another it has to be copied, pasted and deleted, which is time-consuming and wastes space.
- Linked lists avoid all of these problems because they can adapt their ordering by changing the items they point to.
- 向链表插入或删除一项的操作不需要移动很多的项,而只涉及常数个节点链的改变。
从链表中删除
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Ff91c1256-1388-4a92-aeac-c2f89a40a46c%2FUntitled.png?table=block&id=90328199-1be0-4cf6-a675-e4218af2030d&t=90328199-1be0-4cf6-a675-e4218af2030d&width=1099&cache=v2)
向链表插入
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F62dd388e-4ba3-49cf-a0aa-dded60c5c59b%2FUntitled.png?table=block&id=fc0daad8-05de-400b-925e-a90b7a08483d&t=fc0daad8-05de-400b-925e-a90b7a08483d&width=1011&cache=v2)
代码实现
双链表
Doubly linked List
基本概念
- 在经典的链表中,每个节点均存储到其下一节点的链,而拥有指向最后节点的链并不提供最后节点的前驱节点的任何信息。
- 删除最后一项比较复杂,因为必须找出指向最后节点的项,把它的 next 链改成 null,然后再更新持有最后节点的链。
- 双向链表的一个节点有两个方向,分别储存当前节点的前驱节点和后续节点。节点的删除只需要指定前驱节点,或者后续节点就可以进行删除操作;但是缺点也很明显,每次添加节点时都需要 2 个指向,额外增加了内存空间消耗。
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fdc941f36-aa0d-4a0a-94f2-942e4e9e3f1a%2FUntitled.png?table=block&id=f6273cfe-6edf-4abe-89f2-105bcf307ef7&t=f6273cfe-6edf-4abe-89f2-105bcf307ef7&width=384&cache=v2)
代码实现
算法应用
反转链表
: 是链表的长度,需要遍历链表一次
查找中间节点
采用快慢指针的方式
- 快指针一次走两步,慢指针一次走一步。
- 当快指针走完时,慢指针刚好到达中间节点。
合并两个有序链表
Leetcode 21
& 2022 CS211 Final Exam![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fa6a3e431-c6a3-4614-813b-99f8507c2273%2FUntitled.png?table=block&id=f6e8c933-7b1d-4585-8d0a-536ebf3c29b0&t=f6e8c933-7b1d-4585-8d0a-536ebf3c29b0&width=288&cache=v2)