集合的概念？
- 集合类存放在java.util包中
- 集合类存放的都是对象的引用，而非对象本身，出于表达上的便利，称集合中的对象就是指集合中对象的引用。
- 集合类型主要有3种：set（集）、list（列表）和map（映射）
通俗的说，集合就是一个放数据的容器，准确的说是放数据对象引用的容器。
有哪些集合？
- 集合主要分为Collection和Map2个接口。Collection又分别被List和Set继承
- List被AbstractList实现，然后分为3个子类，ArrayList，LinkList和Vector
- Set被AbstractSet实现，又分为HashSet和TreeSet
- 而Map衍生出的集合分为HashMap,HashTable和TreeMap
什么是List？
以下为List的官方定义：
List主要分为3类，ArrayList，LinkedList和Vector,List是一个有序的集合，和set不同的是，List允许存储项的值为空，也允许存储相等值得存储项，还举了e1.equal(e2)的例子
ArrayList?
ArrayList是一个数组实现的列表，由于数据是存入数组中的，所以它的特点也和数组一样，查询很快，但是中间部分的插入和删除很慢。
A.ArrayList的类关系和成员变量
1 | //ArrayList继承了Serializable并且申明了serialVersionUID，表示ArrayList是一个可序列化的对象，可以用Bundle传递 |
B.构造函数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//ArrayList有2个构造函数，一个是默认无参的，一个是传入数组大小的
//在JavaEffect书中明确提到，如果预先能知道或者估计所需数据项个数的，需要传入initialCapacity
//因为如果使用无参的构造函数，会首先把EMPTY_ELEMENTDATA赋值给elementData
//然后根据插入个数于当前数组size比较，不停调用Arrays.copyOf()方法，扩展数组大小
//造成性能浪费
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
C.add()操作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//首先看到，不过是指定index执行add操作，还是在尾部执行add操作，都会先确认当前的数组空间是否够插入数据
//并且从
//int oldCapacity = elementData.length;
//int newCapacity = oldCapacity + (oldCapacity >> 1);
//if (newCapacity - minCapacity < 0)
// newCapacity = minCapacity;
//看出，ArrayList默认每次都是自增50%的大小再和minCapacity比较，如果还是不够，就把当的
//size扩充至minCapacity
//然后，如果是队尾插入，也简单，就把数组向后移动一位，然后赋值
//如果是在中间插入，需要用到System.arraycopy，把index开始所有数据向后移动一位
//再进行插入
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
D.remove()操作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//个人感觉整个remove操作的代码写了很冗余，不像甲骨文这些大神的风格
//首先来看remove(int index)
//先进行边界确认，传入的index是否超过了当前数组的大小，如果是抛出异常
//如果在数组范围内，就把index之后的数据整体向前移动一位，最后一位值清空
//如果是remove(Object o)，传入的是一个对象，就会进行一次indexOf的操作，去当前数组中寻找
//判断是否存在，这里的代码就十分冗余了，就是把indexOf的代码拷贝了一次，完全可以调用indexOf方法
//根据返回值是否为-1来判断该值是否存在，如果存在就调用fastRemove方法
//fastRemove(int index)和remove(int index)方法除了边界检查一模一样
//完全可以在remove调用完rangeCheck(index)后调用fastRemove就可以了
//这里不是很明白设计者的意图
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
E.indexOf()操作1
2
3
4
5
6
7
8
9
10
11
12
13//这里就和上面remove寻找是一模一样的，就不进行探讨了
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Vector ?
Vector就是ArrayList的线程安全版，它的方法前都加了synchronized锁，其他实现逻辑都相同。
如果对线程安全要求不高的话，可以选择ArrayList，毕竟synchronized也很耗性能
LinkedList ?
- link 链接，环节，链路，链
- 故名思意就是链表
- LinkedList还是一个双向链表
LinkedList继承于AbstractSequentialList,和ArrayList一个套路。内部维护了3个成员变量，一个是当前链表的头节点，一个是尾部节点，还有是链表长度。
A.add()操作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//首先void linkLast(E e)，尾部插入
//就是把newNode的前面节点执行现在的尾部节点，newNode的后面节点执行null,因为是在尾部嘛
//然后把现在的尾部节点的后面节点指向newNode,因为现在的尾部节点不是最后一个了
//然后再来看下中间插入
//也是一个套路。假设现在在3号位插入一个newNode
//就是通过现在的3号Node的prev找到2号节点，然后修改2号节点的next，指向nowNode
//然后nowNode的prev指向2号节点，next指向3号节点
//最后3号节点的prev变成了nowNode,next不变
//这样就完成了一次中间插入
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
B.linkLast()操作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//indexOf操作非常简单，就是从头开始遍历整个链表，如果没有就反-1，有就返回当前下标
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
C.remove操作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//如果直接调无参的remove(),就会默认删除头节点
//删除头节点非常简单，就是把头节点的值清空，next清空
//然后把nextNode只为头节点，然后清空next的prev
//最后size减1
//如果是删除中间节点，调用remove(int index)
//首先判断Index对应的节点是否为头节点，即index是否为0
//如果不是中间节点，就是x的prev指向x的next
public E remove() {
return removeFirst();
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
/**
* Unlinks non-null node x.
*/
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) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
总结
通过ArrayList和LinkedList的对比分析，可以得出List的3个特性
- 按顺序查找
- 允许存储项为空
- 允许多个存储项的值相等
- ArrayList是由数组实现的，方便查找，返回数组下标对应的值即可
- LinkedList由链表实现，插入和删除方便
- ArrayList的遍历，可以用for循环实现，可以通过数组下标得到元素，ArrayList的get()方法的时间复杂度为O(1)
- LinkedList的遍历，因为它是双向链表，需要根据所给的下标从头或者尾部开始往下标的位置依次获得下一个元素或者上一个元素，所以Linkedlist不要用for循环，应该用迭代器进行遍历