此源码分析JDK版本为1.7,只是简单分析,算是个人看源码的一点小总结,随意性比较强,专业的还需百度。
先简单介绍一下LinkedList,LinkedList为直线型的链表结构,时间复杂度为O(n)。ArrayList内部存储为数组,LinkedList内部存储为节点Node。以下所有表达LinkedList的内容统称为链表。
简介
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}
属性
//链表大小
transient int size = 0;
//链表头部节点
transient Node<E> first;
//链表尾部节点
transient Node<E> last;
构造方法
//无初始化集合构造方法
public LinkedList() {
}
//初始化集合构造方法
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
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;
}
}
方法
//将值放置第一个节点(私有),此方法可发现增加效率比ArrayList高很多,无需移动其他节点
private void linkFirst(E e) {
//将链表第一个节点地址赋予f
final Node<E> f = first;
//创建节点对象
final Node<E> newNode = new Node<>(null, e, f);
//将新的节点对象地址赋予first
first = newNode;
//如果f为空,则说明之前链表没有节点
if (f == null)
//最后一个节点即第一个节点
last = newNode;
else
//f不为空,则f的上一个节点为第一个节点(节点f由第一个变为第二个)
f.prev = newNode;
//大小+1
size++;
//修改次数+1
modCount++;
}
//将值放置最后一个节点(default,该类及同包可使用),add()会调用该方法,此方法可发现增加效率比ArrayList高很多,无需移动其他节点
void linkLast(E e) {
//将链表第一个节点地址赋予l
final Node<E> l = last;
//创建节点对象
final Node<E> newNode = new Node<>(l, e, null);
//将新的节点对象地址赋予last
last = newNode;
//如果l为空,则说明之前链表没有节点
if (l == null)
//第一个节点即最后一个节点
first = newNode;
else
//l不为空,则l的下一个节点为最后一个节点(节点l由倒数第一个变为倒数第二个)
l.next = newNode;
//大小+1
size++;
//修改次数+1
modCount++;
}
//在succ节点前加入e(default,该类及同包可使用),add()方法会调用该方法,此方法可发现增加效率比ArrayList高很多,无需移动其他节点
void linkBefore(E e, Node<E> succ) {
//succ不能为null(方法声明为default,则说明不为null的话,succ一定存在于该链表)
// assert succ != null;
//succ的上一个节点赋予pred
final Node<E> pred = succ.prev;
//创建节点对象(上个节点:pred,当前节点:e,下一个节点:succ)
final Node<E> newNode = new Node<>(pred, e, succ);
//将新的节点对象赋予为succ的上一个节点
succ.prev = newNode;
//pred为null则说明succ为第一个节点
if (pred == null)
//将新的节点对象作为第一个节点
first = newNode;
else
//pred不为null则说明不是第一个对象,将新的节点对象作为pred的下一个对象
pred.next = newNode;
//大小+1
size++;
//修改次数+1
modCount++;
}
//删除第一个节点(私有),remove(),removeFirst()会调用此方法, 此方法可发现移出效率比ArrayList高很多,无需移动其他节点
private E unlinkFirst(Node<E> f) {
//f不能为null并且f必须是第一个节点
// assert f == first && f != null;
//获取当前节点f的值
final E element = f.item;
//获取当前节点f的下一个节点
final Node<E> next = f.next;
//将当前节点f置null
f.item = null;
//将f下个节点置null
f.next = null; // help GC
//将next赋予第一个节点
first = next;
//如果next为null则说明该链表只有f一个节点
if (next == null)
//将last置null
last = null;
else
//如果next不为null则说明该链表不止一个节点,将next的上一个节点置null(此时next为第一个节点)
next.prev = null;
//大小-1
size--;
//修改次数+1
modCount++;
return element;
}
//删除最后一个节点(私有),此方法可发现移出效率比ArrayList高很多,无需移动其他节点
private E unlinkLast(Node<E> l) {
//l不能为null并且l必须是最后一个节点
// assert l == last && l != null;
//获取当前节点l的值
final E element = l.item;
//获取当前节点l的上一个节点
final Node<E> prev = l.prev;
//将当前节点l的值置null
l.item = null;
//将l下个节点置null
l.prev = null; // help GC
//将prev赋予最后一个节点
last = prev;
//如果prev为null则说明该链表只有f一个节点
if (prev == null)
//将first 置null
first = null;
else
//如果prev不为null则说明该链表不止一个节点,将prev的下一个节点置null(此时prev为最后一个节点)
prev.next = null;
//大小-1
size--;
modCount++;
//修改次数+1
return element;
}
//移出x节点(default,该类及同包可使用),remove(index/o)会调用此方法,此方法可发现增加效率比ArrayList高很多,无需移动其他节点
E unlink(Node<E> x) {
//x不能为null(方法声明为default,则说明不为null的话,succ一定存在于该链表)
// assert x != null;
//将节点x的值赋予element
final E element = x.item;
//将节点x的下个节点赋予next
final Node<E> next = x.next;
//将节点x的上个节点赋予prev
final Node<E> prev = x.prev;
//当prev为null,说明x节点为第一个节点
if (prev == null) {
//将next赋予为第一个节点
first = next;
} else {
//当prev不为null,说明x节点为中间节点,将下个节点赋予为上个节点的下个节点
prev.next = next;
//x节点的下个节点置null
x.prev = null;
}
//当next为null,说明x节点为最后一个节点
if (next == null) {
//将prev赋予为最后一个节点
last = prev;
} else {
//当next不为null,说明x节点为中间节点,将上个节点赋予为上个节点的上个节点
next.prev = prev;
//x节点的上个节点置null
x.next = null;
}
//x节点的值置null
x.item = null;
//大小-1
size--;
//修改次数+
modCount++;
return element;
}
//获取第一个节点的值
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
//获取最后一个节点的值
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
//移除第一个节点的值
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
//调用unlinkFirst()方法
return unlinkFirst(f);
}
//移除最后一个节点值
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
//调用unlinkLast()方法
return unlinkLast(l);
}
//将值放置第一个节点
public void addFirst(E e) {
//调用linkFirst()方法
linkFirst(e);
}
//将值放置最后一个节点
public void addLast(E e) {
//调用linkLast()方法
linkLast(e);
}
//获取元素的第一个下标
public int indexOf(Object o) {
int index = 0;
//如果o为null,则遍历所有节点查询(说明LinkedList是支持null值的)
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
//因为LinkedList为链表结构,没有下标,因为临时index充当下标(index是从0开始,因此应该后++)
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
//因为LinkedList为链表结构,没有下标,因为临时index充当下标(index是从0开始,因此应该后++)
index++;
}
}
//无该值
return -1;
}
//获取元素的最后一个下标
public int lastIndexOf(Object o) {
int index = size;
//如果o为null,则遍历所有节点查询(说明LinkedList是支持null值的)
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
//因为LinkedList为链表结构,没有下标,因为临时index充当下标(index是从0开始,因此应该先--)
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
//因为LinkedList为链表结构,没有下标,因为临时index充当下标(index是从0开始,因此应该先--)
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
//是否包含值
public boolean contains(Object o) {
//indexOf()方法解析可发现此方法会遍历所有,因此应当尽可能少使用
return indexOf(o) != -1;
}
//返回链表大小
public int size() {
return size;
}
//增加值
public boolean add(E e) {
//默认在最后增加节点()
linkLast(e);
return true;
}
//删除值
public boolean remove(Object o) {
//如果值为null,则删除第一个值为null的节点
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
//调用unlink()方法
unlink(x);
return true;
}
}
} else {
//如果值不为null,则删除第一个值为o的节点
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
//调用unlink()方法
unlink(x);
return true;
}
}
}
return false;
}
//参数是否为现有元素的索引
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
//是否是迭代器或添加操作的有效位置的索引
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
//检查是否为现有元素的索引
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//检查是否为迭代器或添加操作的有效位置的索引(最大现有元素下标+1)
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//根据下标获取节点 (类似二分查询法)
Node<E> node(int index) {
//应当保证是有值下标,但是并没有保证
// assert isElementIndex(index);
//如果index小于size的一半,则通过x.next
if (index < (size >> 1)) {
//从first开始next
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//如果index大于等于size,则通过x.prev
//从last开始next
Node<E> x = prev;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//在index之后加入集合
public boolean addAll(int index, Collection<? extends E> c) {
//检查下标是否为添加操作的有效位置的索引
checkPositionIndex(index);
//转换为数组
Object[] a = c.toArray();
//数组a的长度
int numNew = a.length;
//如果数组长度为0则返回false
if (numNew == 0)
return false;
//新建pred(上一个节点)、succ(下一个节点)
Node<E> pred, succ;
//如果index和链表长度相同,则说明要在最后的位置加入节点
if (index == size) {
//下一个节点为null
succ = null;
//上一个节点为链表最后一个节点
pred = last;
} else {
//如果index和链表长度不相同,则说明要在中间位置加入节点
//将当前下标节点赋予succ节点(下一个节点)
succ = node(index);
//将当前下标节点的上一个节点赋予pred节点(上一个节点)
pred = succ.prev;
}
//遍历数组a
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//新建一个对象(当前节点:pred,上一个节点:e,下一个节点:null)
Node<E> newNode = new Node<>(pred, e, null);
//如果pred为null则说明要在第一个节点前加入此节点
if (pred == null)
//将新节点赋予first
first = newNode;
else
//如果pred不为null则说明要在中间位置加入此节点
//将新节点赋予上个节点的下个节点
pred.next = newNode;
//将当前节点赋予上个节点
pred = newNode;
}
//如果index下标的节点为null,则index是链表大小(上方判断)
if (succ == null) {
//将上一个节点赋予last
last = pred;
} else {
//如果index下标的节点不为null,则将该节点赋予为上个节点的下个节点
pred.next = succ;
//将上个节点赋予index下标的上个节点
succ.prev = pred;
}
//size + 数组长度
size += numNew;
//修改次数+1
modCount++;
return true;
}
//在最后加入集合
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
//清空链表
public void clear() {
//清除节点之间的所有链接是“不必要的”,但如果丢弃的节点居住在一代以上,即使有一个可到达的迭代器,也肯定会释放内存,这有助于一代GC。
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
//遍历去除强引用,使gc下次回收
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
//去除强引用,使gc下次回收
first = last = null;
//大小置
size = 0;
//修改次数+1
modCount++;
}
//根据下标获得值
public E get(int index) {
//检查下标是否为有值下标
checkElementIndex(index);
//node(index)查询节点,然后返回值
return node(index).item;
}
//在下标处设置值
public E set(int index, E element) {
//检查下标是否为有值下标
checkElementIndex(index);
//根绝小标获取节点
Node<E> x = node(index);
//旧值
E oldVal = x.item;
//新值
x.item = element;
//返回旧值
return oldVal;
}
//在下标处添加值
public void add(int index, E element) {
//检查下标是否为添加操作的有效位置的索引
checkPositionIndex(index);
//如果下标等于链表大小,则说明加入在最后
if (index == size)
//将值加入在最后
linkLast(element);
else
//如果下标不等于链表大小则说明要在该下标之前加入
linkBefore(element, node(index));
}
//移除下标对应的节点
public E remove(int index) {
//检查下标是否为有值下标
checkElementIndex(index);
//移除该节点
return unlink(node(index));
}
//返回第一个节点,但不删除,如果为null则返回null
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//返回第一个节点,如果为null则返回null,与peek()无区别
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//返回最后一个节点的值
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
//返回第一个节点的值(如果为空链则异常,与getFirst()无区别)
public E element() {
//调用getFirst()
return getFirst();
}
//查询第一个节点的值并删除(简而言之:出栈)
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//查询第一个节点的值并删除(简而言之:出栈,与pollFirst()无区别)
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//查询最后一个节点的值并删除
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
//查询最后一个节点的值并删除
public E remove() {
return removeFirst();
}
//添加到最后一个节点(不知道与add(o)有什么区别)
public boolean offer(E e) {
return add(e);
}
//添加到第一个节点(与addFirst(o)无区别)
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//添加到最后一个节点(与addLast(o)无区别)
public boolean offerLast(E e) {
addLast(e);
return true;
}
//添加到第一个节点(简而言之:入栈)
public void push(E e) {
addFirst(e);
}
//返回值并删除第一个节点(简而言之:出栈)
public E pop() {
return removeFirst();
}
//删除第一个值为o的节点
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
//删除最后一个值为o的节点
public boolean removeLastOccurrence(Object o) {
//判断o是否为null
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
//删除该节点
unlink(x);
return true;
}
}
} else {
//如果o不为null
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
//删除该节点
unlink(x);
return true;
}
}
}
return false;
}
//获取迭代器
public ListIterator<E> listIterator(int index) {
//检查是否为迭代器或添加操作的有效位置的索引
checkPositionIndex(index);
返回迭代器
return new ListItr(index);
}
//转换为数组(与ArrayList不同,ArrayList是通过JNI调用本地方法,LinkedList是自己转换)
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;
}
//将链表的值放入数组a中
public <T> T[] toArray(T[] a) {
//如果a数组的大小小于链表大小
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
//将数组a的地址赋予result
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
//将链表的数据放入result中
result[i++] = x.item;
//如果数组a的长度是大于链表大小的,则将a[size]置为null(之前的操作并不会遍历到size下标)
if (a.length > size)
a[size] = null;
//返回数组a(操作result即操作a吗,因为a的地址赋予给了result)
return a;
}
总结
1.LinkedList允许存在重复的值
2.LinkedList允许存在多个null值
3.remove(o)只会删除第一个o值
4.indexOf(o)只会返回第一值为o的下标
5.尽量减少使用查询的行为,因为查询行为是遍历所有,时间复杂度为O(n)
6.查询少,修改多的地方可使用 例:栈(完美)
7.虽说LinkedList更适合修改场景,但是每次修改是都会通过node(index)进行查询,所以效率还是会有所降低,不过不可避免
8.通过add(),remove()方法可发现修改场景为:node(查询节点,然后增加一个节点即可)
9.add(),addLast(),offer(),offerLast()是一样的
网友评论