数据结构（链表）的应用——单向链表和双向链表（LinkedList）

链表是线性表的其中之一，线性表又是我们要学的数据结构的一部分，所以非常有学习价值，我们今天专门分析单链表和双链表。

一、单链表

存储结构
上图就是单链表的存储结构原理图，由图中我们可以看出每个节点都由两部分构成，一个是data数据域、另一个是指向下一个节点的next指针域，指针域不存放任何数据。然后一直通过这样的方式一直指下去，最后就形成了一条类似铁链的结构，所以称为链表。我们看到最后的next指针为null,说明到了最后一个节点，最后一个节点的指针域不指向任何节点，所以next=null。
代码实现

/**
 * Created by bryanrady on 2017/12/7.
 *  单链表的实现
 */

public class SinglyLinkedList<E>{

private Node<E> first;      //单链表的头结点
private Node<E> last;       //单链表的最后一个节点  
private int size;

public SinglyLinkedList(){

}

public SinglyLinkedList(SinglyLinkedList c){
    this();
    addAll(c);
}

static class Node<E>{
    E data;     //数据域
    Node<E> next;   //指针域

    public Node(E data){
        this.data = data;
    }
}

/**
 * 返回单链表的长度
 * @return
 */
public int size(){
    return size;
}

/**
 * 在单链表尾部添加一个元素节点
 * @param element
 */
public void add(E element){
    Node<E> node = new Node<E>(element);
    Node<E> l = last;
    if(l == null){  //表明之前没有节点
        first = node;
    }else{
        l.next = node;
    }
    last = node;
    size++;
}

/**
 * 删除节点
 */
public E remove(){
    return removeFirst();
}

/**
 * 删除第一个节点
 * @return
 */
private E removeFirst(){
    Node<E> f = first;
    if(f == null){
        throw new NoSuchElementException();
    }
    return unlinkFirst(f);
}

/**
 * 删除第一个节点
 * @param node
 * @return
 */
private E unlinkFirst(Node<E> node) {
    E element = node.data;
    Node<E> next = node.next;
    node.data = null;
    node.next = null;
    first = next;
    if(next == null){
        last = null;
    }
    size--;
    return element;
}

/**
 * 在链表尾部添加一个集合
 * @param list
 * @return
 */
public boolean addAll(SinglyLinkedList<E> list){
    return  addAll(size,list);
}

/**
 * 返回单链表的Object[]数组
 * @return
 */
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    Node<E> e = first;
    while(e!=null){
        result[i++] = e.data;
        e = e.next;
    }
    return result;
}

/**
 * 在指定位置添加集合
 * @param index
 * @param list
 * @return
 */
private boolean addAll(int index,SinglyLinkedList<E> list){
    if(index<0 || index > size){
        throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
    }
    Object[] a = list.toArray();
    int numNew = a.length;
    if(numNew == 0){
        return false;
    }
    for(Object o : a){
        E e = (E)o;
        Node<E> newNode = new Node<>(e);
        if(last==null){
            first = newNode;
        }else{
            last.next = newNode;
        }
        last = newNode;
    }
    size += numNew;
    return true;
}

/**
 * 根据传入的Index查找节点
 * @param index
 * @return
 */
private Node<E> node(int index){
    Node<E> x = first;
    for(int i=0;i<index;i++){
       x = x.next;
    }
    return x;
}

public E get(int index){
    if(index<0||index>=size){
        throw new IndexOutOfBoundsException("Index:"+index);
    }
    return node(index).data;
}

}

我这里没有像其他实现者一样定义头结点是空的数据域，但是实现思路和方法基本都是一模一样的。我是采用的LinkedList代码的思想来进行实现，后面有时间再添加其他有关于集合的方法。

二、双向链表

双向链表与单链表比较就是多了一个指向前驱节点的指针，这样来构成有序性。我们常用的LinkedList就是在双向链表的数据结构上进行实现的，现在我们直接来分析源代码。

LinkedList简介 LinkedList是基于双向循环链表（从源码中可以很容易看出）实现的，除了可以当作链表来操作外，它还可以当作栈，队列和双端队列来使用。LinkedList同样是非线程安全的，只在单线程下适合使用。

