数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

线性表和非线性表：

  • 线性表：线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。比如数组、链表、队列、栈等
  • 非线性表：在非线性表中，数据之间并不是简单的前后关系。比如：二叉树、堆、图等

连续的内存空间和相同的数据类型保证了数组随机访问高效，但是弊端是增加修改删除比较慢，为了保证连续性，就需要做大量的数据搬移工作。

如何选择用数组还是容器：

  • Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类
  • 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
  • 当要表示多维数组时，用数组往往会更加直观。

链表

缓存淘汰策略LRU：

  • 先进先出策略 FIFO
  • 最少使用策略
  • 最近最少使用策略

数组和链表区别：

  • 数组需要连续内存空间，链表不需要，它通过“指针”将一组零散的内存块串联起来使用
  • 数组随机访问性能快，链表随机访问性能差；数组进行增删改时，需要进行大量的数据迁移，链表不需要，只需要修改指针指向节点即可，速度较快

链表的类型：

  • 单链表

头节点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表
尾节点指针不是指向下一个结点，而是指向一个空地址 NULL

  • 双向链表

单链表只有一个方向，但是双向链表有两个方向，每个结点不止有一个后继指针 next 指向后面的结点， 还有一个前驱指针 prev 指向前面的结点。

  • 循环链表

和单链表一样，不同的区别在于循环链表尾节点指向链表的头结点，而不是NULL