LinkedList部分源码实现

LinkedList内部的实现原理是双向链表，每一个内部Node保存有指向前后Node的指针，故而其增删效率较高；而需要查询时则需要遍历链表元素，所以查询效率较低。

先定义一个内部节点Node，储存元素本身和指向前后Node的指针：

class Node<E>{
    E el;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E el, Node<E> next){
         this.el= el;
         this.next = next;
         this.prev = prev;
    }

    @Override
    public String toString() {
        return el.toString();
    }
}

接着实现双向链表LinkedList：

public class LinkedList<E> {
    private int size;
    private Node<E> first;
    private Node<E> last;

    public void add(E element){
        Node<E> node;
        if (first == null){
            node = new Node<>(null,element,null);
            first = node;
            last = node;
        }else {
            node = new Node<>(last,element,null);
            last.next = node;
            last = node;
        }
        size ++;
    }

    public void add(int index,E element){
        if (index>size || index<0){
            throw new RuntimeException("index Error!");
        }
        Node<E> node;
        if(index == 0){
            node = new Node<>(null,element,first);
            first.prev = node;
            first = node;
        }else if(index == size-1){
            node = new Node<>(last,element,null);
            last.next = node;
            last = node;
        }else {
            Node<E> x = get(index);
            node = new Node<>(x.prev,element,x);
            x.prev.next = node;
            x.prev = node;
        }
        size++;
    }

    public int size(){
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node temp  = first;
        while(temp!=null){
            sb.append(temp.el).append(",");
            temp = temp.next;
        }
        sb.setCharAt(sb.length()-1,']');
        return sb.toString();
    }

    public Node<E> get(int index){
        if (index>size || index<0){
           throw new RuntimeException("index Error!");
        }
        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;
        }
    }

    public void remove(int index) {
        Node<E> x = get(index);
        if (x.equals(first)){
            first = x.next;
            first.prev = null;
        }else if (x.equals(last)){
            last = x.prev;
            last.next = null;
        }else {
            x.prev.next = x.next;
            x.next.prev = x.prev;
        }
        size--;
    }
}