单向链表
介绍
单向链表是一种线性数据结构,它由一系列节点组成,每个节点包含两部分:数据域和指针域。数据域用于存储实际数据,指针域存储指向下一个节点的引用。链表中的最后一个节点指向空(null),表示链表的结束。

与数组不同,链表中的元素在内存中不是连续存储的,而是通过指针连接在一起。这种特性让链表在某些操作上比数组更灵活,特别是在频繁进行插入和删除操作的场景下。
核心特性
- 动态大小:链表可以动态增长和缩小,无需预先定义大小
- 非连续存储:节点在内存中分散存储,通过指针相连
- 单向性:每个节点只知道下一个节点在哪里,不知道上一个节点
- 顺序访问:必须从头节点开始,沿着指针逐个访问节点
- 无索引访问:不能像数组那样通过索引直接访问元素
基本操作
1. 访问元素
- 时间复杂度:O(n)
- 说明:必须从头节点开始,沿链表遍历直到找到目标节点
...