本文转自JavaGuide
简介
LinkedList是一个实现了List接口和Deque接口的双端链表。 LinkedList底层的链表结构使它支持高效的插入和删除操作,另外它实现了Deque接口,使得LinkedList类也具有队列的特性; LinkedList不是线程安全的,如果想使LinkedList变成线程安全的,可以调用静态类Collections类中的synchronizedList方法:1 | List list=Collections.synchronizedList(new LinkedList(...)); |
1 | private static class Node<E> { |
1 | public LinkedList() { |
1 | public LinkedList(Collection<? extends E> c) { |
1 | public boolean add(E e) { |
1 | /** |
1 | public void add(int index, E element) { |
addAll(Collection c ):将集合插入到链表尾部
1 | public boolean addAll(Collection<? extends E> c) { |
addAll(int index, Collection c): 将集合从指定位置开始插入
1 | public boolean addAll(int index, Collection<? extends E> c) { |
上面可以看出addAll方法通常包括下面四个步骤:
- 检查index范围是否在size之内
- toArray()方法把集合的数据存到对象数组中
- 得到插入位置的前驱和后继节点
- 遍历数据,将数据插入到指定位置
addFirst(E e): 将元素添加到链表头部
1 | public void addFirst(E e) { |
1 | private void linkFirst(E e) { |
addLast(E e): 将元素添加到链表尾部,与 add(E e) 方法一样
1 | public void addLast(E e) { |
根据位置取数据的方法
get(int index): 根据指定索引返回数据
1 | public E get(int index) { |
获取头节点(index=0)数据方法:
1 | public E getFirst() { |
区别:
getFirst(),element(),peek(),peekFirst()
这四个获取头结点方法的区别在于对链表为空时的处理,是抛出异常还是返回null,其中getFirst() 和element() 方法将会在链表为空时,抛出异常
element()方法的内部就是使用getFirst()实现的。它们会在链表为空时,抛出NoSuchElementException
获取尾节点(index=-1)数据方法:
1 | public E getLast() { |
两者区别:
getLast() 方法在链表为空时,会抛出NoSuchElementException,而peekLast() 则不会,只是会返回 null。
根据对象得到索引的方法
int indexOf(Object o): 从头遍历找
1 | public int indexOf(Object o) { |
int lastIndexOf(Object o): 从尾遍历找
1 | public int lastIndexOf(Object o) { |
检查链表是否包含某对象的方法:
contains(Object o): 检查对象o是否存在于链表中
1 | public boolean contains(Object o) { |
删除方法
remove() ,removeFirst(),pop(): 删除头节点
1 | public E pop() { |
removeLast(),pollLast(): 删除尾节点
1 | public E removeLast() { |
区别: removeLast()在链表为空时将抛出NoSuchElementException,而pollLast()方法返回null。
remove(Object o): 删除指定元素
1 | public boolean remove(Object o) { |
当删除指定对象时,只需调用remove(Object o)即可,不过该方法一次只会删除一个匹配的对象,如果删除了匹配对象,返回true,否则false。
unlink(Node1
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
27E 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;
}
remove(int index):删除指定位置的元素
1 | public E remove(int index) { |
LinkedList类常用方法测试
1 | package list; |