Java的LinkedList源码（一）
只贴出了一部分源码，并不是所有方法的源码，后续更新get和addAll，大部分代码现在已贴出，如有不对的地方还请指正。package collection;
import java.util.AbstractSequentialList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Queue;
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
/**
* LinkedList的长度
* transient：只能用来修饰字段，在对象序列化的过程中，带有此修饰符修饰的字段是不会被序列化的
* 例如：User类有userName和transient password，那么序列化User类的时候password是不会被序列化的，
* 所以反序列化拿出password也是null
*/
transient int size = 0;
/**
* 指针头部
*/
transient Node<E> first;
/**
* 指针尾部
*/
transient Node<E> last;
/**
* 空构造器
*/
public LinkedList() {
}
/**
* 在链表头部插入元素
*/
private void linkFirst(E e) {
//先保存当前头节点
final Node<E> f = first;
//创建一个新节点，此新节点的上一个节点为null，下一个节点为当前头节点
final Node<E> newNode = new Node<>(null, e, f);
//让first指向新节点（更新头节点，这样可以保证对链表进行更改操作时first永远是第一个节点）
first = newNode;
//如果链表为null，则将last指向这唯一的新节点
if (f == null)
last = newNode;
else //如果链表不为null，则将链表原来头节点的上一个元素指向新节点
f.prev = newNode;
size++;
modCount++;
}
/**
* 在链表尾部添加元素
*/
void linkLast(E e) {
//先保存当前尾节点
final Node<E> l = last;
//创建新节点，新节点的前驱(上一个节点)为当前尾节点，后驱为null
final Node<E> newNode = new Node<>(l, e, null);
//将链表尾节点指向新节点（更新尾节点，这样可以保证对链表进行更改操作时last永远是最后一个节点）
last = newNode;
//如果链表尾节点（指向新节点之前）为null，则将链表头节点指向新节点
if (l == null)
first = newNode;
else //否则将链表尾节点（指向新节点之前）的上下一个节点指向新节点
l.next = newNode;
size++;
modCount++;
}
/**
* 向链表中间插入元素
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
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++;
}
/**
* 移除链表头元素, f:链表头元素，从其他方法调用传参而来
* f不可为null，调用此方法的地方都已判断
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//将element指向链表头节点的元素值
final E element = f.item;
//将next指向链表头节点的下一个节点
final Node<E> next = f.next;
//将链表头节点赋值为null
f.item = null;
//将链表头节点的下一个节点指向为null，有助于GC回收
f.next = null; // help GC
//将链表头节点first指向为next（目的是为了数据的正确性，删除此元素，要保证first指向下一个元素，不能指向当前删除的这个）
first = next;
//如果链表只有1个元素，则将last指向null，变成空链表
if (next == null)
last = null;
else //否则将链表的上一个元素指向null
next.prev = null;
//长度减1
size--;
modCount++;
//返回被移除的元素
return element;
}
/**
* 移除链表尾元素, l:链表尾元素，从其他方法调用传参而来
* l不可为null，调用此方法的地方都已判断
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
//将链表尾节点的元素值赋给element
final E element = l.item;
//找到链表尾节点的上一个节点
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
//last指向前一个元素
last = prev;
//若前一个元素为null，则证明链表只有l这一个元素，则将first设置为null，变成空链表
if (prev == null)
first = null;
else //否则删除此元素
prev.next = null;
size--;
modCount++;
//返回删除的这个元素
return element;
}
/**
* 从链表中间删除节点
*/
E unlink(Node<E> x) {
// assert x != null;
//找到当前节点本身，上一个节点和下一个节点
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//前驱为空，说明删除的是头节点，first要指向下一个节点
if (prev == null) {
first = next;
} else { //否则前驱节点的后继节点变为当前删除节点的下一个节点
prev.next = next;
x.prev = null;
}
//后驱为空，说明删除的是尾节点，last要指向前一个节点
if (next == null) {
last = prev;
} else { //否则后驱节点的上一个节点变为当前删除的上一个节点
next.prev = prev;
x.next = null;
}
//将此元素设置为null
x.item = null;
size--;
modCount++;
//返回删除的元素
return element;
}
/**
* 获取链表第一个节点
*/
public E getFirst() {
//将节点f指向链表头节点
final Node<E> f = first;
//如果链表头节点为null，则抛出没有此元素的异常，否则返回此元素
if (f == null)
throw new NoSuchElementException();
return f.item;
}
/**
* 获取链表最后一个节点
*/
public E getLast() {
//将节点l指向链表尾节点
final Node<E> l = last;
//如果链表尾节点为null，则抛出没有此元素的异常，否则返回此元素
if (l == null)
throw new NoSuchElementException();
return l.item;
}
/**
* 移除链表头节点
*/
public E removeFirst() {
//将节点f指向链表头节点
final Node<E> f = first;
//如果链表头节点为null，则抛出没有此元素的异常，否则移除此元素，并返回移除的元素
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/**
* 移除链表尾节点
*/
public E removeLast() {
//将节点f指向链表尾节点
final Node<E> l = last;
//如果链表尾节点为null，则抛出没有此元素的异常，否则移除此元素，并返回移除的元素
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* 向链表头部插入节点
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* 向链表尾部插入节点
*/
public void addLast(E e) {
linkLast(e);
}
/**
* 判断元素是否在链表中。true：在。false：不在
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
/**
* 返回链表长度
*/
public int size() {
return size;
}
/**
* 向链表尾部插入元素，成功则返回true
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 移除链表中的某元素，true：成功，false：失败
*/
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;
}
/**
* 返回元素在链表中第一次出现的位置下标，若不存在，则返回-1
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {//当元素为null时，防止空指针，null用等于判断，非null的字符串用equals
//遍历
for (Node<E> x = first; x != null; x = x.next) {
//链表节点元素中存在null，则返回位置
if (x.item == null)
return index;
index++;
}
} else { //当元素不为null时
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
/**
* 返回元素在链表中最后一次出现的位置下标，若不存在，则返回-1
*/
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
/*
* 链表上的每个节点
*/
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;
}
}
}
膜拜大神 http://www.heniyi.com/img/dot.jpg这个厉害，还有二？ bushi hendong Eclipse
Ctrl + 左键啊 好的，多谢楼主 江南5753 发表于 2016-12-2 11:56
这个厉害，还有二？
这个不全，只是写了常用的，可以看出来LinkedList移动元素很方便，效率很高，但是我并没有写get的，get的效率很低下了，打算在后续文章中写出，并与之前写的ArrayList的做对比。
页:
[1]