数组

数组是物理存储单元连续，顺序的存储结构。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；链表存多重形式。

循环链表

  • 尾结点指针指向头结点的链表
  • 是单链表也可以是双链表

单链表

  • 每个结点包含两个部分：一个是存储数据元素的数据，另一个是存储下一个结点地址指针，只有后继一个结点。

双向链表

数组与链表性能比较

时间复杂度 插入删除 随机访问
数组 O(n) O(1)
链表 O(1) O(n)