链表 Linked List

1. 什么是链表

   线性表：也称线性存储结构，线性表中的数据元素之间的关系是一对一的关系，除了第一个和最后要给数据元素，其他的数据元素都是首尾相连的。

   链表：线性表中使用链式存储的就是链表。

2. 线性表存储结构

   • 顺序存储结构：将数据依次存储在连续的整块的物理空间中，称为顺序存储结构，简称顺序表。
     • 随机取读，访问一个元素的时间复杂度为O(1)
   • 链式存储结构：数据分散存储在物理空间中，每一个元素都有一个指针域，指针域存储着下个元素的指针，这种存储结构称为链式存储结构，也称链表。
     • 优点：定点插入和定点删除时间复杂度为O(1)，不浪费内存，添加元素才申请内存，删除元素释放内存。
     • 缺点：访问的时间复杂度最坏为O(n)。

3. 链表分类

   根据指针域的不同分为：

   • 单向链表
   • 双向链表
   • 循环链表