跟Java集合学数据结构之 LinkedList

链表是很常见的一种数据结构。通常有两种实现方式：一种是使用数组，一种使用指针。数组涉及数据移动和扩容问题，但随机查找方便；指针插入删除方便，但随机查找不方便

下面学习java的LinkedList（双向链表），由于java没有指针，所以使用对象来实现。以下精简版：
常见方法：add、get、remove、size、isEmpty等，简单起见就不抽取父类了

public class MyLinkedList<T>  {

    /** 节点 */
    @SuppressWarnings("hiding")
    private class LinkedNode<T> {
        private T value;
        private LinkedNode<T> prev;
        private LinkedNode<T> next;
        public LinkedNode(T value, LinkedNode<T> prev, LinkedNode<T> next) {
            this.value = value;
            this.prev = prev;   // 前向
            this.next = next;   // 后向
        }
    }
    
    /** 元素数 */
    private transient int size;
    
    /** 头部 */
    private transient LinkedNode<T> first;
    
    /** 尾部 */
    private transient LinkedNode<T> last;
    
    public boolean addFirst(T element) {
        linkFirst(element);
        return true;
    }
    
    // 头部添加数据
    private void linkFirst(T element) {
        LinkedNode<T> temp = first;
        LinkedNode<T> newNode = new LinkedNode<>(element, null, null);
        first = newNode;    // 第一个节点改为新结点
        
        if (last == null) {
            last = newNode;
        } else {
            // 将原来的首节点的前向设为新节点
            temp.prev = first;
        }
        size++;
    }
    
    // 尾部添加数据
    public boolean addLast(T element) {
        linkLast(element);
        return true;
    }
    
    private void linkLast(T element) {
        LinkedNode<T> temp = last;
        LinkedNode<T> newNode = new LinkedNode<>(element, null, null);
        last = newNode;     // 最后一个节点改为新结点
        
        if (first == null) {
            first = newNode;
        } else {
            // 将原来的尾节点的后向设为新节点
            temp.next = last;
        }
        size++;
    }
    
    // 头部删除数据
    public T removeFirst() {
        
        final LinkedNode<T> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    
    private T unlinkFirst(LinkedNode<T> f) {
        final T element = f.value;  // 用于返回数据
        final LinkedNode<T> next = f.next;
        
        f.value = null;
        f.next = null;
        first = next;
        if (next == null)
            last = null;    // 已经没有元素
        else
            // 第一个元素前向应为null
            next.prev = null;
        size--;
        
        return element;
    }
    
    // 尾部删除数据
    public T removeLast() {
        final LinkedNode<T> l = last;
        if (l == null)
            throw new NoSuchElementException();
        
        return unlinkLast(l);
    }
    
    private T unlinkLast(LinkedNode<T> l) {
        final T element = l.value;  // 用于返回数据
        final LinkedNode<T> prev = l.prev;
        
        l.value = null;
        l.prev = null;
        last = prev;
        if (prev == null)
            first = null;   // 已经没有元素
        else
            // 最后一个元素后向应为null
            prev.next = null;
        size--;
        
        return element;
    }
    
    public T getLast() {
        if (last != null) {
            return last.value;
        }
        return null;
    }
    
    public T getFirst() {
        if (first != null) {
            return first.value;
        }
        return null;
    }
}

删除数据方法未添加，这里简单说一下就行：

• 删除指定数据，JDK实现：如果数据是null走一个循环专门检测空值；不是null，专门一个循环，用equal判断是否是要找的数据
• 删除指定位置的数据，检测 position < （size >> 1）成立使用first遍历 position次找到数据；否则使用last前向遍历position次