- ArrayList提供了一宗可增長數(shù)組的實現(xiàn)。有點事對get和set調用花費常數(shù)時間弛饭。缺點是插入和刪除代價昂貴徘公，除非插入和刪除是在ArrayList的末端進行。
- LinkedList提供了雙鏈表實現(xiàn)军洼。優(yōu)點是，插入和刪除開銷很小演怎，花費常數(shù)時間匕争。缺點是不容易做索引，get和set調用昂貴爷耀，除非調用接近表的斷點的項(離哪端近就從哪端開始)甘桑。
原文地址：http://blog.csdn.net/qq_25806863/article/details/76423425
這兩個集合主要是內部對數(shù)據(jù)的存儲方式不一樣，一個用的數(shù)組，一個用的鏈表跑杭。
數(shù)組和鏈表
關于數(shù)組合鏈表在之前有個簡單的比較
簡單數(shù)組
array list
- 數(shù)組可以使遍歷以線性時間執(zhí)行
O(N)铆帽。 - 查找是常數(shù)時間
O(1)。 - 不過插入和刪除開銷昂貴德谅，如果發(fā)生在第一個元素上爹橱，時間是
O(N),如果發(fā)生在最后一個元素上也就是高端，時間是O(1)
當插入和刪除都只對高端操作窄做，數(shù)組也比較合適愧驱，否則就應用 鏈表 linked list
簡單鏈表
使用鏈表是因為鏈表在內存中是不連續(xù)的，不用因為一個元素的插入或刪除而引起其他元素的變動椭盏。
一般鏈表
鏈表由一系列節(jié)點組成组砚，節(jié)點不需要在內存中相連，因此每一個節(jié)點除了自身元素外還要包含自己的后繼元的節(jié)點的鏈(link),稱之為next鏈掏颊。最后一個節(jié)點的next鏈引用null糟红。
- 遍歷的時間是
O(N),跟數(shù)組一樣。 - 查找的時間乌叶，因為需要從第一個節(jié)點開始查找盆偿，所以時間也是線性的，
O(N)枉昏。要查找第x個元素陈肛，花費的時間是O(x), 效率不如數(shù)組。 - 刪除可以通過修改next鏈的引用來實現(xiàn)
- 插入也一樣兄裂，獲取一個新節(jié)點，修改兩個next鏈的引用阳藻，
刪除A2：
刪除一個元素
在A1后插入Ax：
插入
雙鏈表
讓每一個節(jié)點擁有其前驅節(jié)點的引用就成了雙鏈表晰奖。
雙鏈表
ArrayList和LinkedList
- ArrayList提供了一宗可增長數(shù)組的實現(xiàn)。有點事對get和set調用花費常數(shù)時間腥泥。缺點是插入和刪除代價昂貴匾南，除非插入和刪除是在ArrayList的末端進行。
- LinkedList提供了雙鏈表實現(xiàn)蛔外。優(yōu)點是蛆楞，插入和刪除開銷很小，花費常數(shù)時間夹厌。缺點是不容易做索引豹爹，get和set調用昂貴，除非調用接近表的斷點的項(離哪端近就從哪端開始)矛纹。
ArrayList的實現(xiàn)
- 內部使用數(shù)組來保存數(shù)據(jù)臂聋，有一個默認的數(shù)組容量
- 當容量不夠的時候，擴容一個新數(shù)組，將老數(shù)據(jù)復制到新數(shù)組孩等，釋放舊數(shù)組艾君。
- 內部類實現(xiàn) MyIterator
- 增強for循環(huán)的實現(xiàn) implements Iterable<T>
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);
}
//這里是查找，使用數(shù)組直接就查出來了肄方，所以一次查詢的時間是 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的實現(xiàn)
- 使用雙鏈表來實現(xiàn)
- 節(jié)點類Node，為私有靜態(tài)內部類（嵌套類）,包含數(shù)據(jù)和前后節(jié)點的鏈
- 有兩個額外的節(jié)點权她，頭節(jié)點和尾節(jié)點虹茶，中間才是數(shù)據(jù)
- 內部實現(xiàn)MyIterator
- 增強for循環(huán)的實現(xiàn) implements Iterable<E>
- 對add和remove增加一個計數(shù)modCount，在迭代器的hasNext和next中比較這個計數(shù)伴奥，不同就說明這個集合被修改了写烤，就拋出異常ConcurrentModificationException。
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;//額外的頭節(jié)點和尾節(jié)點
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用下面三個方法做一個時間對比：
//從末端添加拾徙，創(chuàng)建一個由N個項的List洲炊。
public static void makeList1(List<Integer> list, int N) {
list.clear();
for (int i = 0; i < N; i++) {
list.add(i);
}
}
//從首端添加，創(chuàng)建一個由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);
}
}
首先創(chuàng)建兩個集合，N=100000崖瞭，打印耗費時間(ms)：
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<Integer>();
-
makeList1
makeList1(arrayList, 100000); makeList1(linkedList, 100000);結果可能會不一樣狂巢，但也是相近的。
運行時間都是O(N)
-
makeList2
makeList2(arrayList, 100000); makeList2(linkedList, 100000);linkedList花費的時間少得多书聚，執(zhí)行時間是O(N)
而ArrayList因為每次在頭部插入都需要將之前所有項向后移動一位唧领，所以執(zhí)行時間是O(N^2)
-
makeList3
makeList2(arrayList, 100000); makeList2(linkedList, 100000); makeList3(arrayList); makeList3(linkedList);
? 這個每次都要查找，所以ArrayList比較快雌续，執(zhí)行時間是O(N)
? 而inkedList的執(zhí)行時間是O(N^2)
-
用迭代器實現(xiàn)makeList3
將makeList3改成：
public static void makeList3(List<Integer> list) { long total = 0; for (Integer i : list) { total+=i; } }
? 兩個都很相近了斩个，都是O(N)。
參考《數(shù)據(jù)結構與算法分析java版》
