链表

认识链表

在计算机科学中，链表（Linked list）是一种常见的基础数据结构
- 是一种线性结构，但是并不会按线性的顺序存储数据，而是在每一个节点里存放下一个节点的指针
- 常用于组织 检索较少，而删除、添加、遍历较多 的数据
链表相对于数组的优缺点
- 优势
  - 内存空间不是必须连续的，可以充分利用计算机的内存，实现灵活的内存动态管理
  - 链表不必在创建时就确定大小，并且大小可以无限的延伸下去
  - 链表在插入和删除数据时，时间复杂度可以达到 O(1)
- 劣势
  - 失去了数组随机读取的优点，访问元素时必须从头开始查找，时间复杂度 O(n)
  - 由于增加了结点的指针域，空间开销比较大
链表在实现上，又可以分为单向链接、双向链表、循环链表等