继承关系与实现的接口

 public class LinkedList<E>
         extends AbstractSequentialList<E>
         implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList继承了AbstractSequentialList，而AbstractSequentialList又是AbstractList<E>的一个子类，这就是集合框架架构图，这里不详细介绍，后面再总结。

LinkedList实现了Deque（双端队列）接口，即LinkedList可以作为一个双端队列来使用。

LinkedList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了Cloneable接口，能被克隆。

数据结构，就是一个双向链表

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.属性字段

  transient int size = 0;    //链表中的节点个数

  transient Node<E> first;    //定义链表头结点

  transient Node<E> last;    //定义最后一个节点

4.构造函数

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

增删改查操作
（1）添加操作

   /**
    * 添加元素
    * @param e
    * @return
    */
   public boolean add(E e){
       linkLast(e);
       return true;
   }

   /**
    * 在指定的位置往集合中添加元素e
    * @param index
    * @param e
    */
   public void add(int index,E e){
       checkPositionIndex(index);
       if(index == size){
           linkLast(e);
       }else{
           linkBefore(e,node(index));
       }
   }

   /**
    * 添加元素作为第一个节点
    * @param e
    */
   public void addFirst(E e){
       linkFirst(e);
   }

   /**
    * 添加元素作为最后一个节点
    * @param e
    */
   public void addLast(E e){
       linkLast(e);
   }

   /**
    * 在链表头部添加元素e,并将元素e作为第一个元素
    * @param e
    */
   private void linkFirst(E e){
       Node<E> f = first;
       Node<E> newNode = new Node<>(null,e,f);
       first = newNode;
       if(f==null){
           last = newNode;
       }else{
           f.prev = newNode;
       }
       size++;
   }

   /**
    * 在链表尾部添加元素e,并将e作为最后一个元素
    * @param e
    */
   private void linkLast(E e){
       Node<E> l = last;
       Node newNode = new Node(l,e,null);
       if(l == null){
           first = newNode;
       }else{
           l.next = newNode;
           newNode.prev = l;
       }
       last = newNode;
       size++;
   }

   /**
    * 在非空节点succ之前插入元素e
    * @param e
    * @param succ
    */
   private void linkBefore(E e,Node<E> succ){
       Node<E> pred = succ.prev;
       Node<E> newNode = new Node<>(pred,e,succ);
       if(pred == null){
           first = newNode;
       }else{
           pred.next = newNode;
       }
       succ.prev = newNode;
       size++;
   }


/**
    * 将集合c追加到LinkedList中
    * @param c
    * @return
    */
   public boolean addAll(Collection<? extends E> c){
       return addAll(size,c);
   }

   /**
    * 将集合c添加到LinkedList的指定位置
    * @param index
    * @param c
    * @return
    */
   public boolean addAll(int index,Collection<? extends E> c){
       checkPositionIndex(index);
       Object[] a = c.toArray();
       int numNew = a.length;
       if(numNew==0){
           return false;
       }
       Node<E> pred,succ;  //设置当前要插入节点的前后节点
       if(index==size){
           succ = null;
           pred = last;
       }else{
           succ = node(index);
           pred = succ.prev;
       }

       /****插入开始***/
       for(Object o : a){
           E e = (E)o;
           Node<E> newNode = new Node<>(pred,e,null);
           if(pred==null){
               first = newNode;
           }else{
               pred.next = newNode;
           }
           //此时把下一个要插入的节点的上一个节点变成刚刚插入的节点
           pred = newNode;
       }
       /****插入完成***/

       //设置前后节点的关系
       if(succ == null){
           last = pred;
       }else{
           pred.next = succ;
           succ.prev = pred;
       }
       size += numNew;
       return true;
   }

(2)删除操作

