Java基础篇--集合(上)（2）-阿里云开发者社区

System.arraycopy()和Arrays.copyOf()方法通过上面源码我们发现这两个实现数组复制的方法被广泛使用而且很多地方都特别巧妙。比如下面add(int index, E element)方法就很巧妙的用到了arraycopy()方法让数组自己复制自己实现让index开始之后的所有成员后移一个位置:

/**
     * 在此列表中的指定位置插入指定的元素。 
     *先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；
     *再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //arraycopy()方法实现数组自己复制自己
        //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组中的起始位置； size - index：要复制的数组元素的数量；
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

又如toArray()方法中用到了copyOf()方法

/**
     *以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。 
     *返回的数组将是“安全的”，因为该列表不保留对它的引用。 （换句话说，这个方法必须分配一个新的数组）。
     *因此，调用者可以自由地修改返回的数组。 此方法充当基于阵列和基于集合的API之间的桥梁。
     */
    public Object[] toArray() {
    //elementData：要复制的数组；size：要复制的长度
        return Arrays.copyOf(elementData, size);
    }

2.2.2.2 Vector集合

Vector 集合可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。不过，Vector的大小是可以增加或者减小的，以便适应创建Vector后进行添加或者删除操作。
Vector实现List接口，继承AbstractList类，所以我们可以将其看做队列，支持相关的添加、删除、修改、遍历等功能。
Vector实现RandmoAccess接口，即提供了随机访问功能，提供提供快速访问功能。在Vector我们可以直接访问元素。
Vector 实现了Cloneable接口，支持clone()方法，可以被克隆。
Vector集合初始化容量是10，每次扩容容量增加一倍，即：10–>20–>40–>80
Vector中所有方法都是线程同步的，都带有synchronized关键字，是线程安全的，效率较低，使用较少。

2.2.2.3 LinkedList集合

2.2.2.3.1 LinkList概述

LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能进行队列操作。
LinkedList 实现Deque接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。 - LinkedList 是非同步的。
ArrayList底层是由数组支持，而LinkedList是由双向链表实现的，其中的每个对象包含数据的同时还包含指向链表中前一个与后一个元素的引用。

2.2.2.3.2 LinkList常用方法与遍历

常用方法：

public E peek()：检索但不删除此列表的头（第一个元素）。
public E peekFirst()：检索但不删除此列表的第一个元素，如果此列表为空，则返回 null 。
public E peekLast()：检索但不删除此列表的最后一个元素，如果此列表为空，则返回 null 。
public E poll()：检索并删除此列表的头（第一个元素）。
public E pollFirst()：检索并删除此列表的第一个元素，如果此列表为空，则返回 null 。
public E pollLast()：检索并删除此列表的最后一个元素，如果此列表为空，则返回 null 。
public boolean offer(E e)：将指定的元素添加为此列表的尾部（最后一个元素）。
public boolean offerFirst(E e)：在此列表的前面插入指定的元素。
public boolean offerLast(E e)：在该列表的末尾插入指定的元素。

LinkList遍历方式

迭代器遍历

Iterator iterator = linkedList.iterator();   
    while(iterator.hasNext()){   
    iterator.next();   
    }

for循环get()遍历

for(int i = 0; i < linkedList.size(); i++){   
linkedList.get(i);   
}

Foreach循环遍历

for(Integer i : linkedList);

通过pollFirst()或pollLast()遍历

while(linkedList.size() != 0){   
linkedList.pollFirst();   
}

通过removeFirst()或removeLast()遍历

while(linkedList.size() != 0){   
linkedList.removeFirst();   
}

效率测试测试以上几种遍历方式的效率，部分代码如下：

