ArrayList和LinkedList时间复杂度的比较:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ArrayList LinkedList
add(e: E) O(1) O(1)
add(index: int, e: E) O(n) O(n)
remove(e: E) O(n) O(n)
remove(index: int) O(n) O(n)
contains(e: E) O(n) O(n)
get(index: int) O(1) O(n)
indexOf(e: E) O(n) O(n)
lastIndexOf(e: E) O(n) O(n)
clear() O(1) O(1)
isEmpty() O(1) O(1)
size() O(1) O(1)
set(index: int, e: E) O(n) O(n)
addFirst(e: E) O(n) O(1)
removeFirst() O(n) O(1)
addLast(e: E) O(1) O(1)
removeLast() O(1) O(1)

链表中结点的定义:

1
2
3
4
5
6
7
8
class Node<E>{
E element;
Node<E> next;
public Node(E element){
this.element = element;
}
}

迭代器接口java.util.Iterator

1
2
3
4
5
6
7
8
9
10
11
package java.util;
public interface Iterator{
public boolean hasNext();//如果迭代器有更多的元素要遍历则返回true
public Object next();//返回来自迭代器的下一个元素
public void remove();//删除使用next方法获得的最后一个元素
}
//应用迭代器
java.util.Iterator<String> iterator = list.iterator();
while(iterator.hasNext())
System.out.print(iterator.next() + " ");

迭代器提供了遍历一个容器中元素的统一形式,集合框架中的所有容器(集合、线性表和图)均支持迭代器。