jdk源码阅读--（LinkedList）

一、linkedList底i层存储结构

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;
        }
    }

很明显是一个双向链表，并且会保存首尾指针。

二、获取某个位置的元素

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

/**     * Returns the (non-null) Node at the specified element index.     */    Node<E> node(int index) {        // assert isElementIndex(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;        }    }

很明显，先判断这个 index位置，距离头部近，还是尾部比较近。然后一个一个向前或向后遍历。最多O（n/2）时间。

三、set方法

/**
     * Inserts the specified element at the specified position in this list.
     * Shifts the element currently at that position (if any) and any
     * subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

如果在最后添加，直接添加。否则，先找到待插入位置的值，然后在它前面插入，就可以了。node方法用的最多。

四、indexOf方法，查找一个对象在链表中的位置

/**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index {@code i} such that
     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for
     * @return the index of the first occurrence of the specified element in
     *         this list, or -1 if this list does not contain the element
     */
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

这里有个疑问，为什么o!=null的时候，不调用==运算符，这样就可以不必分成if else的结构去写了。