1. 数据结构--LinkedList源码摘要

public class LinkedList
     
          extends AbstractSequentialList
      
           implements List
       
        , Deque
        
         , Cloneable, java.io.Serializable{    transient int size = 0;    /**     * Pointer to first node.     * Invariant: (first == null && last == null) ||     *            (first.prev == null && first.item != null)     */    transient Node
         
           first;    /**     * Pointer to last node.     * Invariant: (first == null && last == null) ||     *            (last.next == null && last.item != null)     */    transient Node
          
            last;}
          
         
        
       
      
     

LinkedList底层最重要的三个属性，size,first,last，可以看出，LinkedList是一个双向链表的数据结构。

private static class Node
     
       {        E item;        Node
      
        next;        Node
       
         prev;        Node(Node
        
          prev, E element, Node
         
           next) {            this.item = element;            this.next = next;            this.prev = prev;        }    }
         
        
       
      
     

Node节点包含 item元素、prev上一个节点和next下一个节点的引用。 2 LinkedList的底层数据的调整 add方法

/**     * Appends the specified element to the end of this list.     *     * 
This method is equivalent to {
    @link #addLast}.     *     * @param e element to be appended to this list     * @return {
    @code true} (as specified by {
    @link Collection#add})     */    public boolean add(E e) {        linkLast(e);        return true;    }

/**

     * Links e as last element.

     */

    void linkLast(E e) {

        final Node<E> l = last;

        final Node<E> newNode = new Node<>(l, e, null);

        last = newNode;

        if (l == null)

            first = newNode;

        else

            l.next = newNode;

        size++;

        modCount++;

    }

从源码中可以看出，在add方法中直接调用linkLast方法，该方法1.实例化一个node节点，追加到链表的末尾，2调整上一个

节点的下一个节点应用为新增节点。3修改last为新增的node节点。由此可以看出LinkedList的新增和删除操作效率明显。

get方法

 

/**     * Returns the element at the specified position in this list.     *     * @param index index of the element to return     * @return the element at the specified position in this list     * @throws IndexOutOfBoundsException {
    @inheritDoc}     */    public E get(int index) {        checkElementIndex(index);        return node(index).item;    } /**     * Returns the (non-null) Node at the specified element index.     */    Node
     
       node(int index) {        // assert isElementIndex(index);        if (index < (size >> 1)) {            Node
      
        x = first;            for (int i = 0; i < index; i++)                x = x.next;            return x;        } else {            Node
       
         x = last;            for (int i = size - 1; i > index; i--)                x = x.prev;            return x;        }    }
       
      
     

 

 

 

get方法中首先检查索引是否越界（return index >= 0 && index <= size;），第二部根据二分法判断索引是否大于size的一半，如果大于则从后往前检索，小于则从前往后检索。