链表和数组是数据类型中两个重要又常用的基础数据类型，数组是连续存储在内存中的数据结构，因此它的优势是可以通过下标迅速的找到元素的位置，而它的缺点则是在插入和删除元素时会导致大量元素的被迫移动，为了解决和平衡此问题于是就有了链表这种数据类型。
链表和数组可以形成有效的互补，这样我们就可以根据不同的业务场景选择对应的数据类型了。那么，本文我们就来重点介绍学习一下链表，一是因为它非常重要，二是因为面试面试必考，先来看本文的大纲：
看过某些抗日神剧我们都知道，某些秘密组织为了防止组织的成员被“一窝端”，通常会采用上下级单线联系的方式来保护其他成员，而这种“行为”则是链表的主要特征。
本文已收录至 Github《小白学算法》系列：https://github.com/vipstone/algorith
简介链表（Linked List）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针（Pointer）。
链表是由数据域和指针域两部分组成的，它的组成结构如下：
由于链表无需按顺序存储，因此链表在插入的时可以达到 O(1) 的复杂度，比顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表插入和查询的时间复杂度分别是 O(log n) 和 O(1)。
优缺点分析使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了节点的指针域，空间开销比较大。
分类链表通常会分为以下三类：
单向链表
双向链表
循环链表
单循链表
双循环链表
1.单向链表链表中最简单的一种是单向链表，或叫单链表，它包含两个域，一个数据域和一个指针域，指针域用于指向下一个节点，而最后一个节点则指向一个空值，如下图所示：
单链表的遍历方向单一，只能从链头一直遍历到链尾。它的缺点是当要查询某一个节点的前一个节点时，只能再次从头进行遍历查询，因此效率比较低，而双向链表的出现恰好解决了这个问题。
接下来，我们用代码来实现一下单向链表的节点：
private static class Node<E> { E item; Node<E> next; Node(E element, Node<E> next) { this.item = element; this.next = next; } } 2.双向链表双向链表也叫双面链表，它的每个节点由三部分组成：prev 指针指向前置节点，此节点的数据和 next 指针指向后置节点，如下图所示：
接下来，我们用代码来实现一下双向链表的节点：
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } 3.循环链表循环链表又分为单循环链表和双循环链表，也就是将单向链表或双向链表的首尾节点进行连接，这样就实现了单循环链表或双循环链表了，如下图所示：
学习了链表的基础知识之后，我们来思考一个问题：Java 中的链表 LinkedList 是属于哪种类型的链表呢？单向链表还是双向链表？