• ArrayList提供了一宗可增长数组的实现。有点事对get和set调用花费常数时间。缺点是插入和删除代价昂贵,除非插入和删除是在ArrayList的末端进行。
  • LinkedList提供了双链表实现。优点是,插入和删除开销很小,花费常数时间。缺点是不容易做索引,get和set调用昂贵,除非调用接近表的断点的项(离哪端近就从哪端开始)。

原文地址:http://blog.csdn.net/qq_25806863/article/details/76423425

这两个集合主要是内部对数据的存储方式不一样,一个用的数组,一个用的链表。

数组和链表

关于数组合链表在之前有个简单的比较

简单数组

array list

  • 数组可以使遍历以线性时间执行O(N)
  • 查找是常数时间O(1)
  • 不过插入和删除开销昂贵,如果发生在第一个元素上,时间是O(N),如果发生在最后一个元素上也就是高端,时间是O(1)

当插入和删除都只对高端操作,数组也比较合适,否则就应用 链表 linked list

简单链表

使用链表是因为链表在内存中是不连续的,不用因为一个元素的插入或删除而引起其他元素的变动。

一般链表

链表由一系列节点组成,节点不需要在内存中相连,因此每一个节点除了自身元素外还要包含自己的后继元的节点的链(link),称之为next链。最后一个节点的next链引用null。

  • 遍历的时间是O(N),跟数组一样。
  • 查找的时间,因为需要从第一个节点开始查找,所以时间也是线性的,O(N) 。要查找第x个元素,花费的时间是O(x), 效率不如数组。
  • 删除可以通过修改next链的引用来实现
  • 插入也一样,获取一个新节点,修改两个next链的引用,

删除A2:

删除一个元素

在A1后插入Ax:

插入

双链表

让每一个节点拥有其前驱节点的引用就成了双链表。

双链表

ArrayList和LinkedList

  • ArrayList提供了一宗可增长数组的实现。有点事对get和set调用花费常数时间。缺点是插入和删除代价昂贵,除非插入和删除是在ArrayList的末端进行。
  • LinkedList提供了双链表实现。优点是,插入和删除开销很小,花费常数时间。缺点是不容易做索引,get和set调用昂贵,除非调用接近表的断点的项(离哪端近就从哪端开始)。

ArrayList的实现

  • 内部使用数组来保存数据,有一个默认的数组容量
  • 当容量不够的时候,扩容一个新数组,将老数据复制到新数组,释放旧数组。
  • 内部类实现 MyIterator
  • 增强for循环的实现 implements Iterable
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
124
125
126
127
128
129
import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.function.Consumer;
/**
* @author sll on 2017/6/30.
*/
public class MyArrayList<Element> implements Iterable<Element> {
private static final int DEFAULT_CAPACITY = 5;
private int size;
private Element[] elements;
private int modCount = 0;
public MyArrayList() {
elements = (Element[]) new Object[DEFAULT_CAPACITY];
clear();
}
public void clear() {
size = 0;
ensureCapacity(DEFAULT_CAPACITY);
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void trimToSize() {
ensureCapacity(size);
}
//这里是查找,使用数组直接就查出来了,所以一次查询的时间是 O(1)
public Element get(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
return elements[index];
}
public Element set(int index, Element newElement) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
Element old = elements[index];
elements[index] = newElement;
return old;
}
public boolean add(Element e) {
return add(size, e);
}
//这里的增加和删除就要移动很多项,所以一次插入或删除的速度是 O(N)
public boolean add(int index, Element e) {
if (elements.length == size) {
ensureCapacity(size * 2 + 1);
}
System.arraycopy(elements, index, elements, index + 1, size - index);
elements[index] = e;
size++;
modCount++;
return true;
}
public Element remove(int index) {
Element removeElement = elements[index];
int moveNum = size - index - 1;
if (moveNum > 0) {
System.arraycopy(elements, index + 1, elements, index, moveNum);
}
size--;
elements[size] = null;
modCount++;
return removeElement;
}
public void ensureCapacity(int newCapacity) {
if (newCapacity < size)
return;
elements = Arrays.copyOf(elements, newCapacity);
}
public Itr iterator() {
return new Itr();
}
private class Itr implements Iterator<Element> {
private int exceptMocCount = modCount;
private int current = 0;
@Override
public boolean hasNext() {
return current < size();
}
@Override
public Element next() {
if (exceptMocCount != modCount) {
throw new ConcurrentModificationException();
}
if (!hasNext()) {
throw new NoSuchElementException();
}
return elements[current++];
}
@Override
public void remove() {
if (exceptMocCount != modCount) {
throw new ConcurrentModificationException();
}
MyArrayList.this.remove(--current);
}
@Override
public void forEachRemaining(Consumer<? super Element> action) {
}
}
}

