引入：
前面我们已经讲了重要的一种数据结构——数组，如果说数组是方便读取数据，那么今天所学习的链表便是方便写入数据的数据结构，为什么这么说呢？让我们走进今天的链表学习。
首先让我们来看一个最基础的单向链表：
由图可见，链表和数组数据结构最主要的区别是链表是单线联络的，就像是工厂的产品，一般都是生产之后，然后交给超市等批发商，最后才能到达消费者的手中，产品的运输，就像是链表。
链表的基础概念
链表(linked list)是一种在物理中非连续 ，非顺序的数据结构，由若干节点(node)所组成。
由上图可知，单向链表又包含了两个部分，一是存放数据的变量data，另一个是指向下一个节点的指针next。
public static class Node{ int data; Node next; }
链表的第一个节点称为头节点，最后一个节点叫做尾节点，尾节点的next指针指向NULL。
那么，有的人就要发问了，链表总是通过一个节点寻找到下一个节点，那如何通过链表的一个节点寻找到它的前一个结点呢？
这就用到了双向链表：双向链表不仅拥有原来的data和next，还拥有指向前一个节点的指针prev。
如图所示：
接下来我们来看一下链表在内存中的存储方式：
如果说数组在内存中的存储方式为顺序存储，那么链表在内存中的存储方式就是随机存储。
何为随机存储呢？
上一篇博文中我们讲到数组在内存中的存储存储方式是顺序存储。而链表则是采用了见缝插针的方式。链表的每一个节点分配在内存中的不同位置，用next指针联系起来，这样可以灵活的运用零碎的内存空间。
如图所示：
（其中：灰色表示没有数据，绿色表示其他数据，红色表示该链表数据，直线指向为next指针指向，为3->1->6->4->8->7->6）。
链表的基本操作
查找节点
还是上面那个例子，如果工厂发现某一产品有质量问题，那么应该如何找到有质量问题的产品呢？
答案就是先从工厂开始找，无果，则去下一级经销商中寻找，无果，则通过下一级经销商找到下下一级经销商，若还没有，就继续寻找，最坏的结果就是直至找到最底一级——客户。由此可见，该查找方式就是一级一级寻找，链表亦是如此。
链表的查找方式就是从头结点开始，向后一个一个节点逐一查找。
例如给出一个链表，需要查找从头结点开始的第3个节点
1.第一步，将指针定位在头节点。
2.第二步，根据头结点的next ，定位到第二个节点。
3.第三步，根据第二个节点的next指针，定位到第三个节点，查找完毕。
更新节点
如果不考虑查找结点的过程，链表的更新会像数组一样简单，直接把旧数据改成新数据即可。
插入节点
与数组类似，链表插入节点时，同样分为三种情况。
尾部插入
中间插入
头部插入
尾部插入，是最简单的情况，把最后一个节点的next指针指向新插入的节点即可。
头部插入，可以分成两个步骤。
第一步，把新节点的next指针指向原先的头节点。
第二步，将新节点设置为链表的头节点。
中间插入，同样分为两个步骤。
第一步，新节点的next指针，只想插入位置的节点。
第二步，插入位置前置节点的next指针，指向新节点。
只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要考虑像数组一样的扩容问题。
下面我们来看一下插入操作的代码：
public class ClassNode{ //链表实际大小 private int size; //头结点指针 private Node head; //尾结点指针 private Node last; public static class Node{ int data;//数据域 Node next;//节点指针 Node(int data){ this.data = data; } //data为插入元素，index为插入位置 public void insert(int data,int index) throws Exception{ if(index < 0 || index > size){ throw new IndexOutOfBoundsException("超出链表结点范围！"); } Node insertedNode = new Node(data); if(size == 0){ //空链表 head = insertedNode; last = insertedNode;//链表的第一个节点既是头节点又是尾节点 }else if(index == 0){ //插入头部 insertedNode.next = head;//新节点指针指向原先的头节点 head = insertedNode;//新节点变为链表的头节点 }else if(size == index){ //插入尾部 last.next = insertedNode;//最后一个节点的指针指向新插入的节点 last = insertedNode;//新节点变为链表的尾节点 }else{ //插入中间 Node prevNode = get(index-1);//通过get函数找到插入位置的前一个节点 insertedNode.next = prevNode.next; prevNode.next = insertedNode; } size++; } }
附：链表查找元素的函数get（）
//find-查找的位置 public Node get(int find) throws Exception{ if(find < 0 || find > size){ throw new IndexOutOfBoundsException("超出链表结点范围！"); } Node temp = head; for(int i=0; i<find; i++){ temp = temp.next; } return temp; }
删除节点
链表的删除同样分为三种情况：
尾部删除
头部删除
中间删除
尾部删除，把倒数第二个节点的next指针指向空即可。
头部删除，也很简单，把链表的头节点设为原先头结点的next指针即可。
中间删除，也同样简单，把删除节点的前置节点的next指针，指向删除结点的下一个节点即可。
需要注意的是，许多高级语言如java，拥有自动化的垃圾回收装置，所以不用刻意去释放删除的节点，只要没有外部引用它们，被删除的节点就会自动释放。
代码如下：
//pos:删除的位置 public Node remove(int pos) throws Exception{ if(pos < 0 || pos > size){ throw new IndexOutOfBoundsException("超出链表节点范围！"); } Node removedNode = null; if(pos == 0){ //删除头节点 removedNode = head; head.next = head; }else if(pos == size-1){ //删除尾节点 Node prevNode = get(pos - 1); removedNode = prevNode.next; prevNode.next = null; }else{ //删除中间节点 Node prevNode = get(pos - 1); Node nextNode = prevNode.next.next; removedNode = prevNode.next; prevNode.next = nextNode; } size--; return removedNode; }
数组和链表
根据对于数组和链表的学习，我们知道它们都属于线性结构，而它们没有绝对的好与坏。
我们来对比一下性能：
| 查找 | 更新 | 插入 | 删除 | |
| 数组 | O（1） | O（1） | O（n） | O（n） |
| 链表 | O（n） | O（1） | O（1） | O（1） |
这个表格也印证了一开始的结论：读操作多，写操作少用数组，反之用链表。
