java集合类学习笔记之LinkList

学习编程

2017-12-12

关注关注

1、简述

LinkList的底层其实就是一个双向链表，所谓的链表就是一个LinkList内部静态静态类（Node），对LinkList的所有操作本质上就是通过对LinkList中新建的Node对象

进行关联引用

2、实现

a、构造方法：

LinkList一共提供了两种构造方法：

/**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

b、定义内部私有属性

transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

LinkList的内部属性只有三个，一个是LinkList的长度，另外两个分别是第一个节点和最后一个节点，每次对LinkList进行更新操作之后，第一个节点和最后一个节点的值都会进行相应的变化。

3、LinkList操作

增加操作：

add(E e)：

/**
     * Appends the specified element to the end of this list.
     *
     * <p>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(E e)操作LinkList的时候先new一个Node对象，并设置该节点的上一个元素为之前的最后一个节点，然后再将之前最后一个节点的next

属性指向新建的节点

add(int index, E element)：

/**
     * 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));
    }
 /**
     * Inserts element e before non-null Node succ.
     */
    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++;
    }

调用add(int index, E element)操作的时候和add（E element）方法是一样的，就是通过改变index位置节点的中的next和prev属性的值，再将新创建的

节点的next指向原来index位置的节点

LinkList的删除更新操作本质其实就是通过对内部节点的next和prev属行引用的值进行改变，所以在这里就不再对那些操作一一叙述了