java集合类源码分析之List（一）

　　首先分析一下集合与数组的区别：1.java中的数组一般用于存储基本数据类型，而且是静态的，即长度固定不变，这就不适用于元素个数未知的情况；2.集合只能用于存储引用类型，并且长度可变，适用于大多数情况，可用toArray()方法转换成数组。

java语言提供了多种集合类的接口，如List、Set、Map等。这里首先从List开始分析，其实现类有ArrayList、LinkedList、Vector（Stack），下面就从它们的源代码开始：

1.ArrayList（数组列表）

顾名思义，这是一种以数组形式进行存储的列表，所以其优点是便于随机访问，而在插入和删除操作时效率较低。

构造方法（三种）：

1.public ArrayList(int initialCapacity)　　指定初始列表的容量，当容量不够时会自动进行扩容

2.public ArrayList()　　空的构造方法

3.public ArrayList(Collection<? extends E> c)　　初始化列表元素，传入参数为一个集合类的对象

1         ArrayList<String> arrayList1 = new ArrayList<String>(3);    //初始化ArrayList容量大小
2         arrayList1.add("A");
3         arrayList1.add("B");
4         arrayList1.add("C");
5         ArrayList<String> arrayList2 = new ArrayList<String>(arrayList1);    //初始化ArrayList元素
6         System.out.println(arrayList2);    //[A, B, C]

View Code

插入元素（add）

1.在列表尾部插入 add(E e)

1  public boolean add(E e) {
2         ensureCapacityInternal(size + 1);  // Increments modCount!!
3         elementData[size++] = e;
4         return true;
5     }

View Code

2.在列表指定位置插入 add(int index, E element)

1 public void add(int index, E element) {
2         rangeCheckForAdd(index);
3 
4         ensureCapacityInternal(size + 1);  // Increments modCount!!
5         System.arraycopy(elementData, index, elementData, index + 1,
6                          size - index);
7         elementData[index] = element;
8         size++;
9     }

View Code

3.在列表尾部插入一个子集 addAll(Collection<? extends E> c)

1     public boolean addAll(Collection<? extends E> c) {
2         Object[] a = c.toArray();
3         int numNew = a.length;
4         ensureCapacityInternal(size + numNew);  // Increments modCount
5         System.arraycopy(a, 0, elementData, size, numNew);
6         size += numNew;
7         return numNew != 0;
8     }

View Code

4.在列表的指定位置插入一个子集 addAll(int index, Collection<? extends E> c)

 1     public boolean addAll(int index, Collection<? extends E> c) {
 2         rangeCheckForAdd(index);
 3 
 4         Object[] a = c.toArray();
 5         int numNew = a.length;
 6         ensureCapacityInternal(size + numNew);  // Increments modCount
 7 
 8         int numMoved = size - index;
 9         if (numMoved > 0)
10             System.arraycopy(elementData, index, elementData, index + numNew,
11                              numMoved);
12 
13         System.arraycopy(a, 0, elementData, index, numNew);
14         size += numNew;
15         return numNew != 0;
16     }

View Code

观察源码可知，在指定位置插入元素其实是通过arraycopy()方法来实现的，即是将原数组复制到目标数组，因而效率较低。

应用示例：

1         ArrayList<String> arrayList1 = new ArrayList<String>(3);    //初始化ArrayList容量大小
2         arrayList1.add("A");
3         arrayList1.add("B");
4         arrayList1.add("C");
5         arrayList1.add("D");
6         System.out.println(arrayList1);    //[A, B, C, D]
7         arrayList1.add(0, "E");
8         System.out.println(arrayList1); //[E, A, B, C, D]

View Code

查找元素

1.查找指定位置的元素 get(int index)

2.查找指定元素的位置 indexOf(Object o)、lastIndexOf(Object o)

3.查找列表中是否包含指定元素 contains(Object o)

1  public boolean contains(Object o) {
2         return indexOf(o) >= 0;
3     }

View Code

由于ArrayList以数组方式实现，自带索引，所以便于随机查找。

修改元素

修改指定位置的元素 set(int index, E element)

