链表与数组在数据结构的江湖上被并称为南数组、北链表，其江湖地位可见一斑
概念
链表作为最基础的通用存储结构，它的作用和数组是一样的，但存储数据的方式略有不同。数组需要预先获取一定的内存空间，且内存的地址是连续的，在存储数据的时候，插入和删除都需要遍历数组，还需要移动部分数据，是十分低效的。而链表能够解决以上问题，下面来看一下链表的结构。
链表的数据项存储在链表节点中，一个节点可以叫Node也可以叫Link，它包含数据项和一个引用，数据项存储数据本身，通常是一个包含各种数据的类的对象，而引用则是引用下一个节点，一般记为next，链表的核心实现就是这个next，它标记了每个节点之间的联系，像一根线一样把这些散落在内存各个角落的节点对象串了起来。下面通过代码来直观的理解一下：
/**
* 链表的节点，用来存放数据
*/
public class Node {
// 数据变量
private String data;
// next引用
public Node next;
// 构造函数
public Node(String str) {
data = str;
}
// getter
public String getData() {
return data;
}
// Node的打印方法
public void displayNode() {
System.out.print("{ Node: " + data + " }..");
}
}
可以看到，链表节点的关键两个属性，一个是数据项（这里简单的表示为String类型的data），一个是指向下一个链表节点的next引用（这里为了访问简单设置为public），虽然还不知道下一个节点是谁，但在链表的数据数据结构中，将数据插入时，就会建立这个联系。
单向链表
以上说明了链表的重要概念，节点与引用，下面来展示如何构成一个链表，首先从最简单的单向链表开始，单向链表顾名思义，只有一端可以插入和访问的链表，链表类LinkList值仅维护第一个链表节点first的信息，其它的节点通过next引用，以下是实现代码：
/**
* 单向链表：维护头节点的信息，对链表的操作都从头部开始
*/
public class LinkList {
// 头节点的引用
Node first;
// 构造方法
public LinkList() {
first = null;
}
// 插入方法，头插法
public void insertFirst(String str) {
Node newNode = new Node(str);
newNode.next = first;
first = newNode;
}
// 删除方法，删除头部节点
public Node deleteFirst() {
Node temp = first;
first = first.next;
return temp;
}
// 打印链表方法
public void display() {
System.out.print("LinkList: ");
Node current = first;
while (current != null) {
current.displayNode();
current = current.next;
}
System.out.println();
}
// 判断链表是否为空的方法
public Boolean isEmpty() {
return first == null;
}
// 在链表中查找的方法
public Node find(String str) {
Node current = first;
while (current != null) {
if (current.getData() != str)
current = current.next;
return current;
}
System.out.println("could not find Node :" + str);
return null;
}
// 从链表中查找元素删除方法
public Node delete(String str) {
Node current = first;
Node previous = first;
while (current != null) {
if (current.getData() != str) {
previous = current;
current = current.next;
} else {
previous.next = current.next;
return current;
}
}
System.out.println("cloud not find Node:" + str + ", failed to delete it");
return null;
}
}
代码中定义了唯一一个变量：头节点的引用first，还有一些链表的常用方法：插入、删除、查找、展示等，可以发现这些方法都是由头节点first展开的，在表达这些方法的时候需要注意边界和特殊情况first的分析。
双端链表
注意是双端列表，不是双向链表，在上面的单向链表中，链表类仅维护了一个头节点的引用first，那么如果要在链表尾部插入一个数据，需要遍历整个链表，这种效率很低。双端链表不仅维护了first头节点的引用，而且还维护了last尾节点的引用，这样访问尾节点就像访问头节点一样方便，这种特性使得双端链表比起单向链表在一些场合更有效率，比如说队列。
以下展示双端链表的实现代码，节点还是引用上面的Node类
public class DoubleSideLinkList {
// 首节点和尾节点的引用
Node first;
Node last;
// constructor
public DoubleSideLinkList() {
first = null;
last = null;
}
// isEmpty
public boolean isEmpty() {
return first == null;
}
// insert first
public void insertFirst(String str) {
Node newNode = new Node(str);
if (isEmpty()) {
last = newNode;
}
newNode.next = first;
first = newNode;
}
// insert last
public void insertLast(String str) {
Node newNode = new Node(str);
if (isEmpty()) {
first = newNode;
}
last.next = newNode;
last = newNode;
}
// delete first
public Node deleteFirst() {
Node temp = first;
// 仅有一个元素
if (first.next == null)
last = null;
first = first.next;
return temp;
}
// display
public void displayList() {
System.out.println("List (first-->last): ");
Node current = first;
while(current != null) {
current.displayNode();
current = current.next;
}
System.out.println();
}
}
可以看出，双端链表可以很方便的从尾节点插入数据，这里需要说明的是，这个链表依然是单向的，每个节点也仅有一个引用next指向下一个节点，所以遍历和查找的方法与单向链表没什么差别，在此就不做展示。在实现双端链表的insert与delete方法的时候需要注意特殊情况：列表为空或者列表将要为空时，first与last的处理。
有序链表
有序链表中，数据是按照关键值的有序排列的，有序链表的插入速度优于有序数组，而且可以扩展到所有有效的内存，所以在很多场合可以使用有序链表，在以下的实现中，我们还是引用上面的Node类，因为数据项data为String类型，我们以数据项的hashcode为序来实现有序链表：
public class SortedLinkList {
// filed
Node first;
// constructor
public SortedLinkList() {
first = null;
}
public boolean isEmpty() {
return (first==null);
}
public void insert(String key) {
Node current = first;
Node previous = null;
Node newNode = new Node(key);
while (current != null && current.getData().hashCode() < key.hashCode()) {
previous = current;
current = current.next;
}
if (previous == null) {
first = newNode;
} else {
previous.next = newNode;
}
newNode.next = current;
}
public Node remove() {
Node temp = first;
first = first.next;
return temp;
}
public void display() {
System.out.print("LinkList: ");
Node current = first;
while (current != null) {
current.displayNode();
current = current.next;
}
System.out.println();
}
}
有序链表主要是insert方法比较难实现，也是需要考虑特殊情况，即链表为空。
双向链表
双向链表与双端链表不同，双端链表虽然可以从尾部插入节点，但是每个节点引用的还是其下一个节点，遍历也是单向的，而双向链表则可以从头部或者从尾部开始遍历，为了实现这一特性，我们需要修改一下节点类Node，为了区分，我们以Link为节点命名，在Link中，不仅实现对下一节点的引用next，而且还实现了对上一个节点的引用previous，如下：
public class Link {
private int data;
public Link next;
public Link previous;
public Link(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void displayLink() {
System.out.print(data + " ");
}
}
唯一不同的点就是指向上一个节点的引用previous，虽然仅在节点中加了一个引用，但是双向链表的实现却麻烦了很多，其中各种引用关系特别容易混乱，而且还有一些特殊情况需要考虑，下面一起来感受一下：
public class DoublyLinkList {
// 头节点和尾节点的引用，也是双端的
Link first;
Link last;
// constructor
public DoublyLinkList() {
first = null;
last = null;
}
// isEmpty
public boolean isEmpty() {
return first == null;
}
// insert first
public void insertFirst(int data) {
Link newLink = new Link(data);
if (isEmpty()) {
last = newLink;
} else {
first.previous = newLink;
}
newLink.next = first;
first = newLink;
}
// insert last
public void insertLast(int data) {
Link newLink = new Link(data);
if (isEmpty()) {
first = newLink;
} else {
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}
// insert after
public boolean insertAfter(int key, int data) {
Link newLink = new Link(data);
Link current = first;
// find
while(current != null) {
if (current.getData() != key) {
current = current.next;
} else {
if (current == last) {
newLink.next = null;
last = newLink;
} else {
newLink.next = current.next;
current.next.previous = newLink;
}
current.next = newLink;
newLink.previous = current;
return true;
}
}
System.out.println("cloud not find the key: " + data);
return false;
}
// delete first
public Link deleteFirst() {
Link temp = first;
if (first.next == null) {
last = null;
} else {
first.next.previous = null;
}
first = first.next;
return temp;
}
// delete last
public Link deleteLast() {
Link temp = last;
if (first.next == null) {
first = null;
} else {
last.previous.next = null;
}
last = last.previous;
return temp;
}
// delete key
public Link deleteKey(int data) {
Link current = first;
while (current != null) {
if (current.getData() != data) {
current = current.next;
} else {
if (current == first) {
first = first.next;
} else {
current.previous.next = current.next;
}
if (current == last) {
last = last.previous;
} else {
current.next.previous = current.previous;
}
return current;
}
}
System.out.println("cloud not find the key: " + data + ", delete failed!");
return null;
}
// display forward
public void displayForward() {
System.out.println("List (first-->last): ");
Link current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
System.out.println();
}
// display backward
public void displayBackward() {
System.out.println("List (last-->first): ");
Link current = last;
while (current != null) {
current.displayLink();
current = current.previous;
}
System.out.println();
}
}
这是一个双向链表，同时也是双端列表，可以从前向后或者从后向前遍历，也可以在链表的任何地方插入或是删除节点，在实现这些方法时，需要修改与插入或删除节点有关系的前后四个引用，且还需要考虑first与last、列表为空或者仅有一个元素的特殊情况，可以通过画图来加深理解。
效率与总结
以上我们介绍并实现了单向链表、双端链表、有序链表和双向链表，接下来我们来讨论一下这些链表的效率。
链表与数组作为通用数据结构经常被拿来做对比，以链表和数组这两个通用数据结构为基础的一些抽象数据模型，比如java中的ArrayList与LinkedList，也经常被拿出来作比较，总的来说主要有两大区别：
链表插入和删除的效率高于数组，链表插入、删除头节点、尾节点的时间效率为O(1)，而在链表中间插入、删某一节点的时间复杂度为O(N)，虽然与数组相同操作的时间复杂度相同，可是数组需要复制移动元素位置来填补空洞，所以链表的效率还是要优于数组的，特别是复制时间占比较重的情况中。
数组则是随机访问元素的效率要高于链表，可以通过数组下标直接访问的到。链表比数组优越的另一个重要因素就是，链表可以扩展到所有可用的内存空间，且不用像数组一样初始化容量，也不需要可以扩容。另外当一个数组对象需要一个连续的大内存空间时，会有几率触发jvm的GC去整理内存空间以获取一片连续的内存，而链表则没有这方面的限制，所以在内存的使用效率上，链表优于数组。
正如以上所述，一般来说，链表如果采用头插法(或删除)，则时间复杂度均为O(1)，而如果是随机插入或者向有序链表中插入的时间效率均为O(N)，因为需要找到合适的位置；
有序链表可以在O(1)的时间返回或删除最小或最大值，如果一个应用需要频繁的返回最小值且不需要快速的插入时间，则可以选择有序链表来实现，如优先级队列；
双向链表由于两端都可以插入、删除和遍历，所以可以用来做双端队列。
参考文章
《Data Structures & Algorithms in Java》 Robert Lafore著