/**************** 遍历操作 **************/   
System.out.println(“—————————————–”);   
linkedList.clear();   
for(int i = 0; i < 100000; i++){   
linkedList.add(i);   
}   
// 迭代器遍历   
long start = System.currentTimeMillis();   
Iterator iterator = linkedList.iterator();   
while(iterator.hasNext()){   
iterator.next();   
}   
long end = System.currentTimeMillis();   
System.out.println(“Iterator：” + (end - start) +” ms”);
// 顺序遍历(随机遍历)   
start = System.currentTimeMillis();   
for(int i = 0; i < linkedList.size(); i++){   
linkedList.get(i);   
}   
end = System.currentTimeMillis();   
System.out.println(“for：” + (end - start) +” ms”);
// 另一种for循环遍历   
start = System.currentTimeMillis();   
for(Integer i : linkedList);   
end = System.currentTimeMillis();   
System.out.println(“for2：” + (end - start) +” ms”);
// 通过pollFirst()或pollLast()来遍历LinkedList   
LinkedList temp1 = new LinkedList<>();   
temp1.addAll(linkedList);   
start = System.currentTimeMillis();   
while(temp1.size() != 0){   
temp1.pollFirst();   
}   
end = System.currentTimeMillis();   
System.out.println(“pollFirst()或pollLast()：” + (end - start) +” ms”);
// 通过removeFirst()或removeLast()来遍历LinkedList   
LinkedList temp2 = new LinkedList<>();   
temp2.addAll(linkedList);   
start = System.currentTimeMillis();   
while(temp2.size() != 0){   
temp2.removeFirst();   
}   
end = System.currentTimeMillis();   
System.out.println(“removeFirst()或removeLast()：” + (end - start) +” ms”);

输出：

Iterator：17 ms

for：8419 ms

for2：12 ms

pollFirst()或pollLast()：12 ms

removeFirst()或removeLast()：10 ms

由测试结果可以看出，遍历LinkedList时，使用removeFirst()或removeLast()效率最高，而for循环get()效率最低，应避免使用这种方式进行。应当注意的是，使用pollFirst()或pollLast()或removeFirst()或removeLast()遍历时，会删除原始数据，若只单纯的读取，应当选用第一种或第三种方式。

2.2.2.3.3 LinkList源码解析

为了更了解LinkedList的原理，下面对LinkedList源码代码作出分析。

在阅读源码之前，我们先对LinkedList的整体实现进行大致说明：

LinkedList实际上是通过双向链表去实现的。既然是双向链表，那么它的顺序访问会非常高效，而随机访问效率比较低。

既然LinkedList是通过双向链表的，但是它也实现了List接口{也就是说，它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”}。LinkedList是如何实现List的这些接口的，如何将“双向链表和索引值联系起来的”？

实际原理非常简单，它就是通过一个计数索引值来实现的。例如，当我们调用get(int location)时，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置。

这就是“双线链表和索引值联系起来”的方法。

好了，接下来开始阅读源码(只要理解双向链表，那么LinkedList的源码很容易理解的)。

