LinkedList
当比较LinkedList和ArrayList的区别时我们也许知道前者底层实现是链表,后者底层实现是数组,对于ArrayList在【此文】中详细介绍了,但是对于LinkedList的理解仅仅局限在链表而已,现在一起来看看它的底层实现吧!
类图
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
我们发现LinkedList实现了Deque
接口,它提供了对队列操作的相关方法。所以我们经常使用LinkedList去完成队列相关操作。
类前注释
双向链表实现了List
和Dqeue
接口,它实现了所有的可选列表操作,它允许所有的元素类型,包括null
。
注意:LinkedList是非线程安全的。如果多个线程同时访问链接列表,并且至少有一个线程在结构上修改列表,则必须在外部进行同步。 (结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。)这通常通过在自然封装列表的对象上进行同步来实现。 如果没有这样的对象存在,列表应该使用Collections.synchronizedList
方法“包装”。 这最好在创建时完成,以防止意外的不同步访问列表。
LinkedList的iterator和listIterator方法返回的迭代器是fail-fast
的:如果列表在迭代器创建之后的任何时间被结构化地修改,除了通过迭代器自己的remove或add方法之外,迭代器将会抛出ConcurrentModificationException
。 因此,面对并发修改,迭代器将快速而干净地失败,而不是在未来未确定的时间冒着任意的非确定性行为。
Node节点
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;
}
}
看到next
和prev
就知道LinkedList不是单链表,是双向链表。
成员变量
transient int size = 0; //记录LinkedList的大小
transient Node<E> first; //表示LinkedList的头节点。
transient Node<E> last; //表示LinkedList的尾节点。
构造方法
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
LinkedList提供两个构造方法,其中需要注意的是第二个,它接受一个Collection来完成初始化。关键在于addAll
方法。
public boolean addAll(Collection<? extends E> c) {
//addAll方法可以在指定索引的节点后面插入Collection中的元素,初始化时size为0,即从头开始插入
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
//检查index是否合法,判断规则:index >= 0 && index <= size;
//不合法抛出IndexOutOfBoundsException
checkPositionIndex(index);
//将Collection转为数组
Object[] a = c.toArray();
int numNew = a.length;
//插入的集合为空,直接返回false
if (numNew == 0)
return false;
//pred:index索引节点的前驱
//succ:index索引表示的节点
Node<E> pred, succ;
if (index == size) {
//在最末端插入节点
succ = null;
pred = last;
} else {
//添加位置在链表中
//node()方法用于寻找index索引表示的节点
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)
//pred为null说明链表中无节点
first = newNode;
else
pred.next = newNode;//设置前驱的后继
//③、更新前驱
pred = newNode;
}
//④、链接成完整链表
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
//更新链表的size
size += numNew;
modCount++;
return true;
}
linkFirst
私有方法,插入一个元素,并将它置为头节点。
private void linkFirst(E e) {
//备份头节点
final Node<E> f = first;
//创建新节点
final Node<E> newNode = new Node<>(null, e, f);
//将新节点设置为头节点
first = newNode;
if (f == null)
//f为空说明链表为空,插入的这个节点也是尾节点
last = newNode;
else
//设置原来头节点的前驱为新节点
f.prev = newNode;
size++;
modCount++;
}
linkLast
插入一个元素,并将它置为尾节点。
void linkLast(E e) {
//备份尾节点
final Node<E> l = last;
//创建新节点
final Node<E> newNode = new Node<>(l, e, null);
//将新节点设置为尾节点
last = newNode;
if (l == null)
//f为空说明链表为空,插入的这个节点也是头节点
first = newNode;
else
//设置原来尾节点的后继为新节点
l.next = newNode;
size++;
modCount++;
}
getFirst
重写来自Deque
的方法,返回头节点,如果头节点为null抛出异常。
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
getLast
重写来自Deque
的方法,返回尾节点,如果尾节点为null抛出异常。
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
removeFirst
重写来自Deque
的方法,删除头节点并返回旧值,如果头节点为null抛出异常。
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
// 断言 f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;//将数据域和后继设为null,GC帮助销毁
f.next = null; // help GC
//重新设置头节点
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
removeLast
重写来自Deque
的方法,删除尾节点并返回旧值,如果尾节点为null抛出异常。
remove
删除等于指定元素的第一次出现的节点。删除成功返回true
,失败返回false
。
addFirst
重写来自Deque
的方法,从头部添加节点。借助linkFirst
方法完成此方法。
addLast
重写来自Deque
的方法,从尾部添加节点。借助linkLast
方法完成此方法。
add
往链表中添加节点,从尾部插入。offer
方法调用此方法实现尾插功能。
clear
清空整个链表。其实就是遍历整个链表,将数据域,前驱,后继置为null。
public void clear() {
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++;
}
get
获取指定索引的元素值。
public E get(int index) {
//判断索引的合法性
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
//如果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;
}
}
set
为指定索引的节点设置值,返回旧值。
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
indexOf
返回此列表中指定元素的第一次出现的索引,如果此列表不包含元素,则返回-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;
}
与indexOf
相似的还有lastIndexOf
这一方法,它返回此列表中指定元素的最后一次出现的索引,如果此列表不包含元素,则返回-1。
contains
查找链表中是否有知道的元素值,返回对应的索引(第一次出现的位置),使用indexOf
实现此方法。
public boolean contains(Object o) {
return indexOf(o) != -1;
}
peek
返回头节点的值,如果头节点为null则返回null。
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
与之类似的方法还有element
,但是不同的是如果链表为空则抛出NoSuchElementException
。
peekLast
返回尾节点的值,如果头节点为null则返回null。
poll
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
出队操作,返回队首元素值。
push和pop
push
方法从头部插入元素,pop
从头部删除元素。常使用这两个方法实现栈操作。
迭代器
LinkedList为我们提供了两种迭代器,分别为ListIterator
和DescendingIterator
。使用ListIterator
迭代器我们可以完成遍历,删除和修改节点的操作,同时这也是官方推荐我们遍历链表的方式,而不是使用fori
遍历链表。使用ListIterator
我们不仅可以正向遍历链表也可以反向遍历。
descendingIterator
方法来自Deque
接口,使用DescendingIterator
我们只能从后向前遍历,并且只提供删除操作,无法添加和修改节点。
clone
同ArrayList
一样,LinkedList
的clone方法实现的是浅拷贝。
toArray
此方法将链表中的值放在数组中,并将数组返回。
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
使用此方法不能讲Object[]强转为其他类型,否则抛ClassCastException
异常。如果我们需要实现将链表值放在指定类型数组中使用toArray(T[] a)
方法。不过这里有个小坑哦!
public <T> T[] toArray(T[] a) {
//如果你传入的数组a不够大会新建一个数组对象赋给a,
//后序会将值赋值给新创建的数组对象,那么原来的那个数组将没有值,全为null
//所以我们还是统一使用返回的数组就不会错了
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
版权属于:带翅膀的猫
本文链接:https://www.chengpengper.cn/archives/42/
转载时须注明出处及本声明