数组是常用的数据结构。数组顺序是由下标决定的,因此访问数组的元素速度很快。但是,往数组添加或删除元素时,需要把数组中的其他元素向前或向后移动,速度比较慢。
在元素很多,经常要添加或删除元素,但不经常访问元素的场景下,用数组的性能比较低。这种场景下,可以用链表。
链表介绍
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表的特点和数组相反:访问元素慢,新增或删除元素快。
链表的常用使用场景包括:
- LRU 缓存淘汰算法。
- 解决哈希冲突的哈希表。
- 各类缓冲池 和 栈 的实现。
好吧,好像都和前端都没有关系。使用大型数据集时,链表的大部分性能提升都会很明显。我们通常不会在前端处理这种大小的数据集。
链表在前端的主要应用场景是: 面试,哈哈。面试中,考链表,可以了解面试者程序设计能力和实操能力。下面是一些链表的题目,来练练手吧:
- 单向链表,双向链表的实现。
- 反转链表。
- 使用循环链表解决约瑟夫环问题。