package java.util;
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 链表的表头，表头不包含任何数据。Entry是个链表类数据结构。
    private transient Entry<E> header = new Entry<E>(null, null, null);
    // LinkedList中元素个数
    private transient int size = 0;
    // 默认构造函数：创建一个空的链表
    public LinkedList() {
        header.next = header.previous = header;
    }
    // 包含“集合”的构造函数:创建一个包含“集合”的LinkedList
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    // 获取LinkedList的第一个元素
    public E getFirst() {
        if (size==0)
            throw new NoSuchElementException();
        // 链表的表头header中不包含数据。
        // 这里返回header所指下一个节点所包含的数据。
        return header.next.element;
    }
    // 获取LinkedList的最后一个元素
    public E getLast()  {
        if (size==0)
            throw new NoSuchElementException();
        // 由于LinkedList是双向链表；而表头header不包含数据。
        // 因而，这里返回表头header的前一个节点所包含的数据。
        return header.previous.element;
    }
    // 删除LinkedList的第一个元素
    public E removeFirst() {
        return remove(header.next);
    }
    // 删除LinkedList的最后一个元素
    public E removeLast() {
        return remove(header.previous);
    }
    // 将元素添加到LinkedList的起始位置
    public void addFirst(E e) {
        addBefore(e, header.next);
    }
    // 将元素添加到LinkedList的结束位置
    public void addLast(E e) {
        addBefore(e, header);
    }
    // 判断LinkedList是否包含元素(o)
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }
    // 返回LinkedList的大小
    public int size() {
        return size;
    }
    // 将元素(E)添加到LinkedList中
    public boolean add(E e) {
        // 将节点(节点数据是e)添加到表头(header)之前。
        // 即，将节点添加到双向链表的末端。
        addBefore(e, header);
        return true;
    }
    // 从LinkedList中删除元素(o)
    // 从链表开始查找，如存在元素(o)则删除该元素并返回true；
    // 否则，返回false。
    public boolean remove(Object o) {
        if (o==null) {
            // 若o为null的删除情况
            for (Entry<E> e = header.next; e != header; e = e.next) {
                if (e.element==null) {
                    remove(e);
                    return true;
                }
            }
        } else {
            // 若o不为null的删除情况
            for (Entry<E> e = header.next; e != header; e = e.next) {
                if (o.equals(e.element)) {
                    remove(e);
                    return true;
                }
            }
        }
        return false;
    }
    // 将“集合(c)”添加到LinkedList中。
    // 实际上，是从双向链表的末尾开始，将“集合(c)”添加到双向链表中。
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    // 从双向链表的index开始，将“集合(c)”添加到双向链表中。
    public boolean addAll(int index, Collection<? extends E> c) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Object[] a = c.toArray();
        // 获取集合的长度
        int numNew = a.length;
        if (numNew==0)
            return false;
        modCount++;
        // 设置“当前要插入节点的后一个节点”
        Entry<E> successor = (index==size ? header : entry(index));
        // 设置“当前要插入节点的前一个节点”
        Entry<E> predecessor = successor.previous;
        // 将集合(c)全部插入双向链表中
        for (int i=0; i<numNew; i++) {
            Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
            predecessor.next = e;
            predecessor = e;
        }
        successor.previous = predecessor;
        // 调整LinkedList的实际大小
        size += numNew;
        return true;
    }
    // 清空双向链表
    public void clear() {
        Entry<E> e = header.next;
        // 从表头开始，逐个向后遍历；对遍历到的节点执行一下操作：
        // (01) 设置前一个节点为null 
        // (02) 设置当前节点的内容为null 
        // (03) 设置后一个节点为“新的当前节点”
        while (e != header) {
            Entry<E> next = e.next;
            e.next = e.previous = null;
            e.element = null;
            e = next;
        }
        header.next = header.previous = header;
        // 设置大小为0
        size = 0;
        modCount++;
    }
    // 返回LinkedList指定位置的元素
    public E get(int index) {
        return entry(index).element;
    }
    // 设置index位置对应的节点的值为element
    public E set(int index, E element) {
        Entry<E> e = entry(index);
        E oldVal = e.element;
        e.element = element;
        return oldVal;
    }
    // 在index前添加节点，且节点的值为element
    public void add(int index, E element) {
        addBefore(element, (index==size ? header : entry(index)));
    }
    // 删除index位置的节点
    public E remove(int index) {
        return remove(entry(index));
    }
    // 获取双向链表中指定位置的节点
    private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> e = header;
        // 获取index处的节点。
        // 若index < 双向链表长度的1/2,则从前先后查找;
        // 否则，从后向前查找。
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }
    // 从前向后查找，返回“值为对象(o)的节点对应的索引”
    // 不存在就返回-1
    public int indexOf(Object o) {
        int index = 0;
        if (o==null) {
            for (Entry e = header.next; e != header; e = e.next) {
                if (e.element==null)
                    return index;
                index++;
            }
        } else {
            for (Entry e = header.next; e != header; e = e.next) {
                if (o.equals(e.element))
                    return index;
                index++;
            }
        }
        return -1;
    }
    // 从后向前查找，返回“值为对象(o)的节点对应的索引”
    // 不存在就返回-1
    public int lastIndexOf(Object o) {
        int index = size;
        if (o==null) {
            for (Entry e = header.previous; e != header; e = e.previous) {
                index--;
                if (e.element==null)
                    return index;
            }
        } else {
            for (Entry e = header.previous; e != header; e = e.previous) {
                index--;
                if (o.equals(e.element))
                    return index;
            }
        }
        return -1;
    }
    // 返回第一个节点
    // 若LinkedList的大小为0,则返回null
    public E peek() {
        if (size==0)
            return null;
        return getFirst();
    }
    // 返回第一个节点
    // 若LinkedList的大小为0,则抛出异常
    public E element() {
        return getFirst();
    }
    // 删除并返回第一个节点
    // 若LinkedList的大小为0,则返回null
    public E poll() {
        if (size==0)
            return null;
        return removeFirst();
    }
    // 将e添加双向链表末尾
    public boolean offer(E e) {
        return add(e);
    }
    // 将e添加双向链表开头
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }
    // 将e添加双向链表末尾
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }
    // 返回第一个节点
    // 若LinkedList的大小为0,则返回null
    public E peekFirst() {
        if (size==0)
            return null;
        return getFirst();
    }
    // 返回最后一个节点
    // 若LinkedList的大小为0,则返回null
    public E peekLast() {
        if (size==0)
            return null;
        return getLast();
    }
    // 删除并返回第一个节点
    // 若LinkedList的大小为0,则返回null
    public E pollFirst() {
        if (size==0)
            return null;
        return removeFirst();
    }
    // 删除并返回最后一个节点
    // 若LinkedList的大小为0,则返回null
    public E pollLast() {
        if (size==0)
            return null;
        return removeLast();
    }
    // 将e插入到双向链表开头
    public void push(E e) {
        addFirst(e);
    }
    // 删除并返回第一个节点
    public E pop() {
        return removeFirst();
    }
    // 从LinkedList开始向后查找，删除第一个值为元素(o)的节点
    // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点
    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }
    // 从LinkedList末尾向前查找，删除第一个值为元素(o)的节点
    // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点
    public boolean removeLastOccurrence(Object o) {
        if (o==null) {
            for (Entry<E> e = header.previous; e != header; e = e.previous) {
                if (e.element==null) {
                    remove(e);
                    return true;
                }
            }
        } else {
            for (Entry<E> e = header.previous; e != header; e = e.previous) {
                if (o.equals(e.element)) {
                    remove(e);
                    return true;
                }
            }
        }
        return false;
    }
    // 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)
    public ListIterator<E> listIterator(int index) {
        return new ListItr(index);
    }
    // List迭代器
    private class ListItr implements ListIterator<E> {
        // 上一次返回的节点
        private Entry<E> lastReturned = header;
        // 下一个节点
        private Entry<E> next;
        // 下一个节点对应的索引值
        private int nextIndex;
        // 期望的改变计数。用来实现fail-fast机制。
        private int expectedModCount = modCount;
        // 构造函数。
        // 从index位置开始进行迭代
        ListItr(int index) {
            // index的有效性处理
            if (index < 0 || index > size)
                throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
            // 若 “index 小于 ‘双向链表长度的一半’”，则从第一个元素开始往后查找；
            // 否则，从最后一个元素往前查找。
            if (index < (size >> 1)) {
                next = header.next;
                for (nextIndex=0; nextIndex<index; nextIndex++)
                    next = next.next;
            } else {
                next = header;
                for (nextIndex=size; nextIndex>index; nextIndex--)
                    next = next.previous;
            }
        }
        // 是否存在下一个元素
        public boolean hasNext() {
            // 通过元素索引是否等于“双向链表大小”来判断是否达到最后。
            return nextIndex != size;
        }
        // 获取下一个元素
        public E next() {
            checkForComodification();
            if (nextIndex == size)
                throw new NoSuchElementException();
            lastReturned = next;
            // next指向链表的下一个元素
            next = next.next;
            nextIndex++;
            return lastReturned.element;
        }
        // 是否存在上一个元素
        public boolean hasPrevious() {
            // 通过元素索引是否等于0，来判断是否达到开头。
            return nextIndex != 0;
        }
        // 获取上一个元素
        public E previous() {
            if (nextIndex == 0)
            throw new NoSuchElementException();
            // next指向链表的上一个元素
            lastReturned = next = next.previous;
            nextIndex--;
            checkForComodification();
            return lastReturned.element;
        }
        // 获取下一个元素的索引
        public int nextIndex() {
            return nextIndex;
        }
        // 获取上一个元素的索引
        public int previousIndex() {
            return nextIndex-1;
        }
        // 删除当前元素。
        // 删除双向链表中的当前节点
        public void remove() {
            checkForComodification();
            Entry<E> lastNext = lastReturned.next;
            try {
                LinkedList.this.remove(lastReturned);
            } catch (NoSuchElementException e) {
                throw new IllegalStateException();
            }
            if (next==lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = header;
            expectedModCount++;
        }
        // 设置当前节点为e
        public void set(E e) {
            if (lastReturned == header)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.element = e;
        }
        // 将e添加到当前节点的前面
        public void add(E e) {
            checkForComodification();
            lastReturned = header;
            addBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }
        // 判断 “modCount和expectedModCount是否相等”，依次来实现fail-fast机制。
        final void checkForComodification() {
            if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        }
    }
    // 双向链表的节点所对应的数据结构。
    // 包含3部分：上一节点，下一节点，当前节点值。
    private static class Entry<E> {
        // 当前节点所包含的值
        E element;
        // 下一个节点
        Entry<E> next;
        // 上一个节点
        Entry<E> previous;
        /**
         * 链表节点的构造函数。
         * 参数说明：
         *   element  —— 节点所包含的数据
         *   next      —— 下一个节点
         *   previous —— 上一个节点
         */
        Entry(E element, Entry<E> next, Entry<E> previous) {
            this.element = element;
            this.next = next;
            this.previous = previous;
        }
    }
    // 将节点(节点数据是e)添加到entry节点之前。
    private Entry<E> addBefore(E e, Entry<E> entry) {
        // 新建节点newEntry，将newEntry插入到节点e之前；并且设置newEntry的数据是e
        Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
        newEntry.previous.next = newEntry;
        newEntry.next.previous = newEntry;
        // 修改LinkedList大小
        size++;
        // 修改LinkedList的修改统计数：用来实现fail-fast机制。
        modCount++;
        return newEntry;
    }
    // 将节点从链表中删除
    private E remove(Entry<E> e) {
        if (e == header)
            throw new NoSuchElementException();
        E result = e.element;
        e.previous.next = e.next;
        e.next.previous = e.previous;
        e.next = e.previous = null;
        e.element = null;
        size--;
        modCount++;
        return result;
    }
    // 反向迭代器
    public Iterator<E> descendingIterator() {
        return new DescendingIterator();
    }
    // 反向迭代器实现类。
    private class DescendingIterator implements Iterator {
        final ListItr itr = new ListItr(size());
        // 反向迭代器是否下一个元素。
        // 实际上是判断双向链表的当前节点是否达到开头
        public boolean hasNext() {
            return itr.hasPrevious();
        }
        // 反向迭代器获取下一个元素。
        // 实际上是获取双向链表的前一个节点
        public E next() {
            return itr.previous();
        }
        // 删除当前节点
        public void remove() {
            itr.remove();
        }
    }
    // 返回LinkedList的Object[]数组
    public Object[] toArray() {
    // 新建Object[]数组
    Object[] result = new Object[size];
        int i = 0;
        // 将链表中所有节点的数据都添加到Object[]数组中
        for (Entry<E> e = header.next; e != header; e = e.next)
            result[i++] = e.element;
    return result;
    }
    // 返回LinkedList的模板数组。所谓模板数组，即可以将T设为任意的数据类型
    public <T> T[] toArray(T[] a) {
        // 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)
        // 则新建一个T[]数组，T[]的大小为LinkedList大小，并将该T[]赋值给a。
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);
        // 将链表中所有节点的数据都添加到数组a中
        int i = 0;
        Object[] result = a;
        for (Entry<E> e = header.next; e != header; e = e.next)
            result[i++] = e.element;
        if (a.length > size)
            a[size] = null;
        return a;
    }
    // 克隆函数。返回LinkedList的克隆对象。
    public Object clone() {
        LinkedList<E> clone = null;
        // 克隆一个LinkedList克隆对象
        try {
            clone = (LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
        // 新建LinkedList表头节点
        clone.header = new Entry<E>(null, null, null);
        clone.header.next = clone.header.previous = clone.header;
        clone.size = 0;
        clone.modCount = 0;
        // 将链表中所有节点的数据都添加到克隆对象中
        for (Entry<E> e = header.next; e != header; e = e.next)
            clone.add(e.element);
        return clone;
    }
    // java.io.Serializable的写入函数
    // 将LinkedList的“容量，所有的元素值”都写入到输出流中
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();
        // 写入“容量”
        s.writeInt(size);
        // 将链表中所有节点的数据都写入到输出流中
        for (Entry e = header.next; e != header; e = e.next)
            s.writeObject(e.element);
    }
    // java.io.Serializable的读取函数：根据写入方式反向读出
    // 先将LinkedList的“容量”读出，然后将“所有的元素值”读出
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();
        // 从输入流中读取“容量”
        int size = s.readInt();
        // 新建链表表头节点
        header = new Entry<E>(null, null, null);
        header.next = header.previous = header;
        // 从输入流中将“所有的元素值”并逐个添加到链表中
        for (int i=0; i<size; i++)
            addBefore((E)s.readObject(), header);
    }
}

