链表
什么是数据结构
数据存储于计算机的内存中，决定数据存储的顺序和位置的便是数据结构。数据在内存中是线性排列的。可以使用指针等工具，构造复杂的“树形”型等复杂结构。
链表特点
链表是数据结构之一，其中的数据呈现线性排列。链表中的数据进行添加和删除非常方便，访问耗时间。
指针：每个数据都有一个指针，用于指向下一个数据的内存地址。
image.png
在链表中，数据一般是分散存储于内存中，无需连续存储。
- 访问：因为无序和分散存储，所以访问数据的话，只能从头开始，称之为顺序访问
- 添加：改变添加位置前后的指针指向即可
- 删除：也是改变指针指向，数据本身还是存在；但是没有指针指向这个数据，所以无法访问到该数据
运行时间
将链表中的数据量记为n，
- 访问：如果数据在末尾，需要从头开始线性查找，需要的时间就是O(n)
- 添加和删除：只是单纯的改变指针指向，和n无关，所以时间是O(1)
其他链表
循环链表
在链表尾部使用指针，使其指向指针链表头部的数据，形成一个闭环，称之为循环链表。
- 没有头和尾的概念
- 保存固定数量的最新数据常用循环链表
image.png
双向链表
指针设为两个，分别指向指针前后的数据，称之为双向链表。
- 可以前后双向访问数据
- 指针数量增加，会带来存储空间的增加
- 添加和删除数据时候需要改变更多的指针指向
image.png
网友评论