链表是在非连续的内存单元中保存数据，并且通过指针将各个内存单元链接在一起，最有一个节点的指针指向 NULL 。链表不需要提前分配固定大小存储空间，当需要存储数据的时候分配一块内存并将这块内存插入链表中。
在链表中查找第 n 个数据以及查找指定的数据的时间复杂度是 O(N) ，但是插入和删除数据的时间复杂度是 O(1) ，因为只需要调整指针就可以：
图 2.1 链表
图 2.2 向链表中插入一个数据
图 2.3 从链表中删除一个数据
向上面这样的链表结构在插入和删除的时候编程会比较困难，因为需要记住当前节点的前一个节点，这样才能完成插入和删除。为了简便通常使用带有头节点的链表：
图 2.4 带有头节点的单链表
上面的链表是单链表，此外还有双链表，就是节点中包含指向下一个节点的指针和指向上一个节点的指针：
图 2.5 双向链表
不带有头节点的双向链表在插入和删除数据的时候也不会出现单链表那样的问题。此外还有一种链表是循环链表，它是将双向链表的头尾相接：
图 2.6 双向循环链表
向循环双向链表和循环链表中插入或者从中删除数据只是多移动几个指针。