在上一篇博文中，我们实现了顺序表MyArrayList，并且分析了它在不同情形下的操作效率不同。对于MyArrayList来说，
我们要读取或修改某一个位置的元素只花费常数时间 O(1)； 我们要增加或删除某一个元素最坏情况下要花费线性时间 O(n)
因此，当我们在遇到频繁访问列表中元素时，ArrayList是一个很好的选择；但当我们需要频繁添加、删除列表中元素，尤其是在表的前端进行增删操作时，ArrayList就不是一个特别好的选择了。
那么，有没有一种数据结构能让高效地让我们增加、删除列表中的元素呢？
答案就是：链表
链表是一种物理存储单元上非连续、非顺序的存储结构。它由一系列结点（链表中每一个元素称为结点）组成。其中，每个节点都包括存储数据元素的数据域，和存储下一个结点地址的指针域(若是双向链表则包含两个指针域，一个指向前驱节点，一个指向后继节点)。
双向链表由于比单向链表多存储一个指针域，因此能够前后两个方向进行遍历；而单向链表只能单方向向后遍历。这就是计算机中典型的增加空间复杂度来降低时间复杂度。
我们在这里来实现一个双向链表MyLinkedList。与之前一样，我们要先分析如何来建立这样一个数据结构。
MyLinkedList： 1. MyLinkedList需要装各种类型的元素，因此需要使用泛型 2. MyLinkedList中的元素(节点)包含着一个数据域、两个指针域，因此我们应该把节点作为一个内部类实现。 3. MyLinkedList应该提供常用的集合操作方法：
- get(int index) //返回指定位置元素- set(int index, E element) //修改指定位置的元素- add(E element) //在列表末尾增加元素- add(int index, E element) //在指定位置添加元素- remove(int index) //删除指定位置的元素- remove(E element) //从列表中删除指定的元素- contains(E element) //检查列表中是否存在指定元素- size() //返回列表中元素的个数- clear() //清空列表中所有的元素- isEmpty() //检查列表是否为空- 等等……既然理清了思路我们就来一步步地构建自己的MyLinkedList吧
public class MyLinkedList<E> { PRivate int size=0; //列表中元素的个数 private Node firstNode; //列表中的头节点，此节点不存储任何数据 private Node lastNode; //列表着的尾节点，此节点不存储任何数据 public MyLinkedList(){ //初始化头节点,此时头节点的前驱节点指向null,后继节点指向null //因为此时尾节点还没初始化，无法指向 firstNode = new Node(null,null,null); //初始化尾节点,此时尾节点的前驱节点指向头节点,后继节点指向null lastNode = new Node(null,firstNode,null); //将头节点的后继节点指向尾节点 firstNode.nextNode = lastNode; } //建立内部类Node用来表示每一个列表中的元素 class Node{ E data; //节点的数据域 Node prevNode; //节点的前驱指针域，指向前一个Node Node nextNode; //节点的后继指针域，指向后一个Node Node(E data, Node prevNode, Node nextNode){ this.data = data; this.prevNode = prevNode; this.nextNode = nextNode; } };接下来我们提供几个简单的获取元素数量、查看是否为空的方法
public int size(){ return this.size; } public boolean isEmpty(){ return size()==0; } //清空列表中的所有节点,将每个节点的数据域与指针域都指向null，来帮助GC工作 public void clear(){ for(Node n = firstNode; n != null;){ Node next = n.nextNode; n.data =null; n.prevNode = null; n.nextNode = null; n = next; } firstNode = lastNode = null; this.size = 0; }接着我们提供两种不同情形下的插入方法
public boolean add(E element){ //新建一个节点，前驱节点指向尾节点的前一个节点，后继节点指向尾节点 Node n = new Node (element,lastNode.prevNode,lastNode); //原先尾节点的前一个节点的后继节点指向我们新建的节点 lastNode.prevNode.nextNode = n; //尾节点的前驱节点指向我们新建的节点 lastNode.prevNode = n; this.size++; return true; } public void add(int index, E element){ //一旦要插入元素的位置为负或大于目前的元素数量就抛出异常 //此处允许index等于size，相当于在列表末尾插入元素 if(index<0 || index>size()) throw new IndexOutOfBoundsException(); Node n; int i; //通过for循环，n将指向我们需要插入位置节点的前驱节点 for(i=0,n = firstNode; i<index; i++){ n = n.nextNode; } Node newNode = new Node(element, n , n.nextNode); //n节点的后继节点的前驱节点指向newNode n.nextNode.prevNode = newNode; //n节点的后继节点指向newNode n.nextNode = newNode; this.size++; }接下来我们提供两种不同的删除方法
public boolean remove(E element){ //如果删除的元素为null if(element == null){ for(Node n = firstNode.nextNode; n.nextNode!=null;){ if(n.data == null){ //将找到节点的前驱节点的后继结点指向该节点的后继节点 n.prevNode.nextNode = n.nextNode; //将找到节点的后继结点的前驱节点指向该节点的前驱节点 n.nextNode.prevNode = n.prevNode; //将该节点的指针域以及它本身都指向null，方便GC工作 n.prevNode = null; n.nextNode = null; n=null; this.size--; return true; } n = n.nextNode; } return false; }else{ //如果删除的元素不为null for(Node n = firstNode.nextNode; n.nextNode!=null;){ if(element.equals(n.data)){ //将找到节点的前驱节点的后继结点指向该节点的后继节点 n.prevNode.nextNode = n.nextNode; //将找到节点的后继结点的前驱节点指向该节点的前驱节点 n.nextNode.prevNode = n.prevNode; //将该节点的指针域以及它本身都指向null，方便GC工作 n.prevNode = null; n.nextNode = null; n = null; this.size--; return true; } n = n.nextNode; } return false; } } public void remove(int index){ checkValidIndex(index); Node n = getNodeByValidIndex(index); //将找到节点的前驱节点的后继结点指向该节点的后继节点 n.prevNode.nextNode = n.nextNode; //将找到节点的后继结点的前驱节点指向该节点的前驱节点 n.nextNode.prevNode = n.prevNode; //将该节点的数据域、指针域以及它本身都指向null，方便GC工作 n.data = null; n.nextNode = null; n.prevNode = null; n = null; this.size--; } private void checkValidIndex(int index){ //一旦要插入元素的位置为负或大于目前的元素数量就抛出异常 //此处不允许index等于size if(index<0 || index>=size()) throw new IndexOutOfBoundsException(); } //通过合法的index来获取当前的节点 private Node getNodeByValidIndex(int index){ Node n; int i; for(i=0,n=firstNode.nextNode;i<index;i++){ n = n.nextNode; } return n; }实现完了添加、删除方法之后，我们最后实现获取、修改与查看是否存在三个简单的方法
public E get(int index){ checkValidIndex(index); Node n = getNodeByValidIndex(index); return n.data; } public void set(int index, E element){ checkValidIndex(index); Node n = getNodeByValidIndex(index); n.data = element; } public boolean contains(E element){ if(element == null){ for(Node n = firstNode.nextNode; n.nextNode!=null;){ if(n.data == null){ return true; } n = n.nextNode; } return false; }else{ //如果查找的元素不为null for(Node n = firstNode.nextNode; n.nextNode!=null;){ if(element.equals(n.data)){ return true; } n = n.nextNode; } return false; } }我们在这里也分析一下MyLinkedList的特点：
我们要读取或修改某一个位置的节点需要花费线性时间 O(n)去遍历列表； 我们要增加或删除某一个(已知位置的)节点最坏情况下要花费常数时间 O(1)
因此，当我们在遇到频繁访问列表中元素时，ArrayList是一个很好的选择；但当我们需要频繁在已知位置添加、删除列表中元素时，LinkedList有更好的性能。
那么到这里，我们自己实现的双向链表就也完成了。感兴趣的同学可以自己实现一个单向链表(将Node中的指针域变为一个)，或是循环链表(将尾节点的后继节点指向头节点)。
java源码中提供的LinkedList实现类也是一个双向链表，因此大家可以参考一下源码中是如何实现的，来改进我们的MyLinkedList。
本博文源码下载地址，欢迎下载测试。
新闻热点
疑难解答