LinkedList 实际上是通过双向链表去实现的。
它包含一个非常重要的内部类：Entry。Entry是双向链表节点所对应的数据结构，它包括的属性有：当前节点所包含的值，上一个节点，下一个节点。
从LinkedList的实现方式中可以发现，它不存在LinkedList容量不足的问题。
LinkedList的克隆函数，即是将全部元素克隆到一个新的LinkedList对象中。
LinkedList实现java.io.Serializable。当写入到输出流时，先写入“容量”，再依次写入“每一个节点保护的值”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
由于LinkedList实现了Deque，而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。
总结起来如下表格：

第一个元素（头部）                 最后一个元素（尾部）
        抛出异常        特殊值            抛出异常           特殊值
插入    addFirst(e)    offerFirst(e)    addLast(e)        offerLast(e)
移除    removeFirst()  pollFirst()      removeLast()      pollLast()
检查    getFirst()     peekFirst()      getLast()         peekLast()

LinkedList可以作为FIFO(先进先出)的队列，作为FIFO的队列时，下表的方法等价：

队列方法       等效方法
add(e)        addLast(e)
offer(e)      offerLast(e)
remove()      removeFirst()
poll()        pollFirst()
element()     getFirst()
peek()        peekFirst()

7.LinkedList可以作为LIFO(后进先出)的栈，作为LIFO的栈时，下表的方法等价：

