一、签名
|
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable |
1. 继承了AbstractSequentialList<>
2. 实现了Deque：出现在1.6，继承了Queue。双端队列容器，不仅可以在尾部插入，删除元素，还可以在头部插入和删除元素。
3. Clone:可以克隆
4. Serializable：可被序列化
二、成员变量
trainsient int size = 0; |
Transient Node<E> first; // 记录第一个。 |
Transient Node<E> last; // 只记录当前的节点，也是最后一个 |
protected transient int modCount = 0; //记录当前对LinkedList修改的次数 |
|
private static class Node<E> { E item; Node<E> next; Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } |
三、构造方法
|
public LinkedList() { } |
|
public LinkedList(Collection<? extends E> c) { this(); addAll(c); } |
四、成员方法
1.1 .add(E e)
|
public boolean add(E e) { linkLast(e); return true; } |
|
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++; } |
1.2 add(intindex,E element)
|
public void add(int index, E element) { checkPositionIndex(index);
if (index == size) // 如果插入的位置是最后一个， linkLast(element); else linkBefore(element, node(index)); } |
void linkLast(E e) 见上 |
|
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++; } |
1.3 push();
|
public void push(E e) { addFirst(e); // 不知道为什么 不直接使用linkFirst(e) } |
|
public void addFirst(E e) { linkFirst(e); } |
|
private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f);//注意linkLast的不同之处。 first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } |
2.1.remove()
|
public E remove() { return removeFirst(); } |
|
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(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; } |
2.2 removeFirst()
2.3 removeLast()
2.4 remove(intindex)
|
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } |
|
Node<E> node(int index) { // assert isElementIndex(index);
if (index < (size >> 1)) { // 二分查找。 Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return 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; } |
2.5 public E pop()
|
public E pop() { return removeFirst(); } |
3.1 public E set(int index,E element)
|
public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; } |
4.1 publicE get(int index)
|
public E get(int index) { checkElementIndex(index); return node(index).item; } |
4.2 publicE peekFirst()
|
public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; } |
4.3 publicE peekLast()
|
public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; } |
5. publicBoolean contains(Object o)
|
public boolean contains(Object o) { return indexOf(o) != -1; } |
|
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; } |
6. publicvoid clear()
|
public void clear() { // 将所有都置为null，help GC for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; } |
五、遍历方式
1. for
2. fori
3. iterator()
总结：
1. 原理是链表。
2. 有序
3. 非线程安全
4. 元素允许为null
5. 遍历时候for,都会调用node(index)方法。
6. 效率问题：
很多文章都再说，arrayList查找快，增删慢，LinkedList增删快，查找慢。
这种说法不准确：
（1）LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址
（2）ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址
所以，如果待插入、删除的元素是在数据结构的前半段尤其是非常靠前的位置的时候，LinkedList的效率将大大快过ArrayList，因为ArrayList将批量copy大量的元素；越往后，对于LinkedList来说，因为它是双向链表，所以在第2个元素后面插入一个数据和在倒数第2个元素后面插入一个元素在效率上基本没有差别，但是ArrayList由于要批量copy的元素越来越少，操作速度必然追上乃至超过LinkedList。
从这个分析看出，如果你十分确定你插入、删除的元素是在前半段，那么就使用LinkedList；如果你十分确定你删除、删除的元素在比较靠后的位置，那么可以考虑使用ArrayList。如果你不能确定你要做的插入、删除是在哪儿呢？那还是建议你使用LinkedList吧，因为一来LinkedList整体插入、删除的执行效率比较稳定，没有ArrayList这种越往后越快的情况；二来插入元素的时候，弄得不好ArrayList就要进行一次扩容，记住，ArrayList底层数组扩容是一个既消耗时间又消耗空间的操作，