Python算法札记3-链表

链表

什么是数据结构

数据存储于计算机的内存中，决定数据存储的顺序和位置的便是数据结构。数据在内存中是线性排列的。可以使用指针等工具，构造复杂的“树形”型等复杂结构。

链表特点

链表是数据结构之一，其中的数据呈现线性排列。链表中的数据进行添加和删除非常方便，访问耗时间。

指针：每个数据都有一个指针，用于指向下一个数据的内存地址。

image.png

在链表中，数据一般是分散存储于内存中，无需连续存储。

• 访问：因为无序和分散存储，所以访问数据的话，只能从头开始，称之为顺序访问
• 添加：改变添加位置前后的指针指向即可
• 删除：也是改变指针指向，数据本身还是存在；但是没有指针指向这个数据，所以无法访问到该数据

运行时间

将链表中的数据量记为n，

• 访问：如果数据在末尾，需要从头开始线性查找，需要的时间就是O(n)
• 添加和删除：只是单纯的改变指针指向，和n无关，所以时间是O(1)

其他链表

循环链表

在链表尾部使用指针，使其指向指针链表头部的数据，形成一个闭环，称之为循环链表。

• 没有头和尾的概念
• 保存固定数量的最新数据常用循环链表

image.png

双向链表

指针设为两个，分别指向指针前后的数据，称之为双向链表。

• 可以前后双向访问数据
• 指针数量增加，会带来存储空间的增加
• 添加和删除数据时候需要改变更多的指针指向

image.png