Java集合学习--LinkedList

一、ArrayList 定义

ArrayList 是一个用双向链表实现的集合，支持随机访问，元素有序且可以重复。同样是非线程安全的，只在单线程下适合使用。

①、实现 List 接口

List接口继承Collection接口，是List类的顶层接口，定义了大量方法，子类可进行个性化实现

②、继承AbstractSequentialList类，是一个抽象类， List接口的简化版实现，AbstractSequentialList 支持按次序访问，想要实现一个支持按次序访问的 List的话，只需要继承这个抽象类，然后把指定的抽象方法实现。

特别需要注意的：AbstractSequentialList 把父类AbstractList中没有实现或者没有支持的操作都实现了，而且都是调用ListIterator相关方法进行操作。AbstractSequentialList 只支持迭代器按顺序 访问，不支持 RandomAccess，所以遍历 AbstractSequentialList 的子类，使用 for 循环 get() 的效率要 <= 迭代器遍历

 ③、实现 Cloneable 接口和Serializable接口，与ArrayList一样，支持克隆与序列化。

④、实现Deque接口，一个双向队列接口，双向队列就是支持队列的两端都可以进行增加和删除操作。

二、字段属性

//链表节点个数
transient int size = 0;
//链表的首节点
transient Node<E> first;
//链表的尾节点
transient Node<E> last;

节点类Node:是 LinkedList 类中的一个内部类，集合中的每一个元素都可以用一个 Node 实例对象表示，LinkedList 集合就是由许多个 Node 类实例对象构成。结构如下：

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.无参构造器，不必初始化链表的大小，链表没有大小限制，通过指针的移动来指向下一个内存地址的分配

public LinkedList() {
}

2.有参构造器，参数是一个集合，最终通过迭代集合，将集合中元素加入链表中。

public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
}

四、主要方法

1.添加元素，分为首部添加和尾部添加，add()默认是添加在链表的尾部。

public boolean add(E e) {
        linkLast(e);
        return true;
}

①、addFirst(E e)，具体如下：

//将指定的元素附加到链表头节点
    public void addFirst(E e) {
        linkFirst(e);
    }
    private void linkFirst(E e) {
        final Node<E> f = first;//将头节点赋值给 f
        final Node<E> newNode = new Node<>(null, e, f);//将指定元素构造成一个新节点，此节点的指向下一个节点的引用为头节点
        first = newNode;//将新节点设为头节点，那么原先的头节点 f 变为第二个节点
        if (f == null)//如果第二个节点为空，也就是原先链表是空
            last = newNode;//将这个新节点也设为尾节点（前面已经设为头节点了）
        else
            f.prev = newNode;//将原先的头节点的上一个节点指向新节点
        size++;//节点数加1
        modCount++;//和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
    }

②、addLast(E e)，具体如下：

//将元素添加在链表的尾部
public void addLast(E e) {
        linkLast(e);
}

void linkLast(E e) {
        final Node<E> l = last;//将l指向尾节点
        final Node<E> newNode = new Node<>(l, e, null);//构建一个新的节点，封装添加的元素，并且新节点的前继指向添加尾节点
        last = newNode;//修改尾节点为当前新增的节点
        if (l == null)//如果尾节点为空，表示原先链表为空
            first = newNode;//新节点为首节点，同时也是尾节点
        else
            l.next = newNode;
        size++;//链表个数+1
        modCount++;//链表的修改次数+1
    }

③、add(int index, E element)，在指定索引的位置加入指定元素。

public void add(int index, E element) {
        checkPositionIndex(index);//判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常

        if (index == size)
            linkLast(element);//如果给定的索引位置与链表大小一致，表示插入链表的尾部
        else
            linkBefore(element, node(index));//确定索引的位置后添加元素
}

//通过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;//最终找到索引对应的Node节点
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

最终将节点插入到链表的指定位置，原理就是数据结构中链表的插入。

2.删除元素，分为删除头部元素，尾部元素和指定元素。

①、remove()和removeFirst()，remove()默认删除链表头部元素。

　　//从此链表中移除并返回第一个元素
    public E remove() {
        return removeFirst();
    }
    //从此列表中移除并返回第一个元素
    public E removeFirst() {
        final Node<E> f = first;//f指向头结点
        if (f == null)
            throw new NoSuchElementException();//如果头结点为空，则抛出异常
        return unlinkFirst(f);
    }
    private E unlinkFirst(Node<E> f) {
        final E element = f.item;
        final Node<E> next = f.next;//next 为头结点的下一个节点
        f.item = null;
        f.next = null; // 将节点的元素以及引用都设为 null，便于垃圾回收
        first = next; //修改头结点为第二个节点
        if (next == null)//如果第二个节点为空（当前链表只存在第一个元素）
            last = null;//那么尾节点也置为 null
        else
            next.prev = null;//如果第二个节点不为空，那么将第二个节点的上一个引用置为 null
        size--;
        modCount++;
        return element;
    }