栈方法        等效方法
push(e)      addFirst(e)
pop()        removeFirst()
peek()       peekFirst()

无论如何，千万不要通过随机访问去遍历LinkedList！

2.2.2.3.4 LinkedList示例

import java.util.LinkedList;
/*
 * @desc LinkedList测试程序。
 */
public class LinkedListTest {
    public static void main(String[] args) {
        // 测试LinkedList的API
        testLinkedListAPIs();
        // 将LinkedList当作 LIFO(后进先出)的堆栈
        useLinkedListAsLIFO();
        // 将LinkedList当作 FIFO(先进先出)的队列
        useLinkedListAsFIFO();
    }
    /**
     * 将LinkedList当作 FIFO(先进先出)的队列
     */
    private static void useLinkedListAsFIFO() {
        System.out.println("\nuseLinkedListAsFIFO");
        // 新建一个LinkedList
        LinkedList queue = new LinkedList();
        // 将10,20,30,40添加到队列。每次都是插入到末尾
        queue.add("10");
        queue.add("20");
        queue.add("30");
        queue.add("40");
        // 打印“队列”
        System.out.println("queue:" + queue);
        // 删除(队列的第一个元素)
        System.out.println("queue.remove():" + queue.remove());
        // 读取(队列的第一个元素)
        System.out.println("queue.element():" + queue.element());
        // 打印“队列”
        System.out.println("queue:" + queue);
    }
    /**
     * 将LinkedList当作 LIFO(后进先出)的堆栈
     */
    private static void useLinkedListAsLIFO() {
        System.out.println("\nuseLinkedListAsLIFO");
        // 新建一个LinkedList
        LinkedList stack = new LinkedList();
        // 将1,2,3,4添加到堆栈中
        stack.push("1");
        stack.push("2");
        stack.push("3");
        stack.push("4");
        // 打印“栈”
        System.out.println("stack:" + stack);
        // 删除“栈顶元素”
        System.out.println("stack.pop():" + stack.pop());
        // 取出“栈顶元素”
        System.out.println("stack.peek():" + stack.peek());
        // 打印“栈”
        System.out.println("stack:" + stack);
    }
    /*
     * 测试LinkedList中部分API
     */
    private static void testLinkedListAPIs() {
        String val = null;
        //LinkedList llist;
        //llist.offer("10");
        // 新建一个LinkedList
        LinkedList llist = new LinkedList();
        //---- 添加操作 ----
        // 依次添加1,2,3
        llist.add("1");
        llist.add("2");
        llist.add("3");
        // 将“4”添加到第一个位置
        llist.add(1, "4");
        System.out.println("\nTest ", llist.addFirst("10"), llist.removeFirst(), llist.getFirst()"");
        // (01) 将“10”添加到第一个位置。  失败的话，抛出异常！
        llist.addFirst("10");
        System.out.println("llist:" + llist);
        // (02) 将第一个元素删除。        失败的话，抛出异常！
        System.out.println("llist.removeFirst():" + llist.removeFirst());
        System.out.println("llist:" + llist);
        // (03) 获取第一个元素。          失败的话，抛出异常！
        System.out.println("llist.getFirst():" + llist.getFirst());
        //System.out.println("\nTest ",llist.offerFirst( ), pollFirst(), peekFirst()+"");
        // (01) 将“10”添加到第一个位置。  返回true。
        llist.offerFirst("10");
        System.out.println("llist:" + llist);
        // (02) 将第一个元素删除。        失败的话，返回null。
        System.out.println("llist.pollFirst():" + llist.pollFirst());
        System.out.println("llist:" + llist);
        // (03) 获取第一个元素。          失败的话，返回null。
        System.out.println("llist.peekFirst():" + llist.peekFirst());
        //System.out.println("\nTest "addLast(), removeLast(), getLast()"");
        // (01) 将“20”添加到最后一个位置。  失败的话，抛出异常！
        llist.addLast("20");
        System.out.println("llist:" + llist);
        // (02) 将最后一个元素删除。        失败的话，抛出异常！
        System.out.println("llist.removeLast():" + llist.removeLast());
        System.out.println("llist:" + llist);
        // (03) 获取最后一个元素。          失败的话，抛出异常！
        System.out.println("llist.getLast():" + llist.getLast());
        //System.out.println("\nTest "offerLast(), pollLast(), peekLast()"");
        // (01) 将“20”添加到第一个位置。  返回true。
        llist.offerLast("20");
        System.out.println("llist:" + llist);
        // (02) 将第一个元素删除。        失败的话，返回null。
        System.out.println("llist.pollLast():" + llist.pollLast());
        System.out.println("llist:" + llist);
        // (03) 获取第一个元素。          失败的话，返回null。
        System.out.println("llist.peekLast():" + llist.peekLast());
        // 将第3个元素设置300。不建议在LinkedList中使用此操作，因为效率低！
        llist.set(2, "300");
        // 获取第3个元素。不建议在LinkedList中使用此操作，因为效率低！
        System.out.println("\nget(3):" + llist.get(2));
        // ---- toArray(T[] a) ----
        // 将LinkedList转行为数组
        String[] arr = (String[]) llist.toArray(new String[0]);
        for (String str : arr) {
            System.out.println("str:" + str);
            // 输出大小
            System.out.println("size:" + llist.size());
            // 清空LinkedList
            llist.clear();
            // 判断LinkedList是否为空
            System.out.println("isEmpty():" + llist.isEmpty() + "\n");
        }
    }
}

