链表是什么？
上几篇文章中，分别介绍了动态数组，栈和队列，其中都是通过resize的方法进行动态扩容，从而实现了动态的数据结构，不过这种方法称为伪动态。真正的动态数据结构还要从链表说起，链表是真正的动态数据结构，一个动态数据结构不需要处理固定容量的问题，而且是最简单的动态数据结构，学好链表很重要，对后面复杂的数据结构是一种铺垫。链表见名知意，元素和元素之间就像链子一样拴住，元素也可以成为节点（Node），叫啥都行，反正能理解就好。每一个元素有两部分组成，一部分是元素本身，另一部分是下一个元素的引用。下文将元素本身就叫e，他的下一个引用就叫做next。
class Node<E>{ E e; //当前元素本身 Node next; //下一个元素的引用}
上图表示，第一个元素的e是1，他的next是2。第二个元素的e是2，他的next是3。最后一个元素的e是3，但next为null，因为3就是最后一个元素，可以说如果一个元素的next为null，就代表他是最后一个元素。如果我想找到2，那就通过1去找，如果我想找到3，那不好意思，你也得通过1去找，因为1和3之间没有直接的关联，只能先通过1先找到2，2里面有存储3的地址。这也代表链表没有随机访问的能力，比如数组可以通过索引去找，效率很高。链表想找一个元素只能从头到尾遍历去找，查询效率低。
链表的实现
首先创建了一个Node内部类，目的是只给LinkedList外部类用，外面的类是不可以操作Node对象的，这样做是比较安全的。成员变量分别是E e和Node next，e用于存储元素本身，next存储下一个元素的引用。LinkedList里面维护了两个变量，Node head和size，head用于存储目前链表的头元素，size用于维护链表里元素的个数。
public class LinkedList<E> { //内部维护一个Node对象，给外部类（LinkedList）使用 private class Node<E> { public E e; //当前Node对象的元素值 public Node next; //当前Node对象下一个对象的引用 public Node(E e,Node next) { this.e = e; this.next = next; } public Node(E e) { this.e = e; this.next = null; } public Node() { this.e = null; this.next = null; } } //头元素节点 private Node head; //当前链表节点个数 private int size; public LinkedList() { head = null; size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; }}添加一个头节点
添加头节点就是要创建一个新Node节点，新节点的e为666，新节点的next就指向了原来的头节点，改变指向后，要维护一下head，让新创建的这个节点变成头节点。最后维护一下size的个数。
public void addFirst(E e){ Node node = new Node(e); //创建一个节点 node.next = head; //节点的next为当前头节点 head = node; //改变head指向，现在头的位置变成了最新的node //head = new Node(e,head); 以上三步可简化成这种写法 size++;}按照索引位置添加元素
现在要把新元素添加到指定位置，比如索引为2的位置插入一个新元素。那就要找到索引2之前的那个元素，因为新元素插入后，要维护一下指向关系，原来是1的next为2，现在666的next变成了2，1的next为666。找到了1之后，先把1的next给666，让666的next先指向2，然后1的next在指向666就好啦。看下面图或者自己画一下就很清楚了。可是怎么能找到索引为1的元素呢？遍历！我们可以维护一个变量，用于保存每次next的值，可以看到从头元素到1的位置只需要一次next。
public void addByIndex(E e,int index) //index = 2{ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed. Because index is illegal."); if(index == 0) addFirst(e); //1.要想得到某个位置的元素，需要从第一个往后找，因为第一个存储的是第二个的"联系方式"，第二个存储的是第三个人的"联系方式"。 //这里循环只是遍历多少次才能拿到索引前的那个元素，里面的x变量没有任何使用意义。你也可以写成x = 1; x < index; 只要是循环次数算对了就行。 //0 1 2 3 ， 如果index = 2，那么待插入元素就是这样 0 1 _ 2 3 ，那么从头元素开始遍历，拿到索引为1的节点，只需要经过一次next Node prevNode = head; for(int x = 0; x < index - 1; x++) { head = prevNode.next; } //2.拿到currentNode后，维护指向关系 Node node = new Node(e); node.next = prevNode.next; prevNode.next = node; //currentNode.next = new Node(node,currentNode.next);//简略写法 size++;}虚拟节点的引入
实现上面的addByIndex方法时，需要对index为0时，做特殊判断处理。那能不能不做特殊判断，改变一种思想，让addFirst方法也能复用呢？办法是使用虚拟节点。设计一个dummyHead，每次在第0个位置添加元素时候，都可以通过dummyHead找到原来的头元素位置。然后按索引添加的逻辑就可以复用了。
private Node dummyHead;private int size;public LinkedList() { dummyHead = new Node(null, null); //创建虚拟节点 size = 0;}//链表头添加元素public void addFirst(E e) { addByIndex(e, 0);}//链表尾添加元素public void addLast(E e) { addByIndex(e, size);}public void addByIndex(E e, int index) //3{ if (index < 0 || index > size) throw new IllegalArgumentException("Add failed. Because index is illegal."); //如果index为3，那么从dummyHead到索引2的位置，一共要三次next。循环从0开始，然后<3，也就是0 1 2一共三次 Node currentNode = dummyHead; //从头元素开始遍历 dummy 0 1 2 -- 3 for (int x = 0; x < index; x++) { dummyHead = currentNode.next; } Node node = new Node(e); node.next = currentNode.next; currentNode.next = node; //currentNode.next = new Node(node,currentNode.next);//简略写法 size++;}在提供一些基础的方法，比如查询，删除，是否包含某个元素，修改某个元素。只要掌握了遍历链表的思想，其实万变不离其宗。要注意的就是控制好索引的边界。
public E get(int index) { if (index < 0 || index >= size) throw new IllegalArgumentException("Get filed.Index is not true!"); Node currentNode = dummyHead; for (int x = 0; x < index; x++) { currentNode = currentNode.next; } return (E) currentNode.next.e;}public E getFirst(){ return get(0);}public E getLast(){ return get(size - 1);}public void set(E e,int index){ if (index < 0 || index >= size) throw new IllegalArgumentException("Get filed.Index is not true!"); Node currentNode = dummyHead; for(int x = 0; x < index; x++) { currentNode = currentNode.next; } currentNode.next.e = e;}public boolean contains(E e){ Node currentNode = dummyHead; for(int x = 0; x < size; x++) { currentNode = currentNode.next; if(currentNode.e.equals(e)) { return true; } } return false;}@Overridepublic String toString() { StringBuffer sb = new StringBuffer(); sb.append("linkedHead["); Node currentNode = dummyHead; for(int x = 1; x <= size; x++) { currentNode = currentNode.next; sb.append(currentNode.e + "...."); } sb.append("]linkedFooter"); return sb.toString();}删除操作
//删除链表中的某个元素public E delete(int index){ Node currentNode = dummyHead; for(int x = 0; x < index; x++) { currentNode = currentNode.next; } Node delNode = currentNode.next; currentNode.next = delNode.next; delNode.next = null; size--; return (E) delNode.e;}