赞
踩
LinkedList底层实现上有俩种,一种是基于Node结节;另外一种基于Entry对象
本篇主要介绍基于Node节点的源码分析,有关数据结构和基于Entry对象的源码介绍可查看本人博文
LinkedList源码解析 基于Entry结构
https://blog.csdn.net/ted_cs/article/details/82853009
LinkedList的定义
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
AbstractSequentialList继承了AbstractList并实现了一些方法,其他与ArrayList基本一致就不写了,现在说下Deque这个接口
public interface Deque<E> extends Queue<E> {
//队头插入元素
void addFirst(E e);
//队尾插入元素
void addLast(E e);
//队头插入元素返回是否成功
boolean offerFirst(E e);
//队尾插入元素返回是否成功
boolean offerLast(E e);
//删除头顶元素(当linkedlist为空时抛出异常)
E removeFirst();
//删除尾部元素(当linkedlist为空时抛出异常)
E removeLast();
//删除头顶元素(当linkedlist为空时返回null)
E pollFirst();
//删除尾部元素(当linkedlist为空时返回null)
E pollLast();
//获得头顶元素(当linkedlist为空时抛出异常)
E getFirst();
//获得尾部元素(当linkedlist为空时抛出异常)
E getLast();
//获得头顶元素(当linkedlist为空时返回null)
E peekFirst();
//获得尾部元素(当linkedlist为空时返回null)
E peekLast();
//删除最后一次出现的元素o
boolean removeLastOccurrence(Object o);
//相当于addLast
boolean add(E e);
//相当于add
boolean offer(E e);
//删除头部元素,如果没有可删除的抛出异常
E remove();
//获取并移除此队列的头,如果此队列为空,则返回 null
E poll();
//获取,但是不移除此队列的头。此方法与 peek 唯一的不同在于:此队列为空时将抛出一个异常
E element();
//获取但不移除此队列的头;如果此队列为空,则返回 null
E peek();
//相当于addFirst
void push(E e);
//相当于removeFirst()
E pop();
//移除指定的元素
boolean remove(Object o);
//是否包含指定的元素
boolean contains(Object o);
//获得元素数
public int size();
//获得迭代器
Iterator<E> iterator();
//获得逆向的迭代器
Iterator<E> descendingIterator();
}
3.属性
记住LinkedList是基于双向循环链表设计的
transient int size = 0;
//第一个元素
transient Node<E> first;
//最后一个元素
transient Node<E> last;
//内部类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;
}
}
4.构造器
//创建一个空linkedlist
public LinkedList() {
}
//根据传入的list集合创建一个linkedlist
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
5.解析部分方法源码
5.1 增加方法
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
//把最后一个元素复制给l
final Node<E> l = last;
//根据传入对象创建一个新的node元素
final Node<E> newNode = new Node<>(l, e, null);
//把这个node赋值最后一个元素
last = newNode;
//如果还没插入之前last是null,把first也赋值为newnode
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//下面看看另外一种插入指定位置的add方法
public void add(int index, E element) {
//检查输入的index符不符合要求
checkPositionIndex(index);
//如果传入index刚好在队尾,相当于直接调用add()方法
if (index == size)
linkLast(element);
else
//调用方法插入
linkBefore(element, node(index));
}
//先来看看node方法怎么查找对应的node元素
Node<E> node(int index) {
//二分查找法提高查找速度,如果index小于size的一半,或者大于一半
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;
}
}
//现在来看看linkBefore方法
void linkBefore(E e, Node<E> succ) {
// 把元素插入的index对应的元素之前
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++;
}
5.2 删除方法
//remove方法是删除顶部元素,里面调用了另外的方法
public E remove() {
return removeFirst();
}
//现在我们来看看调用的方法内部是怎么写的
public E removeFirst() {
//里面写的很简单,最主要的还是unlinkFirst方法
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
//再来看看unlinkFirst方法的内部
private E unlinkFirst(Node<E> f) {
// 把对应的元素赋值为null
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
// 让垃圾回收尽快处理掉这个对象
f.next = null;
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
//以下两个方法最后都是调用了unlink方法
public E remove(int index) {
//检查index是否符合要求的方法
checkElementIndex(index);
return unlink(node(index));
}
public boolean remove(Object o) {
//如果为null需要特殊处理
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;
}
//现在来看看unlink方法
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 把传入nude的与上一个node之间的关系清空
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
// 把传入nude的与下一个node之间的关系清空
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 把自己赋值为空,能够更快的垃圾回收
x.item = null;
size--;
modCount++;
return element;
}
5.3 修改方法
public E set(int index, E element) {
//检查index是否符合要求
checkElementIndex(index);
//获得传入index对应的node
Node<E> x = node(index);
//获得修改之前的值
E oldVal = x.item;
//把当前元素赋值为传入的值
x.item = element;
//返回修改之前的值
return oldVal;
}
5.4 查找方法
//有两种查找方法,一种只是获得元素,一种是获得元素并且删除元素
//先来看看获得元素方法,很简单调用了上面讲的node方法
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//另外一种是获得元素并且删除的方法,也很简单调用了上面的删除方法,删除方法会返回元素
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
5.5 迭代器
//迭代器也分为两种,一种是正常顺序迭代,一种是逆向迭代
//先来看看正常顺序迭代的方法,可以看到是调用了自己的一个内部类
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(final int index) {
//看名字就知道是个检查index是否符合要求的方法
rangeCheckForAdd(index);
return new ListItr(index);
}
//下面来详细看看ListItr这个类内部是怎么写的
//方法比较简单,就不多写注释了
private class ListItr implements ListIterator<E> {
//最后一次返回的元素
private Node<E> lastReturned = null;
//下一个元素
private Node<E> next;
//下一个指针
private int nextIndex;
//期待改变次数,保证迭代过程中没有做修改
private int expectedModCount = modCount;
ListItr(int index) {
//赋值初始元素与指针
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
//再来看看逆向迭代的方法,也是创建了一个内部类返回
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
//老样子,来看看内部类的源码,很简单next方法直接调用了itr的previous方法
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
</div>
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。