数据结构小记【Python/C++版】——链表篇

一，基础概念

链表是一种线性表结构，节点是链表中的基本单元。

链表是节点的集合，节点可以分布在内存中的任何位置，每个节点都存储着链表中下一个节点的地址。

如图，看似随意摆放的各个节点，其内部其实有链表维持的相对位置信息。

我们用“指针”来表示链表中的方向，为了维持节点之间的先后顺序，链表给每个节点都附加了一个指针。单链表中的每个节点都包含指向后一个节点的后向指针，双链表中的每个节点不仅包含指向后一个节点的后向指针，也包含指向前一个节点的前向指针。链表在内存上不一定是连续分布的，我们只能沿着指针的方向迭代遍历链表上的节点，无法直接根据下标来访问链表指定位置上的元素。

链表和数组相比，主要优势： 

1.链表在编译期不需要知道具体大小。

2.数组中的元素在内存中是连续分布的，且以相同距离间隔开。因此，往数组中插入新的元素就需要移动数组中的其他数据，链表不需要这么麻烦。

数组的内存分布：