重新认识链表(上)

梦里梦外; 2022-01-20 11:51 185阅读 0赞

## 定义 ##

**[链表（Linked list）][Linked list]**是一种线性表数据结构。通常说链表的时候，会把它与数组放在一起进行比较，这样会更好的理解链表。链表克服了数组需要预先知道数据大小的缺点，并且它可以充分利用好内存空间，通过“**指针**”将**一组零散的内存块**串联起来使用，实现**灵活的内存动态管理**。但是链表失去了数组随机访问优点，同时链表由于增加了结点的指针域，空间开销比较大。

## 优缺点（以数组为参照，以单链表为例） ##

### 优点： ###

因为链表的存储空间不是连续的，所以不像数组呢样，每做一次插入删除操作的时候，为了保证内存数据的连续性，都需要做大量的数据迁移，也就意味着它的插入删除操作是十分快速的。通常只需要考虑相邻节点的指针的变化就可以了，所以时间复杂度很低，为O（1）。

### 缺点： ###

当然有利就有弊。链表的随机访问效率就不如数组了。同样原因，非连续存储，所以不能通过寻址公式来直接计算内存地址了。只能根据指针去一个节点一个节点的遍历，时间复杂度要搞一些，为O（n）。

## 常见的链表结构有： ##

单链表，双向链表和循环链表。

### 单链表 ###

单链表是最简单的一种链表结构了，它包含两个域，一个**信息域**和一个**指针域**。并且是单向，结点只有一个后继指针 next 指向后面的结点。

### 双向链表 ###

双向链表，顾名思义，它支持两个方向，一个前驱指针prev指向前面的节点，一个后继指针next指向后面的节点。同时它也比单链表更加占内存，但是它更灵活，可以双向遍历，所以对插入、删除操作更加简单、高效。

JAVA的LinkedHashMap容器底层就是这个双向链表。