LinkedList: 如何存取一个元素？

LinkedList的结构

LinkedList是一个双向链表

  
    transient int size = 0;

    /**
     * 首节点
     */
    transient Node<E> first;

    /**
     * 尾节点
     */
    transient Node<E> last;

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

1.如何存一个元素？

双向链表中存一个元素，最常用的是在首节点向前追加或者在尾节点向后追加或者在某个节点前后追加，LinkedList都支持，而添加新元素linkedList在向尾节点向后追加。

• 在首节点向前追加

    // 向前追加
    public void addFirst(E e) {
        linkFirst(e);
    }

    private void linkFirst(E e) {
        // 记录当前首节点
        final Node<E> f = first;
       // 生成新的首节点，并将新首节点前指向null，后指向旧首节点
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            //如果首节点为null，说明插入的是第一个元素，则将尾节点指向最新的节点
            last = newNode;
        else
            // 将旧首节点前指向新首节点
            f.prev = newNode;
        size++;
        modCount++;
    }

• 在尾节点向后追加

    // 向后追加
    public void addLast(E e) {
        linkLast(e);
    }

    void linkLast(E e) {
       // l为旧尾节点
        final Node<E> l = last;
       // newNode为新尾节点，前指向l,后指向null
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            // l为null，说明插入的是第一个元素，赋值给first
            first = newNode;
        else
            // l旧尾节点后指向新尾节点
            l.next = newNode;
        size++;
        modCount++;
    }

• 或者在某个节点前后追加不详细赘述，和双向链表插入元素的方法相同

  // 在节点succ前追加元素e
  void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
 

2.如何读取一个元素？

    // 根据索引读取元素
     public E get(int index) {
        checkElementIndex(index);  // 确保索引不越界
        return node(index).item;
    }
    // 获取元素
    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;
        }
    }