一.线性表1.线性结构特点1.存在唯一的“第一个”元素2.存在唯一的“最后一个”元素3.除第一个外每个元素只有一个前驱4.除最后一个外每个元素只有一个后驱图是一种非线性数据结构其他的栈、队列和数组都是线性结构。顺序表时间复杂度插入一个元素的时间复杂度On删除一个元素的时间复杂度O(n)二.线性链表特点:一个节点包括两个域存储数据元素信息的域称为数据域存储直接后继存储位置的域称为指针域指针域指向下一个节点的位置。应用场景1 .动态数据结构动态调整大小的数据结构 方便的插入和删除元素。2.频繁的插入和删除操作例如任务调度、 操作系统中的进程管理等场景。3.实现其他数据结构如栈、队列、哈希表等。4.处理不确定数量的数据。5.实现图的邻接表。6.内存管理空闲内存块的链表管理可以有效地跟踪和分配内存。三.双向链表应用场景浏览器的历史记录在 Web 浏览器中双向链表被用于管理浏览器的前进和后退历史记录前进与后退功能双向链表允许用户在浏览器中轻松实现前进next和后退previous操作。当用 户访问一个新页面时当前页面会被添加到链表中用户可以在链表中进行遍历快速返回到之前的页 面或者前进到未来的页面。双向导航菜单在用户界面UI设计中双向链表可以用来构建双向导航菜单前进与后退功能用户可以在多个菜单层级之间进行前后跳转双向链表使得这种操作变得更加高效尤 其在用户需要频繁切换菜单时。音乐播放器中的播放列表在音乐播放器或视频播放器中双向链表可以用来管理播放列表播放列表的管理双向链表允许用户在播放列表中前后跳转用户可以选择跳到播放列表中的任意歌曲 并且支持播放列表的循环播放和顺序播放。双向链表构建一个结点中有两个指针域一个指向直接后继另一个指向直接前驱。四.总结链表内存不连续分散内存通过指针保存下一个节点的地址。中间插入删除性能高。数组内存连续大小固定支持随机访问数组下标访问性能最高中间插入删除性能偏低。动态数组堆区创建的数组插入/删除链表O(1)只需改指针数组O(n)需移动元素。随机访问链表O(n)得从头遍历数组O(1)直接下标。内存链表不连续无碎片问题但每个节点多耗内存存指针。Dummy 节点也叫虚拟头节点、哨兵节点是一个不存储实际数据的辅助节点作为链表的头节点简化链表操作。Dummy 节点的作用1.简化头节点操作:不用特判头节点2.统一插入删除逻辑:所有节点处理方式相同3.避免空指针异常:链表为空时也有节点4.返回dummy-nextreturn dummy-next; // 返回真实头节点1.在数组中访问元素的时间复杂度为 O(1)。如果数组有足够空间插入元素到末尾也是 O(1)。链表在头部插入元素也是 O(1)。而在链表中查找元素需要遍历因此是 O(n)。2.链表支持动态内存分配可以在运行时根据需要分配内存且插入和删除操作无需移动元素效率较高。链表不支持随机访问访问元素需要顺序遍历。3.链表的每个节点除了存储数据外还需要存储指针因此相较于数组链表的空间开销更大空间利用率较低。