一、LinkedList概述：
LinkedList与ArrayList一样，是实现了List接口。由于LinkedList是基于链表实现的，所以它执行插入和删除操作时比ArrayList更高效，而随机访问的性能要比ArrayList低。
二、LinkedList的实现：
1、构造方法
|
1
2
3
4
5
6
7
8
|
//构造一个空的LinkedListpublic LinkedList() {}//接收一个Collection参数c，默认构造方法构造一个空的链表，并通过addAll将c中的元素全部添加到链表中。public LinkedList(Collection<? extends E> c) { this(); addAll(c);} |
2、一些方法
2.1 getFirst()
|
1
2
3
4
5
6
7
|
//获取LinkedList第一个元素，如果LinkedList为空，则抛出异常。 public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } |
2.2 getLast()
|
1
2
3
4
5
6
7
|
//获取getLast()最后一个元素，如果LinkedList为空，则抛出异常。 public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } |
2.3 removeFirst()
|
1
2
3
4
5
6
7
|
//删除LinkedList第一个元素，如果LinkedList为空，则抛出异常。 public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } |
2.4 removeLast()
|
1
2
3
4
5
6
7
|
//删除LinkedList最后一个元素，如果LinkedList为空，则抛出异常。 public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } |
2.5 addFirst(E e)
|
1
2
3
4
|
//在LinkedList开始的位置插入一个新元素。 public void addFirst(E e) { linkFirst(e); } |
2.6 addLast(E e)
|
1
2
3
4
|
//在LinkedList末尾的位置插入一个新的元素。 public void addLast(E e) { linkLast(e); } |
2.7 contains(Object o)
|
1
2
3
4
|
//判断LinkedList中是否包含某个元素，若包含返回True，否则返回False public boolean contains(Object o) { return indexOf(o) != -1; } |
2.8 add(E e)
|
1
2
3
4
5
|
//在LinkedList末尾处添加一个新的元素。 public boolean add(E e) { linkLast(e); return true; } |
2.9 remove(Object o)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
//删除LinkedList中第一个出现的指定元素，如果LinkedList中不包含该元素，则链表保持不变。public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } |
2.10 addAll()
|
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
|
//增加Collection中的所有元素， public boolean addAll(Collection<? extends E> c) { return addAll(size, c); }//index参数指定collection中插入的第一个元素的位置 public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; } |
2.11 clear()
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
//删除LinkedList中的所有元素。 public void clear() { //删除LinkedList中所有链接是没有必要的，但是： // 可以帮助分代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++; } |
2.12 get(int index)
|
1
2
3
4
5
|
//获取指定位置的节点 public E get(int index) { checkElementIndex(index); return node(index).item; } |
2.13 set(int index, E element)
|
1
2
3
4
5
6
7
8
|
//给指定节点赋一个指定的值，替换原来的值。 public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; } |
2.14 add(int index, E element)
|
1
2
3
4
5
6
7
8
9
|
//在指定位置插入一个指定的值，原来该位置上以后的节点依次向后移动一位。 public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } |
2.15 remove(int index)
|
1
2
3
4
5
|
//删除指定位置的值，该位置之后的节点依次向前移动一位。 public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } |
三、总结
LinkedList，通俗的理解就是数据结构中讲的链表在Java语言中的实现，所以在链表中所有操作，LinkedList中都有，其实现原理也都是基于数据结构中所讲的对链表中的节点插入、删除、移动等方法。
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/wangshuang1631/article/details/52949638