LinkedList的实现

  • 使用双链表来实现
  • 节点类Node,为私有静态内部类(嵌套类),包含数据和前后节点的链
  • 有两个额外的节点,头节点和尾节点,中间才是数据
  • 内部实现MyIterator
  • 增强for循环的实现 implements Iterable
  • 对add和remove增加一个计数modCount,在迭代器的hasNext和next中比较这个计数,不同就说明这个集合被修改了,就抛出异常ConcurrentModificationException。
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* @author sll on 2017/6/30.
*/
public class MyLinkedList<E> implements Iterable<E> {
private int theSize = 0;
private int modCount = 0;
private Node<E> startNode, endNode;//额外的头节点和尾节点
public MyLinkedList() {
clear();
}
private void clear() {
startNode = new Node(null, null, null);
endNode = new Node(null, startNode, null);
startNode.next = endNode;
theSize = 0;
modCount++;
}
public int size() {
return theSize;
}
public boolean isEmpty() {
return size() == 0;
}
public boolean add(E x) {
return add(size(), x);
}
public boolean add(int index, E x) {
addBefore(getNode(index), x);
return true;
}
public E get(int index) {
return getNode(index).data;
}
public E set(int index, E x) {
Node<E> p = getNode(index);
E old = p.data;
p.data = x;
return old;
}
public E remove(int index) {
return remove(getNode(index));
}
private void addBefore(Node<E> p, E x) {
Node<E> newNode = new Node<>(x, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
modCount++;
}
private Node<E> getNode(int index) {
Node<E> p;
if (index < 0 || index > size())
throw new IndexOutOfBoundsException();
if (index < size() / 2) {
p = startNode.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
} else {
p = endNode;
for (int i = size(); i > index; i--) {
p = p.prev;
}
}
return p;
}
private E remove(Node<E> x) {
x.prev.next = x.next;
x.next.prev = x.prev;
theSize--;
modCount++;
return x.data;
}
@Override
public Iterator<E> iterator() {
return new MyIterator();
}
private static class Node<E> {
public E data;
public Node<E> prev;
public Node<E> next;
public Node(E data, Node<E> prev, Node<E> next) {
this.data = data;
this.prev = prev;
this.next = next;
}
}
private class MyIterator implements Iterator<E> {
private Node<E> current = startNode.next;
private int expectedModCount = modCount;
private boolean okToRemove = false;
@Override
public boolean hasNext() {
return current!= endNode;
}
@Override
public E next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (!hasNext()) {
throw new NoSuchElementException();
}
E nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}
@Override
public void remove() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (!okToRemove) {
throw new NoSuchElementException();
}
MyLinkedList.this.remove(current.prev);
okToRemove = false;
expectedModCount++;
}
}
}

时间对比

以分别用ArrayList和LinkedList用下面三个方法做一个时间对比:

###

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//从末端添加,创建一个由N个项的List。
public static void makeList1(List<Integer> list, int N) {
list.clear();
for (int i = 0; i < N; i++) {
list.add(i);
}
}
//从首端添加,创建一个由N个项的List。
public static void makeList2(List<Integer> list, int N) {
list.clear();
for (int i = 0; i < N; i++) {
list.add(0, i);
}
}
//获取长度为N的List的每一个值求和。
public static void makeList3(List<Integer> list) {
long total = 0;
for (int i = 0; i < list.size(); i++) {
total += list.get(i);
}
}

首先创建两个集合,N=100000,打印耗费时间(ms):

1
2
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<Integer>();
  • makeList1

    1
    2
    makeList1(arrayList, 100000);
    makeList1(linkedList, 100000);

    结果可能会不一样,但也是相近的。

    运行时间都是O(N)

  • makeList2

    1
    2
    makeList2(arrayList, 100000);
    makeList2(linkedList, 100000);

    linkedList花费的时间少得多,执行时间是O(N)

    而ArrayList因为每次在头部插入都需要将之前所有项向后移动一位,所以执行时间是O(N^2)

  • makeList3

    1
    2
    3
    4
    5
    makeList2(arrayList, 100000);
    makeList2(linkedList, 100000);
    makeList3(arrayList);
    makeList3(linkedList);

​ 这个每次都要查找,所以ArrayList比较快,执行时间是O(N)

​ 而inkedList的执行时间是O(N^2)

  • 用迭代器实现makeList3

    将makeList3改成:

    1
    2
    3
    4
    5
    6
    public static void makeList3(List<Integer> list) {
    long total = 0;
    for (Integer i : list) {
    total+=i;
    }
    }

​ 两个都很相近了,都是O(N)。

参考《数据结构与算法分析java版》