Java集合框架详解（一）Collection接口、List接口、ArrayList类、Vector类

一、集合架构图

二、Collection接口

Collection集合的遍历
迭代器：Iterater

Collection<String> collection = new ArrayList<String>();
collection.add("test01");
collection.add("test02");
collection.add("test03");
collection.add("test04");
Iterator iterator = collection.iterator();
while (iterator.hasNext()){
	System.out.println(iterator.next());
}
1
2
3
4
5
6
7
8
9

手写Iterator迭代器的hasNext方法和next方法：

public class TestIterator {
    private List list;
    
    /**
     * @param list
     */
    public TestIterator(List list){
        this.list = list;
    }

    //计数器 初始值为0
    private int count = 0;

    /**
     * 手写 next方法
     * @return
     */
    public Object next(){
        if(list == null){
            throw new TestException("list is null");
        }
        if(count>=list.size()){
            throw new TestException("无法向下获取元素了");
        }
        return list.get(count++);
    }

    /**
     * 手写 hasNext方法
     * @return boolean 
     */
    public boolean hasNext(){
        return count != list.size();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

> 三、List接口：

（1）有序集合：存储和取出的元素顺序一致，可以精确控制集合中每个元素，可以通过索引访问元素，并搜索集合中的元素。
（2）可重复：存放的数据可以重复。
（3）子类：

• ArrayList：底层是基于数组结构来实现的；
• LinkedList：底层是基于链表结构来实现的。

三、ArrayList类

1. ArrayList的特点

ArrayList是基于数组结构来实现的。
ArrayList根据index下标查询get(index)、修改set(index, e)效率非常高，增加add(e)、删除remove(index)效率非常低。
ArrayList存放的数据可以重复，存入数据保证有序性。
ArrayList不是线程安全的。
ArrayList类是一个可以动态修改的数组，它没有固定长度.
ArrayList类位于java.util包中。

2. ArrayList常见的方法

eg：

List<String> arrayList = new ArrayList<String>();
//添加元素1
arrayList.add("test01");
arrayList.add("test02");
//添加元素2
arrayList.add(2, "text03");
//删除元素
arrayList.remove(1);
//替换元素
arrayList.set(0,"test011");
//元素数量
arrayList.size();
1
2
3
4
5
6
7
8
9
10
11
12

3. ListItertor迭代器

public class Test02 {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("test01");
        list.add("test02");
        list.add("test03");
        ListIterator listIterator = list.listIterator();
        //从前往后遍历
        while (listIterator.hasNext()){
            System.out.println(listIterator.next());
        }
        //从后往前遍历
        while (listIterator.hasPrevious()){
            System.out.println(listIterator.previous());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. 增强for循环

int[] arrInt = {60,88,99,10};
for(int arr:arrInt){
	System.out.println(arr);
}
System.out.println("---------------------");
List<String> list = new ArrayList<String>();
list.add("test01");
list.add("test02");
list.add("test03");
list.add("test04");
for(String arr:list){
	System.out.println(arr);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5. Arrays.asList方法
   Arrays.asList方法可以创建集合，但创建的集合时不能够进行添加add()和删除remove()操作，集合的元素个数是不能够发生变化的，可以使用set()方法进行替换元素操作。

public static void main(String[] args) {
	//使用Arrays.asList方法创建的集合时不能够添加add()和删除remove()的
    List<String> stringList = Arrays.asList("qize", "chenq", "zeyu");
    System.out.println(stringList);
 }
1
2
3
4
5

6. ArrayList的效率问题

ArrayList 查询功能（get）：底层基于数组实现，根据index下标查询效率非常高，时间复杂度为O(1)。
ArrayList 新增功能（add）：ArrayList默认初始化数组容量为10，如果底层数组容量不够的情况下，就会触发动态扩容机制，效率非常低。
ArrayList 删除功能(remove)：会将删除后面的元素向前移动一位效率也非常低。
ArrayList 修改功能(set)：根据下标位置修改，效率非常高；根据元素修改，效率非常低。

7. ArrayList总结

（1）ArrayList 底层是基于数组实现的；
（2）ArrayList 底层数组初始化容量为10；
（3）ArrayList 每次扩容是原来的1.5倍；
（4）ArrayList 是线程不安全的；
（5）ArrayList 懒加载的形式去初始化容量，不调用add方法不会有容量

ArrayList 的 add()方法的实现：

（1）判断集合容量是否装得下；
（2）如果装不下则扩容，1.5倍创建新数组，将原来的数组的数据拷贝到新的数组中。

ArrayList 的 get()方法的实现：

（1）直接提供了根据index下标查询，效率非常高；

ArrayList 的 remove()方法的实现：

（1）查找到删除对于的index 下标位置+1到最后的元素值向前移动一位。

四、Vector类

1. Vector总结

（1）Vector 底层是基于数组实现的；
（2）Vector 底层数组初始化容量为10；
（3）Vector 每次扩容是原来的2倍；
（4）Vector 是线程安全的；
（5）Vector 直接通过构造函数去初始化容量，数组容量为10。

eg:

public class Test01 {
    public static void main(String[] args) {
        Vector<String> strings1 = new Vector<>();
        strings1.add("qize");
        //参数10为初始化容量=10，参数20为每次扩容20
        Vector<String> strings2 = new Vector<>(10,20);
    }
}
1
2
3
4
5
6
7
8

五、ArrayList 与Vector的异同

1. 相同点

（1）ArrayList 与 Vector 底层都是基于数组实现的；
（2）ArrayList 与 Vector 初始化数组容量都为10；
（3）ArrayList 与 Vector 都是List接口下的子类。

2. 不同点

（1）ArrayList 是线程不安全的，Vector 是线程安全的；
（2）ArrayList 每次扩容是原来的1.5倍，Vector 每次扩容是原来的2倍；
（3）ArrayList 懒加载的形式去初始化容量，不调用add方法不会有容量，Vector 直接通过构造函数去初始化容量，Vector 可以设置每次扩容的容量。

六、LinkedList类

1. LinkedList类概述

（1）LinkedList类底层是基于双向链表结构实现的，不同于ArrayList类和Vector类是基于数组实现的；
（2）LinkedList类是非线程安全的；
（3）LinkedList类元素允许为null，允许重复元素；
（4）LinkedList类插入、删除效率高，查询效率低；
（5）LinkedList类基于链表实现的，因此不存在容量不足的问题，不用动态扩容；
（6）双向链表有三个区域，前指针域、数据域、后指针域。
（7）LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
（8）LinkedList 实现 List 接口，能对它进行队列操作。
（9）LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
（10）LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
（11）LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
（12）LinkedList 是非同步的。

2. LinkedList类的方法

与ArrayList类相似，LinkedList类常见方法也有add()、get()、remove()、set()、size()等，用法也类似。
Object getFirst（） 它返回链表的第一个元素。
Object getLast（） 它返回链接列表的最后一个元素。
boolean contains（Object element）如果元素存在于列表中，则返回true。
void clear（）：删除列表中的所有元素。

3. LinkedList类的特点

（1）LinkedList的底层结构为双向链表，将零散的内存单元通过附加的引用关联起来体现出其顺序性，相比数组的连续空间存储，链表对内存的利用率更高；
（2）有序：插入元素的顺序和取出顺序一致；
（3）可重复：可以插入相同的元素（元素值也允许为null）；
（4）插入、删除操作效率高，和ArrayList恰恰相反，按索引查找效率较低；
（5）线程不安全：没有线程锁，多个线程同步进行写操作的时候可能导致数据错误；
（6）使用场景：不会随机访问数据，更多的插入删除操作，更少的查询读取操作。

4. LinkedList类简化版原码

public class QizeLinkedList<E> {
    private Node<E> first;//链表中第一个节点
    private Node<E> last;//链表中最后一个节点
    private int size;//链表当前节点数

    private static class Node<E>{
        E item;//当前节点的值
        private Node<E> prev;//当前节点的上一个节点
        private Node<E> next;//当前节点的下一个节点

        /**
         * 构造方法
         * @param prev
         * @param item
         * @param next
         */
        public Node(Node<E> prev, E item, Node<E> next){
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }

    /**
     * 插入方法
     *
     * @param e
     */
    public void add(E e){
        Node l = last;//获取链表中最后一个节点
        //最后一个节点就是新创建节点的上一个节点，新创建节点的下一个节点为null
        Node<E> newNode = new Node<>(l,e,null);
        last = newNode;
        if(l == null){
            //如果在链表中没有最后一个节点，链表为空
            first = newNode;
        }else {
            l.next = newNode;
        }
        size++;
    }

    /**
     * 利用折半查找算法来实现查询的方法
     *
     * @param index
     * @return
     */
    private Node<E> node(int index){
        if(index < size >> 1){
            //如果index小于size值的一半，则查询链表中间值的左边
            Node<E> f = first;
            for(int i=0;i<index; i++){
                f = f.next;
            }
            return f;
        }else{
            //如果index大于size值的一半，则查询链表中间值的右边
            Node<E> l = last;
            for(int i=size-1; i>index; i--){
                l = l.prev;
            }
            return l;
        }
    }

    /**
     * 查询方法
     * @param index
     * @return
     */
    public E get(int index){
        //下标如果越界，需要做报错处理
        return node(index).item;
    }

    public E remove(int index){
        return unlink(node(index));
    }

    private E unlink(Node<E> node){
        //根据index查询需要删除的node节点
        //获取删除节点的上一个节点和下一个节点
        Node<E> prev = node.prev;//删除节点的上一个节点
        Node<E> next = node.next;//删除节点的下一个节点
        final E element = node.item;//删除节点的元素值
        if(prev == null){
            //如果删除节点的上一个节点是null,则删除的节点是头节点
            first = next;
        }else {
            //删除节点上一个节点.next节点=删除节点的下一个节点
            prev.next = next;
            node.prev = null;
        }
        if(next == null){
            //如果删除节点的下一个节点是null,则删除的节点是尾节点
            last = prev;
        }else {
            //如果删除的不是尾节点，删除的下一个节点.prev=删除的上一个节点
            next.prev = prev;
            node.next = null;//gc回收
        }
        node.item = null;
        size--;
        return element;
    }

    public static void main(String[] args) {
        QizeLinkedList qizeLinkedList = new QizeLinkedList();
        qizeLinkedList.add("qize1");
        qizeLinkedList.add("qize2");
        qizeLinkedList.add("qize3");
        System.out.println("--------------------");
        System.out.println(qizeLinkedList.get(0));
        System.out.println(qizeLinkedList.get(1));
        System.out.println(qizeLinkedList.get(2));
        System.out.println("--------------------");
        qizeLinkedList.remove(1);
        System.out.println(qizeLinkedList.get(1));
        System.out.println("--------------------");

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123