链表不需要一块连续的内存空间，其通过"指针"将一组零散的内存连接起来使用。其优点在于本身没有大小限制，天然支持扩容，插入删除操作高效(时间复杂度为O(1))，但缺点是随机访问低效(时间复杂度为O(N))。并且由于需要额外的空间存储指针。

链表的实现方式有很多种，常见的主要有三个，单向链表、双向链表、循环链表。

单向链表

单链表中每个节点除了包含数据之外还包含一个指针，叫后继指针，因此需要额外的空间来存储后继节点的地址。

有两个特殊的节点,头结点和尾节点，其中头节点用来记录链表的基地址，有了它就可以遍历整个链表，尾节点的后继指针不是指向下一个节点，而是指向一个空地址NULL表示这是链表上最后一个节点。

单链表也支持数据的查找、插入和删除操作，其中插入和删除操作只需要考虑相邻节点指针的变化，因此为常数级时间复杂度O(1)。要想随机访问第 k 个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点，因此时间复杂度为O(N)。

双向链表

双向链表和单链表不同的是多了一个前驱指针，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。因此存储同样多的数据，双向链表占用比单链表更多的空间。但其优点在于支持双向遍历，体现在以下两个方面。

• 在有序链表中查找某个元素，单链表由于只有后继指针，因此只能从前往后遍历查找时间复杂度为O(N)，而双向链表可以双向遍历。

• 删除给定指针指向的结点。假设已经找到要删除的节点，要删除就必须知道其前驱节点和后继节点，单链表想要知道其前驱节点只能从头开始遍历，时间复杂度为0(n)，而双向链表由于保存了其前驱节点的地址，因此时间复杂度为0(1)。

循环链表

循环链表与单、双链表不同的是其呈环状，单循环链表中其尾节点并非指向NULL而是指向头结点。双循环链表中其头节点的前驱指针指向尾节点，尾节点的后继指针指向头结点。循环链表的优势在于链尾到链头，链头到链尾比较方便适合处理的数据具有环型结构特点。

单向循环

双向循环

双向无环链表