2.2.2.4 List集合相关的面试题

ArrayList中的操作不是线程安全的吗？

ArrayList中的操作不是线程安全的！所以，建议在单线程中使用，多线程情况下可以选择CopyOnWriteArrayList或者使用Collections中的synchronizedList方法将其包装成一个线程安全的List。

ArrayList、Vector、Linklist集合的异同点相同点：

Vector、ArrayList和LinkedList都是List的接口的实现类，所以它们三个都有List集合身上的特点.List是有序的(元素存入集合的顺序和取出的顺序一致).ArrayList和Vector都是基于动态的Object数组，他们两个的底层实现其实是类似的。

不同点：

ArrayList类主要是实现类，虽然效率高，但是线程不安全。底层用的是Object[]数组存储。从查找的时间复杂度来说它属于O(I)。删除元素的时间复杂度O(n)。
LinkedList类主要是用于频繁插入，删除操作，当然它的效率比ArrayList高，所以它的线程安全程度比ArrayList更低，底层使用的是双向链表存储。从查找的时间复杂度来说属于O(n)。插入删除的时间复杂度属于O(I)。
Vector属于比较古老的一种类，效率比较低，反之线程比较安全，底层使用的是Object[]数组存储。
ArrayList和Vector，两个其中ArrayList是非线程安全的而Vector是线程安全的，但是ArrayList的效率比Vector快的多，并且我们一般常用的都ArrayList，而出现多线程时我们采用Vector， ArrayList的add方法的扩容原理是扩为原来的1.5倍而Vector则是扩为原来的2倍。
ArrayList和LinkedList相比，ArrayList是动态基于动态的Object数组而LinkedList是链表，ArrayList在指定增加位置、删除和修改没有LinkedList快，在指定位置增加时候很麻烦需要先判断数组是否已满，如果满了还要扩容，然后将指点位置的元素和它后面的元素全部往后移一位，而LinkedList则直接将指定位置的链表断开将元素插入让指针指向对应的地方则可以，删除和修改ArrayList也可能要涉及到元素移动问题除非是最后一位，而LinkedList因为是链表则不涉及这个问题。但是ArrayList的查找速度比LinkedList快，因为ArrayList是连续的内存而LinkedList因为是链表所以它是连续的内存块。 ArrayList：数组实现，查询快，增删慢，轻量级；(线程不安全)
LinkedList：双向链表实现，增删快，查询慢 (线程不安全)
底层是一种双向循环链表。在此链表上每一个数据节点都由三部分组成：前指针（指向前面的节点的位置），数据，后指针（指向后面的节点的位置）。最后一个节点的后指针指向第一个节点的前指针，形成一个循环。

