链表：
- 通过指针串联在一起的线性结构；
- 每个节点包含两部分：数据域、指针域（存放下一个节点的指针）
- 入口节点：称为 头节点 head
- 最后一个节点的指针指向 NULL（空指针）
链表的类型
1. 单链表（Singly Linked List）
- 结构：每个节点包含数据域和指向下一个节点的指针（
next）。 - 特点：
- 单向遍历，只能从头节点开始逐个访问。
- 插入/删除节点的时间复杂度为 O(1)（已知前驱节点时）。
- 查找时间复杂度为 O(n)。
- 缺点：- 无法逆向遍历，删除节点需要从头查找前驱节点。
- 应用场景：简单队列、不需要反向操作的场景。
2. 双向链表（Doubly Linked List）
- 结构：每个节点包含数据域、前驱指针（
prev）和后继指针（next）。 - 特点：
- 支持双向遍历（正向和逆向）。
- 插入/删除节点的时间复杂度为 O(1)（已知目标节点时）。
- 缺点：- 每个节点多占用一个指针的空间。
- 应用场景：需要双向操作的场景（如浏览器历史记录、撤销/重做功能）。
3. 循环链表（Circular Linked List）
- 结构：链表首尾相连，形成闭环。
- 类型：
- 单循环链表：尾节点指向头节点，只能单向循环遍历。
- 双循环链表：头尾节点互相连接，支持双向循环遍历。
- 特点：
- 从任意节点出发均可遍历整个链表。
- 适合周期性操作。
- 应用场景：轮询任务调度、约瑟夫环问题。
链表的存储
- 数组：连续分布
- 链表：不连续的，分布在内存的不同地址空间上，通过指针串联在一起
链表相关代码
定义
// 单链表
struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};
输出链表
void printLinkedList(ListNode* head){ListNode* cur = head;while(cur != nullptr) {cout << cur->val << " ";cur = cur->next;}cout << endl;
}
通过输入 - 创建单链表
int main() {int n, m;ListNode* dummyHead = new ListNode(0);while(cin >> n){if(n == 0){cout << "list is empty" << endl;continue;}ListNode* cur = dummyHead;while(n--){cin >> m;ListNode* newNode = new ListNode(m);cur->next = newNode;cur = cur->next;}}ListNode* head = dummyHead->next;printLinkedList(head);
}
直接创建单链表
ListNode* head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(3);head->next->next->next = new ListNode(4);head->next->next->next->next = new ListNode(5);head->next->next->next->next->next = new ListNode(6);