1         ArrayList<String> arrayList1 = new ArrayList<String>(3);    //初始化ArrayList容量大小
2         arrayList1.add("A");
3         arrayList1.add("B");
4         arrayList1.add("C");
5         arrayList1.add("D");
6         System.out.println(arrayList1); //[A, B, C, D]
7         arrayList1.set(0, "X");
8         System.out.println(arrayList1); //[X, B, C, D]

View Code

由于ArrayList以数组方式实现，自带索引，所以便于随机修改。

删除元素

1.删除指定位置的元素 remove(int index)

 1     public E remove(int index) {
 2         rangeCheck(index);
 3 
 4         modCount++;
 5         E oldValue = elementData(index);
 6 
 7         int numMoved = size - index - 1;
 8         if (numMoved > 0)
 9             System.arraycopy(elementData, index+1, elementData, index,
10                              numMoved);
11         elementData[--size] = null; // clear to let GC do its work
12 
13         return oldValue;
14     }

View Code

2.删除指定元素 remove(Object o)

 1     public boolean remove(Object o) {
 2         if (o == null) {
 3             for (int index = 0; index < size; index++)
 4                 if (elementData[index] == null) {
 5                     fastRemove(index);
 6                     return true;
 7                 }
 8         } else {
 9             for (int index = 0; index < size; index++)
10                 if (o.equals(elementData[index])) {
11                     fastRemove(index);
12                     return true;
13                 }
14         }
15         return false;
16     }

View Code

3.清空列表 clear()

1     public void clear() {
2         modCount++;
3 
4         // clear to let GC do its work
5         for (int i = 0; i < size; i++)
6             elementData[i] = null;
7 
8         size = 0;
9     }

View Code

从源码中我们可以知道，删除元素时也是通过arraycopy()方法，将原数组复制到目标数组，因而效率较低。

应用示例：

 1         ArrayList<String> arrayList1 = new ArrayList<String>(3);    //初始化ArrayList容量大小
 2         arrayList1.add("A");
 3         arrayList1.add("B");
 4         arrayList1.add("C");
 5         arrayList1.add("D");
 6         arrayList1.remove(0);
 7         System.out.println(arrayList1);    //[B, C, D]
 8         arrayList1.remove("D");
 9         System.out.println(arrayList1);    //[B, C]
10         arrayList1.clear();
11         System.out.println(arrayList1.isEmpty());    //true

View Code

2.LinkedList（链接列表）

顾名思义，以链表的方式来实现List接口，其优点是便于元素插入和删除，而在随机访问时效率较低。此外LinkedList提供额外的get，remove，insert方法操作 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

存储节点的基本定义（静态内部类实现）

 1     private static class Node<E> {
 2         E item;
 3         Node<E> next;
 4         Node<E> prev;
 5 
 6         Node(Node<E> prev, E element, Node<E> next) {
 7             this.item = element;
 8             this.next = next;
 9             this.prev = prev;
10         }
11     }

View Code

构造方法（两种）

1. public LinkedList()　　空的构造方法

2.public LinkedList(Collection<? extends E> c)　　初始化列表元素，传入参数为一个集合类的对象

插入元素

1.addFirst(E e) 在列表的头部插入

2.addLast(E e)、add(E e) 在列表的尾部插入

3.add(int index, E element) 在列表的指定位置插入

4.addAll(Collection<? extends E> c) 在列表的尾部插入一个子集

5.addAll(int index, Collection<? extends E> c) 在列表的指定位置插入一个子集

应用示例：

 1         LinkedList<Integer> linkedList = new LinkedList<Integer>();
 2         LinkedList<Integer> linkedList2 = new LinkedList<Integer>();
 3         linkedList.add(100);
 4         linkedList.add(120);
 5         linkedList.add(105);
 6                 System.out.println(linkedList);//[100, 120, 105]
 7         linkedList.add(200);
 8         System.out.println(linkedList);//[100, 120, 105, 200]
 9         linkedList.add(0, 300);