双向循环链表的查询效率低但是增删效率高。

Vector和LinkedList 第一个不同就是Vector是线程安全的而LinkedList是非线程安全的因为Vector和ArrayList底层实现基本类似，所以增删改上ArrayList有的问题Vector也有，并且Vector的查找速度也是比LinkedList快因为他也是连续的内存。

2.2.3 Set

HashSet

HashSet常用方法: public boolean contains(Object o) ：如果set包含指定元素，返回true

public Iterator iterator()返回set中元素的迭代器

public Object[] toArray() ：返回包含set中所有元素的数组public Object[] toArray(Object[] a) ：返回包含set中所有元素的数组，返回数组的运行时类型是指定数组的运行时类型

public boolean add(Object o) ：如果set中不存在指定元素，则向set加入

public boolean remove(Object o) ：如果set中存在指定元素，则从set中删除

public boolean removeAll(Collection c) ：如果set包含指定集合，则从set中删除指定集合的所有元素

public boolean containsAll(Collection c) ：如果set包含指定集合的所有元素，返回true。如果指定集合也是一个set，只有是当前set的子集时，方法返回true 实现Set接口的HashSet，依靠HashMap来实现的。我们应该为要存放到散列表的各个对象定义hashCode()和equals()。

LinkedHashSet

TreeSet

