数组是常用的数据结构。数组顺序是由下标决定的,因此访问数组的元素速度很快。但是,往数组添加或删除元素时,需要把数组中的其他元素向前或向后移动,速度比较慢。

在元素很多,经常要添加或删除元素,但不经常访问元素的场景下,用数组的性能比较低。这种场景下,可以用链表。

链表介绍

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

链表的特点和数组相反:访问元素慢,新增或删除元素快。

链表的常用使用场景包括:

  • LRU 缓存淘汰算法。
  • 解决哈希冲突的哈希表。
  • 各类缓冲池 和 栈 的实现。

好吧,好像都和前端都没有关系。使用大型数据集时,链表的大部分性能提升都会很明显。我们通常不会在前端处理这种大小的数据集。

链表在前端的主要应用场景是: 面试,哈哈。面试中,考链表,可以了解面试者程序设计能力和实操能力。下面是一些链表的题目,来练练手吧:

  • 单向链表,双向链表的实现。
  • 反转链表。
  • 使用循环链表解决约瑟夫环问题。

参考文档