[TOC] # 链表 定义： * 是一种线性结构 * 最简单的动态数据结构 * 更深入的理解引用（或者指针） * 更深入的理解递归 * 辅助组成其它数据结构 * 数据存储在“节点”（Node）中 ``` class Node { $e; Node next;---------指向下一个节点 } ```  # 链表的优缺点 优点：真正的动态，不需要处理固定容量的问题 缺点：丧失了随机访问的能力 原因： * 在计算机底层，数组是开辟连续的一段内存空间，是连续的，所以可以通过索引快速找到 * 链表不是一块连续的内存空间，是通过指针指向下一个地址，将一系列不连续的内存联系起来，将那种碎片内存进行合理地利用，解决空间的问题。 # 链表的类型 * 单向链表 > 单向链表包含两个域，一个是信息域，一个是指针域。也就是单向链表的节点被分成两部分，一部分是保存或显示关于节点的信息，第二部分存储下一个节点的地址，而最后一个节点则指向一个空值  * 双向链表 > 每个节点有两个链接，一个是指向前一个节点（当此链接为第一个链接时，指向的是空列表或空值），另一个则指向后一个节点（当此链接为最后一个链接时，指向的是空值或空列表）。意思就是说双向链表有两个指针，一个是指向前一个节点的指针，另一个则指向后一个节点的指针 >  * 循环链表 > 循环链表就是首节点和末节点被连接在一起。循环链表中的第一个节点之前就是最后一个节点，反之亦然 >