扩展Collection接口

无序集合，不允许存放重复的元素；

允许使用null元素

对 add()、equals() 和 hashCode() 方法添加了限制

HashSet和TreeSet是Set的实现 Set -->hashSet-->linkedHashSet SortedSet TreeSet HashSet 的后台有一个HashMap; 初始化后台容量；只不过生成一个HashSet的话，系统只提供key的访问；如果有两个Key重复，那么会覆盖之前的；实现类 : HashSet：equals返回true，hashCode返回相同的整数；哈希表；存储的数据是无序的。

LinkedHashSet：此实现与HashSet的不同之外在于，后者维护着一个运行于所有条目的双重链接列表。存储的数据是有序的。 HashSet类 HashSet类直接实现了Set接口，其底层其实是包装了一个HashMap去实现的。HashSet采用HashCode算法来存取集合中的元素，因此具有比较好的读取和查找性能。 HashSet的特征: 不仅不能保证元素插入的顺序，而且在元素在以后的顺序中也可能变化（这是由HashSet按HashCode存储对象（元素）决定的，对象变化则可能导致HashCode变化） **HashSet是线程非安全的

**HashSet元素值可以为NULL

HashSet的equals和HashCode：

前面说过，Set集合是不允许重复元素的，否则将会引发各种奇怪的问题。那么HashSet如何判断元素重复呢？

HashSet需要同时通过equals和HashCode来判断两个元素是否相等，具体规则是，如果两个元素通过equals为true，并且两个元素的hashCode相等，则这两个元素相等（即重复）。

所以如果要重写保存在HashSet中的对象的equals方法，也要重写hashCode方法，重写前后hashCode返回的结果相等（即保证保存在同一个位置）。所有参与计算 hashCode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。

试想如果重写了equals方法但不重写hashCode方法，即相同equals结果的两个对象将会被HashSet当作两个元素保存起来，这与我们设计HashSet的初衷不符（元素不重复）。

另外如果两个元素哈市Code相等但equals结果不为true，HashSet会将这两个元素保存在同一个位置，并将超过一个的元素以链表方式保存，这将影响HashSet的效率。

如果重写了equals方法但没有重写hashCode方法，则HashSet可能无法正常工作，比如下面的例子。

LinkedHashSet的特征

LinkedHashSet是HashSet的一个子类，LinkedHashSet也根据HashCode的值来决定元素的存储位置，但同时它还用一个链表来维护元素的插入顺序，插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素。查看LinkedHashSet的源码发现它是样的

各种Set集合性能分析

HashSet和TreeSet是Set集合中用得最多的I集合。HashSet总是比TreeSet集合性能好，因为HashSet不需要额维护元素的顺序。 LinkedHashSet需要用额外的链表维护元素的插入顺序，因此在插入时性能比HashSet低，但在迭代访问（遍历）时性能更高。因为插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素。 EnumSet元素是所有Set元素中性能最好的，但是它只能保存Enum类型的元素

Java基础篇--集合(上)（2）

2.2.2.2 Vector集合

2.2.2.3 LinkedList集合

2.2.2.3.1 LinkList概述

2.2.2.3.2 LinkList常用方法与遍历

2.2.2.3.3 LinkList源码解析

2.2.2.3.4 LinkedList示例

2.2.2.4 List集合相关的面试题

2.2.3 Set

HashSet

LinkedHashSet

TreeSet

热门文章

最新文章

相关课程

相关电子书

相关实验场景