10         System.out.println(linkedList);//[300, 100, 120, 105, 200]
11         linkedList.addFirst(400);
12         System.out.println(linkedList);//[400, 300, 100, 120, 105, 200]
13         linkedList.addLast(500);
14         System.out.println(linkedList);//[400, 300, 100, 120, 105, 200, 500]
15         
16         linkedList2.addAll(linkedList);
17         System.out.println(linkedList2);//[400, 300, 100, 120, 105, 200, 500]
18         linkedList2.addAll(0, linkedList);
19         System.out.println(linkedList2);//[400, 300, 100, 120, 105, 200, 500, 400, 300, 100, 120, 105, 200, 500]

View Code

由于LinkedList以链表方式实现，所以在插入元素时只需要修改指针(前驱节点和后继节点)即可，因而效率较高。

查找元素

1.getFirst() 返回列表头部元素

2.getLast() 返回列表尾部元素

3.get(int index) 返回列表指定位置的元素

4.indexOf(Object o) 返回指定元素首次出现的位置

5.lastIndexOf(Object o) 返回指定元素最后一次出现的位置

应用示例：

1         System.out.println(linkedList);//[400, 300, 100, 120, 105, 200, 500]
2                 System.out.println(linkedList.getFirst());//400
3         System.out.println(linkedList.getLast());//500
4         System.out.println(linkedList.get(3));//120
5         System.out.println(linkedList.indexOf(120));//3;
6         System.out.println(linkedList.lastIndexOf(120));//3

View Code

由于链表实现的列表没有索引，所以查找指定位置的元素只能通过不断遍历来实现，因而效率低下。

修改元素

1.set(int index, E element) 修改指定位置的元素

1     public E set(int index, E element) {
2         checkElementIndex(index);
3         Node<E> x = node(index);
4         E oldVal = x.item;
5         x.item = element;
6         return oldVal;
7     }

View Code

同样首先需要遍历找到指定元素，然后进行修改，效率低下。

删除元素

1.removeFirst() 删除列表头部元素

2.removeLast() 删除列表尾部元素

3.remove(Object o) 删除指定元素

4.remove(int index) 删除指定位置的元素

应用示例：

1         System.out.println(linkedList);//[400, 300, 100, 120, 105, 200, 500]
2         System.out.println(linkedList.removeFirst());//400
3         System.out.println(linkedList.removeLast());//500
4         System.out.println(linkedList.remove(3));//105
5         System.out.println(linkedList.remove(new Integer("300")));//true

View Code

由于链接的实现方式，删除元素只需要修改指针（前驱节点和后继节点）即可，因而效率较高。

3.Vector（Stack）向量

Vector与ArrayList用法类似，并且也是以数组方式实现的，但它消耗的内存资源比ArrayList多，因而常常用于大量数据的存储，并且Vector是线程安全的。Stack（栈）是Vector的一个子类，具有后进先出的特性。

构造方法（四种）

1.Vector(int initialCapacity, int capacityIncrement) 指定初始容量以及扩容的大小

1     public Vector(int initialCapacity, int capacityIncrement) {
2         super();
3         if (initialCapacity < 0)
4             throw new IllegalArgumentException("Illegal Capacity: "+
5                                                initialCapacity);
6         this.elementData = new Object[initialCapacity];
7         this.capacityIncrement = capacityIncrement;
8     }

View Code

2.Vector(int initialCapacity) 指定初始容量

3.Vector() 空的构造器

4.Vector(Collection<? extends E> c) 初始化向量元素，参数为一个集合类的对象

应用示例：

1         Vector<Integer> vector1 = new Vector<Integer>();
2         vector1.add(100);
3         vector1.add(102);
4         Vector<Integer> vector2 = new Vector<Integer>(6);
5         Vector<Integer> vector3 = new Vector<Integer>(6, 3);
6         Vector<Integer> vector4 = new Vector<Integer>(vector1);
7         System.out.println(vector4); //[100, 102]

View Code

插入元素

1.addElement(E obj)、add(E e) 在向量尾部插入指定元素

2.add(int index, E element)、insertElementAt(E obj, int index) 在指定位置插入元素

 1     public synchronized void insertElementAt(E obj, int index) {
 2         modCount++;
 3         if (index > elementCount) {
 4             throw new ArrayIndexOutOfBoundsException(index
 5                                                      + " > " + elementCount);
 6         }
 7         ensureCapacityHelper(elementCount + 1);
 8         System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
 9         elementData[index] = obj;
10         elementCount++;
11     }