/**
     * 删除元素，默认删除第一个,并返回
     * @return
     */
    public E remove(){
        return removeFirst();
    }

    /**
     * 删除集合中指定位置的元素
     * @param index
     * @return
     */
    public E remove(int index){
        checkElementIndex(index);
        return unlink(node(index));
    }

    /**
     * 在集合中删除指定的对象
     * @param o
     * @return
     */
    public boolean remove(Object o){
        if(o == null){
            for(Node<E> x=first;x!=null;x=x.next){
                if(x.element == null){
                    unlink(x);
                    return true;
                }
            }
        }else{
            for(Node<E> x=first;x!=null;x=x.next){
                if(x.element.equals(o)){
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 删除链表的第一个元素并返回
     * @return
     */
    public E removeFirst(){
        Node<E> f = first;
        if(f == null){
            throw new NoSuchElementException();
        }
        return unlinkFirst(f);
    }

    /**
     * 删除链表的最后一个元素，并返回
     * @return
     */
    public E removeLast(){
        Node<E> l = last;
        if(l == null){
            throw new NoSuchElementException();
        }
        return unlinkLast(l);
    }

    /**
     * 清空链表     循环遍历全部置为null
     */
    public void clear(){
        for(Node<E> x=first;x!=null;x=x.next){
            x.element =null;
            x.prev = null;
            x.next = null;
            x = null;
        }
        first = last = null;
        size = 0;
    }

    /**
     * 删除一个非空节点x，并返回
     * @param x
     * @return
     */
    private E unlink(Node<E> x){
        E element = x.element;
        Node<E> pred = x.prev;
        Node<E> succ = x.next;
        if(pred == null){
            first = succ;
        }else{
            pred.next = succ;
            x.prev = null;
        }
        if(succ == null){
            last = pred;
        }else{
            succ.prev = pred;
            x.next = null;
        }
        x.element = null;
        size--;
        return element;
    }

    /**
     * 删除不为空的第一个节点
     * @param f
     */
    private E unlinkFirst(Node<E> f){
        E element = f.element;
        Node<E> succ = f.next;
        f.element = null;     //help gc
        f.next = null;
        first = succ;
        if(succ == null){
            last = null;
        }else{
            succ.prev = null;
        }
        size--;
        return element;
    }

    /**
     * 删除不为空的最后一个节点
     * @param l
     * @return
     */
    private E unlinkLast(Node<E> l){
        E element = l.element;
        Node<E> pred = l.prev;
        l.element = null;
        l.prev = null;
        last = pred;
        if(pred == null){
            first = null;
        }else{
            pred.next = null;
        }
        size--;
        return element;
    }

(3)更新操作

/**
     * 修改在链表中指定位置的元素
     * @param index
     * @param e
     * @return
     */
    public E set(int index,E e){
        checkElementIndex(index);
        Node<E> oldNode = node(index);
        E oldVal = oldNode.element;
        oldNode.element = e;
        return oldVal;
    }

(4)查询操作

/**
     * 根据index获取集合中的指定的元素
     * @param index
     * @return
     */
    public E get(int index){
        checkElementIndex(index);
        return node(index).element;
    }

    /**
     * 获取第一个节点上的元素
     * @return
     */
    public E getFirst(){
        Node<E> f = first;
        if(f == null){
            throw new NoSuchElementException();
        }
        return f.element;
    }

    /**
     * 获取最后一个节点的元素
     * @return
     */
    public E getLast(){
        Node<E> l = last;
        if(l == null){
            throw new NoSuchElementException();
        }
        return l.element;
    }

    /**
     * 根据index位置获取节点
     *  利用双向链表的特点提高查找效率
     * @param index
     * @return
     */
    private Node<E> node(int index){
        if(index < (size>>1)){  //说明要查找的节点在前半部分
            Node<E> x = first;
            for(int i=0;i<index;i++){
                x = x.next;
            }
            return x;
        }else{  //说明要查找的节点在前半部分
            Node<E> x = last;
            for(int i=size-1;i>index;i--){
                x = x.prev;
            }
            return x;
        }
    }

6.集合的一些常规方法

/**
     * 返回LinkedList的大小
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 判断集合是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }
/**
     * 判断链表集合中是否包含此对象
     * @param o
     * @return
     */
    public boolean contains(Object o){
        return indexOf(o) >= 0;
    }

    /**
     * 获取对象o在链表集合中的索引位置
     * @param o
     * @return
     */
    public int indexOf(Object o){
        int index = 0;
        if(o == null){
            for(Node<E> x=first;x!=null;x=x.next){
                if(x.element == null){
                    return index;
                }
                index++;
            }
        }else{
            for(Node<E> x=first;x!=null;x=x.next){
                if(x.element.equals(o)){
                   return index;
                }
                index++;
            }
        }
        return -1;
    }

    /**
     * 返回此对象在链表中最后出现的位置
     * @param o
     * @return
     */
    public int lastIndexOf(Object o){
        int index = size-1;
        if(o == null){
            for(Node<E> x=last;x!=null;x=x.prev){
                if(x.element == null){
                    return index;
                }
                index--;
            }
        }else{
            for(Node<E> x=last;x!=null;x=x.prev){
                if(x.element.equals(o)){
                    return index;
                }
                index--;
            }
        }
        return -1;
    }

    /**
     *  添加元素的时候检查索引位置
     * @param index
     */
    private void checkPositionIndex(int index){
        if(index<0 || index>size) {
            throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);
        }
    }

    /**
     * 在删除和获取元素时判断检查下标位置
     * @param index
     */
    private void checkElementIndex(int index){
        if(index<0 || index>=size) {
            throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);
        }
    }

    /**
     * 返回LinkedList的Object数组
     * @return
     */
    public Object[] toArray(){
        Object[] o = new Object[size];
        int i=0;
        for(Node<E> x=first;x!=null;x=x.next){
            o[i++] = x.element;
        }
        return o;
    }

7.LinkedList作为双端队列的方法

/***    LinkedList实现了Deque<E>接口，Deque<E>接口对Queue<E>接口进行了扩展</>
     * </>  LinkedList作为队列使用
     *      一般用LinkedList作为队列使用较多，使用栈的时候最好还是使用Stack<E>这个类
     * </>*****/

    /**
     * 往队列尾部添加元素
     * @param e
     * @return
     */
    public boolean offer(E e){
        return add(e);
    }

    /**
     * 从队列头部取元素,并删除
     * @return
     */
    public E poll(){
        Node<E> f = first;
        if(f == null){
            return null;
        }
        return unlinkFirst(f);
    }

    /**
     * 从队列头部读取元素，但是不删除
     * @return
     */
    public E peek(){
        Node<E> f = first;
        if(f == null){
            return null;
        }
        return f.element;
    }

    public boolean offerFrist(E e){
        addFirst(e);
        return true;
    }

    public boolean offerLast(E e){
        addLast(e);
        return true;
    }

    public E pollFirst(){
        Node<E> f = first;
        if(f == null){
            return null;
        }
        return unlinkFirst(f);
    }

    public E pollLast(){
        Node<E> f = first;
        if(f == null){
            return null;
        }
        return unlinkLast(f);
    }

    public E peekFirst(){
        Node<E> f = first;
        if(f == null){
            return null;
        }
        return f.element;
    }

    public E peekLast(){
        Node<E> l = last;
        if(l == null){
            return null;
        }
        return l.element;
    }

LinkedList作为栈的使用方法

/***    LinkedList还可以当成是栈来使用  *****/

    /**
     * 往栈顶添加元素,就是在链表前面添加元素作为第一个节点
     * @param e
     */
    public void push(E e){
        addFirst(e);
    }

    /**
     * 往栈顶取元素并删除，即删除链表前面删除元素，这样在就满足了栈的先进后出的原则
     *  还有个不删除的就是和peek（）方法一样
     * @return
     */
    public E pop(){
        return removeFirst();
    }

看了这么多LinkedList的方法，现在我们来总结一下ArrayList和LinkedList的区别（也是顺序表和链表的区别）：

（1）ArrayList是基于动态数组实现的，LinkedList是基于双向链表实现的。

（2）ArrayList支持随机访问（通过下标），LinkedList不支持。

（3）ArrayList的查询和尾部插入元素效率较高，中间插入和删除元素效率较低，因为有大量的数组复制操作。
LinkedList的插入和删除效率较高，只需要把节点指针改变一下就行，但是查询效率较低，即使有双向链表的特性可以从两个方向查找，但还是需要使用蛮力法的方式进行遍历，所以效率较低。

（4）ArrayList会造成一定的空间浪费，因为随时需要探测数组容量然后扩容；LinkedList通过节点方式进行存放数据，不存在空间浪费。