java集合类 -- List接口

List接口简介

　　List接口继承自Collection接口，是单列集合的一个重要分支，习惯性会将实现了List接口的对象成为List集合。在List集合中允许出现重复的元素，所有的元素是以一种线性方式进行储存的，在程序中可以通过索引来访问集合中的指定元素。另外，List集合还有一个特点就是元素有序，即元素的存入和取出顺序一样。

　　List作为Collection集合的子接口，不但继承了Collection接口中的全部方法，而且还增加了一些根据元素索引来操作集合的特有方法。

ArrayList集合

　　ArrayList是List接口的一个实现类，它是程序中最常见的一种集合。在ArrayList内部封装了一个长度可变的数组对象，当存入的数组长度超过数组长度时，ArrayList会在内存中分配一个更大的数组来储存这些元素，因此可以将ArrayList集合看做一个长度可变的数组。ArrayList集合中大部分方法都是从父接口Collection和List继承过来的。

public class Example01 {
    public static void main(String[] args) {
        ArrayList list = new ArrayList();//创建ArrayList集合
        //向集合中添加元素
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add(4,"e");//向集合的指定位置中插入指定的元素
        list.set(3,"x");//将指定位置索引的元素替换
        int i = list.size();//获取集合中元素的个数
        list.get(1);//获取指定位置索引的元素
        list.remove(4);//删除指定索引的元素
        list.contains("c");//集合是否存在指定的元素
        list.indexOf("b");//返回对象在集合中出现的位置索引
        list.lastIndexOf("c");//返回对象在集合中最后一次出现的位置索引
    }
 }

　　这里只是列举了部分基本的方法，剩下的就不一样列举了。

　　需要注意的是索引的取值范围是从0开始的，最后一个索引是size-1，在访问元素时一定要注意索引不可超出此范围，否则会抛出角标越界异常IndexOutOfBoundsException。

　　由于ArrayList集合的底层是使用一个数组来保存元素，在增加或删除指定位置的元素时，会导致创建新的数组，效率比较低，因此不适合做大量的增删操作。但这种数组的结构运行程序通过索引的方式来访问元素，因此使用ArrayList集合查找元素很便捷。

LinkedList集合

　　前面提到ArrayList集合在查询元素时速度很快，但在增删元素时效率较低，为了克服这种局限性，可以使用List接口的另一个实现类LinkedList。该集合内部维护了一个双向循环链表，链表中的每一个元素都使用引用的方式来记住它的前一个元素和后一个元素，从而可以将所有的元素彼此连接起来。当插入一个新元素时，只需要修改元素之间的这种引用关系即可，删除一个节点也是如此。正因为这样的存储结构，所以LinkedList集合对于元素的增删操作具有很高的效率。

　　LinkedList是基于链表结构实现的，所以在类中包含了first和last两个指针（Node）。Node中包含了上一个节点和下一个节点的引用，这样就构成了双向的链表。每个Node只能知道自己的前一个例程和后一个节点，但对于链表来说，这已经足够了。

　

 

 　　百度出来的答案基本都涉及底层原理，苦涩难懂，对于初学者来不太友好，简单点来说，新增一个元素时，元素1和元素2在集合中彼此互为前后关系，在它们之间新增一个元素时，只需要让元素1记住它后面的元素是新元素，让元素2记住它前面的元素为新元素就可以了；删除元素3时，只需要让元素1和元素2变成前后关系就可以了。（有兴趣的建议查阅官方文档或源码）

　　LinkedList集合除了具备增删元素效率高的特点，还专门针对元素的增删操作定义了一些特有的方法。

　　列出的方法主要针对集合中的元素进行增加、删除和获取操作。

public class Example {
    public static void main(String[] args) {
        LinkedList link = new LinkedList();//创建LinkedList集合
        //向集合中添加元素
        link.add("stu1");
        link.add("stu2");
        link.add("stu3");
        link.add("stu4");
        System.out.println(link.toString());//取出并打印该集合中的元素
        link.add(3,"student");//向集合中指定位置插入元素
        link.addFirst("First");//向该集合第一个位置插入元素
        System.out.println(link);
        System.out.println(link.getFirst());//取出该集合中第一个元素
        link.remove(3);//移除该集合中指定位置的元素
        link.removeFirst();//移除该集合中的第一个元素
        System.out.println(link);
    }
 }

运行结果：

 LinkedList源码解析(1.6)

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

}

迭代器

　　通常情况下，你会希望遍历一个集合中的元素。例如，显示集合中的每个元素。

　　一般遍历数组都是采用for循环或者增强for，这两个方法也可以用在集合框架，但是还有一种方法是采用迭代器遍历集合框架，它是一个对象，实现了Iterator 接口或 ListIterator接口。

　　迭代器，使你能够通过循环来得到或删除集合的元素。ListIterator 继承了 Iterator，以允许双向遍历列表和修改元素。

public class Example01 {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();//创建ArrayList集合
        //向集合中添加元素
        list.add("stu1");
        list.add("stu2");
        list.add("stu3");
        list.add("stu4");
      //第一种方法，把链表变为数组相关内容进行遍历
        String[] strArray = new String[list.size()];
        list.toArray(strArray);
        for (int i = 0; i <strArray.length ; i++) {
            System.out.println(strArray[i]);
        }
        //第二种遍历方法使用 For-Each 遍历 List
        for (String str : list) {
            System.out.println(str);
        }
        //第三种遍历 使用迭代器进行相关遍历
        Iterator it = list.iterator(); //获取Iterator对象
        while (it.hasNext()){       //判断ArrayList集合中是否存在下一个元素
            Object obj = it.next(); //取出ArrayList集合中的元素
            System.out.println(obj);
        }
    }
 }