View Code

3.addAll(Collection<? extends E> c) 在向量尾部插入一个子集

4.addAll(int index, Collection<? extends E> c) 在向量的指定位置插入一个子集

 1     public synchronized boolean addAll(int index, Collection<? extends E> c) {
 2         modCount++;
 3         if (index < 0 || index > elementCount)
 4             throw new ArrayIndexOutOfBoundsException(index);
 5 
 6         Object[] a = c.toArray();
 7         int numNew = a.length;
 8         ensureCapacityHelper(elementCount + numNew);
 9 
10         int numMoved = elementCount - index;
11         if (numMoved > 0)
12             System.arraycopy(elementData, index, elementData, index + numNew,
13                              numMoved);
14 
15         System.arraycopy(a, 0, elementData, index, numNew);
16         elementCount += numNew;
17         return numNew != 0;
18     }

View Code

与ArrayList类似，在指定位置插入是通过arraycopy()方法实现的，即是将原数组复制到目标数组，因而效率较低。

查询元素

1.contains(Object o) 查询是否包含指定元素

2.indexOf(Object o) 返回指定元素首次出现的位置

3.indexOf(Object o, int index) 返回从index开始的指定元素首次出现的位置

4.elementAt(int index) 返回指定位置的元素

5.firstElement() 返回响向量的第一个元素

6.lastElement() 返回向量的最后一个元素

7.get(int index) 返回指定位置的元素

8.subList(int fromIndex, int toIndex) 返回指定位置的子序列

由于Vector使用数组实现，自带索引，因此在查询时效率较高。

修改元素

1.set(int index, E element) 修改指定位置的元素

2.setElementAt(E obj, int index) 修改指定位置的元素

应用示例：

1         System.out.println(vector4); //[100, 102, 200]
2         
3         vector4.set(0, 500);
4         System.out.println(vector4);//[500, 102, 200]
5         vector4.setElementAt(300, 1);
6         System.out.println(vector4);//[500, 300, 200]

View Code

删除元素

1.removeElement(Object obj)、remove(Object o) 删除首次出现的指定元素

2.removeAllElements() 清空向量的所有元素

3.remove(int index) 删除指定位置的元素

4.removeAll(Collection<?> c) 删除向量中出现的集合c中的元素

5.removeElementAt(int index) 删除指定位置的元素

应用示例:

1         System.out.println(vector4);//[500, 300, 200]
2         
3         vector4.removeAll(vector1);
4         System.out.println(vector4);//[500, 300]
5         vector4.removeAllElements();

View Code

与ArrayList类似，删除指定位置的元素时也是将原数组复制到目标数组实现的。

Stack（栈）

前面说过Stack是Vector的一个子类，可以调用其父类的大部分成员方法，这里只介绍Stack自身的一些成员方法：

1.public Stack() 空的构造器

2.E push(E item) 将一个元素压入栈顶

3.E pop() 返回栈顶元素，并将该元素移除

4.E peek() 返回栈顶元素，而并不将其移除

5.empty() 判断栈是否为空

6.search(Object o) 搜索栈中的元素，返回值为该元素在栈中的位置（从1开始计数，自上而下）

 1         Stack<Integer> stack = new Stack<Integer>();
 2         stack.push(100);
 3         stack.push(200);
 4         stack.push(300);
 5         System.out.println(stack.peek());//300
 6         System.out.println(stack.size());//3
 7         System.out.println(stack.pop());//300
 8         System.out.println(stack.size());//2
 9         stack.push(100);
10         stack.push(200);
11         stack.push(300);
12         System.out.println(stack);//[100, 200, 100, 200, 300]
13         System.out.println(stack.search(100));//3

View Code

至此，List集合的几个实现类基本介绍完毕，下一节将分析这几个实现类的区别。

秒客网

java集合类源码分析之List（一）

1.ArrayList（数组列表）

2.LinkedList（链接列表）

3.Vector（Stack）向量

相关文章