链表

尽管数组在元素的访问上很方便,但是在数组的起点和中间插入或移除元素的成本却很高,因为数组是一块连续的内存空间存储的,插入一个节点要改变插入点及后面所有元素的位置。当数组元素足够多的时候,插入一个元素的成本就会显现出来。

相对于传统的数组,链表的一个好处在于,添加或移除元素的时候不需要移动其他元素。链表同样是储存有序的元素的集合,但链表中元素在内存的位置并非连续放置的,而是有一个指针指向相邻的下一个元素。所以链表虽然插入移除节点很快,但是查询节点却很慢,因为要从头到尾遍历查询。而数组则是查询节点很快,但插入移除节点较慢。

分类

  1. 单链表

  2. 双链表

  3. 循环单链表