②、removeLast(),删除链表尾节点，并返回元素值，原理类似上面删除头节点

③、remove(int index)，删除指定位置的节点，首先检查索引是否超过链表大小，或小于0，找到指定位置后删除节点并返回元素值。

    //删除此链表中指定位置的元素
    public E remove(int index) {
        //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常
        checkElementIndex(index);
        return unlink(node(index));
    }
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {//如果删除节点位置的上一个节点引用为null（表示删除第一个元素）
            first = next;//将头结点置为第一个元素的下一个节点
        } else {//如果删除节点位置的上一个节点引用不为null
            prev.next = next;//将删除节点的上一个节点的下一个节点引用指向删除节点的下一个节点（去掉删除节点）
            x.prev = null;//删除节点的上一个节点引用置为null
        }

        if (next == null) {//如果删除节点的下一个节点引用为null（表示删除最后一个节点）
            last = prev;//将尾节点置为删除节点的上一个节点
        } else {//不是删除尾节点
            next.prev = prev;//将删除节点的下一个节点的上一个节点的引用指向删除节点的上一个节点
            x.next = null;//将删除节点的下一个节点引用置为null
        }

        x.item = null;//删除节点内容置为null，便于垃圾回收
        size--;
        modCount++;
        return element;
    }

④、remove(Object o)，原理类似删除指定位置的元素，这里只不过是通过循环的方式找到第一个符合要求的元素节点后，删除节点，并返回值。

public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
}

3.查找元素

①、get(int index),通过索引查找指定位置的元素

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

②、getLast()和getFirst(),获取头结点元素值和尾节点封装的元素值。原理非常简单，直接通过指向Node对象的引用获取即可

 public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
  }

③indexOf(Object o)，返回指定元素在链表中首次出现的位置，如果object部位null,从头部开始遍历

//返回此列表中指定元素第一次出现的索引，如果此列表不包含元素，则返回-1。
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {//如果查找的元素为null(LinkedList可以允许null值)
            for (Node<E> x = first; x != null; x = x.next) {//从头结点开始不断向下一个节点进行遍历
                if (x.item == null)
                    return index;
                index++;
            }
        } else {//如果查找的元素不为null
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;//找不到返回-1
    }

4.修改元素，set(int index, E element) ，主要是修改指定位置的元素值，原理即先找到指定位置后替换值即可

public E set(int index, E element) {
        //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常
        checkElementIndex(index);
        Node<E> x = node(index);//获取指定索引处的元素
        E oldVal = x.item;
        x.item = element;//将指定位置的元素替换成要修改的元素
        return oldVal;//返回指定索引位置原来的元素
}

5.遍历元素

①、普通 for 循环，通过循环，再借助get(int index),通过索引查找指定位置的元素，LinkedList集合的遍历，一般不推荐这种方案，效率不好

②、通过迭代器遍历

public Iterator<E> iterator() {
        return listIterator();
}

-----------------------------------------------------------
public ListIterator<E> listIterator() {
        return listIterator(0);
}

-----------------------------------------------------------
public ListIterator<E> listIterator(final int index) {
        rangeCheckForAdd(index);

        return new ListItr(index);
}

迭代器最终返回的ListItr实例，这个类的实现如下：

 private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public E previous() {
            checkForComodification();
            try {
                int i = cursor - 1;
                E previous = get(i);
                lastRet = cursor = i;
                return previous;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor-1;
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                AbstractList.this.add(i, e);
                lastRet = -1;
                cursor = i + 1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

五、总结

• LinkedList基于双向链表结构实现
• 在查找和删除某元素时，源码中都划分为该元素为null和不为null两种情况来处理，LinkedList中允许元素为null。
• LinkedList是基于链表，在内存足够的情况下，不存在容量与扩容的问题
• LinkedList通过索引查找元素，存在一个提速动作，以二分的思想确定差查找的方向是头部开始还是尾部开始
• LinkedList是基于链表实现的，因此插入删除效率高，查找效率低
• LinkedList非线程安全，可以作为栈，对列以及双端队列来使用