linkedList是List 接口的链接列表实现类，其底层是链表
1、对linkedList方法的使用(手动编码)2、研究linkedList的源码实现（按照研究思路贴核心代码，贴注解知识，将特点总结）
源码研究思路。 2.1、继承关系
源码如下：
//linkedList继承AbstractSequentialList，AbstractSequentialList类是实现自List接口,对接口中通用的方法做了实现，子类可以不用实现。子类如果有特殊要求可以重写对应方法。 public class linkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable {
linkedList继承AbstractSequentialList，AbstractSequentialList类是实现自List接口,对接口中通用的方法做了实现，子类可以不用实现。子类如果有特殊要求可以重写对应方法。
linkedList实现接口List, Deque, Cloneable,Serializable。
List接口是ArrayList、linkedList的接口，定义了集合中大部分方法。
Deque接口是继承自Queue接口，对Queue接口中通用的方法做了实现，子类可以不用实现。子类如果有特殊要求可以重写对应方法。
Cloneable接口表明当前类可以被克隆。
Serializable接口表明当前类是可以支持序列化和反序列化。
2.2、构造函数
//空参构造
public linkedList() {
}
//通过链表实例来实例化linkedList
public linkedList(Collection c) {
this();
//调用addAll(c)方法
addAll(c);
}
//返回成功与否
public boolean addAll(Collection c) {
//调用addAll(size, c)方法
return addAll(size, c);
}
//布尔类型。从index开始，通过链表实例来实例化linkedList
public boolean addAll(int index, Collection c) {
//调用checkPositionIndex(index)方法判断index是否合法。
checkPositionIndex(index);
//
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
2.3、属性信息
//定义一个头结点：指向第一个节点 transient Nodefirst; //定义一个尾结点：指向最后一个节点 transient Node last; //储存元素个数 transient int size = 0; private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
2.4、默认值或默认属性
//默认元素长度
transient int size = 0;
public linkedList() {
}
public linkedList(Collection c) {
this();
addAll(c);
}
//链接e作为第一个元素
private void linkFirst(E e) {
final Node f = first;
final Node newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
//链接e作为最后一个元素
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//在非空节点succ之前插入元素e
void linkBefore(E e, Node succ) {
// assert succ != null;
final Node pred = succ.prev;
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
//解除第一个非空节点f的链接。
private E unlinkFirst(Node f) {
// assert f == first && f != null;
final E element = f.item;
final Node next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
//取消最后一个非空节点L的链接。
private E unlinkLast(Node l) {
// assert l == last && l != null;
final E element = l.item;
final Node prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
//解除非空节点x的链接。
E unlink(Node x) {
// assert x != null;
final E element = x.item;
final Node next = x.next;
final Node 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;
}
2.5、底层数据结构
底层数据结构是链表。
2.6、常用方法研究 //返回列表中的第一个元素。
public E getFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
//返回列表中的最后一个元素。
public E getLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
//移除并返回列表中的第一个元素。
public E removeFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
//移除并返回列表中的最后一个元素
public E removeLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
//在列表的开头插入指定的元素。
public void addFirst(E e) {
linkFirst(e);
}
//将指定的元素追加到列表的末尾。
public void addLast(E e) {
linkLast(e);
}
//如果列表中包含指定的元素，则返回 true
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//返回列表中元素的个数。
public int size() {
return size;
}
//将指定的元素追加到列表的末尾。
public boolean add(E e) {
linkLast(e);
return true;
}
//链接e作为最后一个元素
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
protected transient int modCount = 0;
//从列表中删除指定元素的第一次出现.更正式地说，删除索引最低的元素
public boolean remove(Object o) {
if (o == null) {
for (Node x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//将指定集合中的所有元素追加到末尾
public boolean addAll(Collection c) {
return addAll(size, c);
}
//将指定集合中的所有元素插入到此列表，从指定位置开始。
public boolean addAll(int index, Collection c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
//从列表中删除所有元素。
public void clear() {
//
for (Node x = first; x != null; ) {
Node next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
//返回列表中指定位置的元素。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//将列表中指定位置的元素替换为指定元素。
public E set(int index, E element) {
checkElementIndex(index);
Node x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//在列表的指定位置插入指定的元素。移动元素当前在该位置(如果有)和任何右边的后续元素(在它们的下标上加1)。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//移除列表中指定位置的元素。任何变化左边的后续元素(从索引中减去1)。返回从列表中删除的元素。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//解除第一个非空节点f的链接。
private E unlinkFirst(Node f) {
// assert f == first && f != null;
final E element = f.item;
final Node next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
//取消最后一个非空节点l的链接。
private E unlinkLast(Node l) {
// assert l == last && l != null;
final E element = l.item;
final Node prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
//判断下标是否合法
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
