3.基础数据结构-链表

2023-12-13 06:55:37

3 基础数据结构-链表

3.1 定义

????????链表（Linked List）是一种线性数据结构，由一系列节点（Node）组成。每个节点包含两部分：元素值（Element Value）和指向下一个节点的指针（Pointer）。链表可以分为多种类型，如单向链表、双向链表、循环链表等。元素在存储上并不连续。

?3.1.1?分类

（1）单向链表：每个元素只知道下一个元素。

（2）双向链表：每个元素知道下一个元素和上一个元素。

（3）循环链表：通常的链表为节点tail指向null，但是循环链表的tail指向head。

?3.1.2 哨兵节点

链表内还有一种特殊的节点，成为哨兵（Sentinel）节点，也叫做哑元（Dummy）节点，他并不存储数据，用来减缓别介判断。

3.2 性能

随机访问：

? ? ? ? 根据index查找，时间复杂度O(n)。

插入或者删除：

? ? ? ? 起始位置：O(1)。

? ? ? ? 结束位置：如果已知tail为节点是O(1)，否则为O(n)。

? ? ? ? 中间位置：根据index查找时间+O(1)。

?

?

文章来源:https://blog.csdn.net/weixin_67852890/article/details/134948880
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。