LinkedList
目录
一、基本结构
// 元素的个数 （链表长度）
transient int size = 0;
// 头结点
transient Node<E> first;
// 尾结点
transient Node<E> last;
//节点类 定义如下
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;
}
}
从上面源代码可知，底层结构是链表，而且是一个双向链表，这也就意味着不会再有容量的限制，没了扩容操作，但自身不仅仅实现了List相关操作还实现了Deque相关操作，我们以List操作为主
二、add操作
采用尾插法，尾部为空时说明链表为空，新节点会同时成为尾节点和头节点，尾部不为空，就把尾结点指向到新节点，最后链表长度+1
源代码如下：
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
// 新建一个节点
final Node<E> newNode = new Node<>(l, e, null);
// 尾部插入 新节点直接成为尾部节点
last = newNode;
// 判断之前链表尾部是否为空
if (l == null)
// 为空说明链表内还没节点 新节点直接作为头节点
first = newNode;
else
// 不为空说明链表已经有节点了 把原尾部节点指向到下一个新节点
l.next = newNode;
// 元素个数+1（链表长度+1）
size++;
modCount++;
}
因为是list所以同样可以直接指定位置插入元素，操作也很简单，先找到原来的节点，然后把新节点放进去，改变原节点的上一个指向，总得来说原来的节点下移
源代码如下：
public void add(int index, E element) {
// 索引校验 不能<0 或者 >链表长度
checkPositionIndex(index);
// 判断是否在尾部插入
if (index == size)
// 同上尾插法
linkLast(element);
else
linkBefore(element, node(index));
}
// 找到索引原有位置的节点
Node<E> node(int 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;
}
}
void linkBefore(E e, Node<E> succ) {
// 获取原节点的上一个节点
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++;
}
三、get操作
就是上面说的分半然后遍历
源代码如下：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// 找到索引原有位置的节点
Node<E> node(int 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;
}
五、contains操作
因为是允许存在null值的，所以遍历的时候要两种情况遍历，一种是遍历null值，一种是对比值，遍历找值对应节点的索引，没找到就返回-1 即false不存在
源代码如下：
public boolean contains(Object o) {
return indexOf(o) != -1;
}
public int indexOf(Object o) {
int index = 0;
if (o == null) {
//遍历链表 找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;
}
六、remove操作
分半查找到元素，然后修改指向
源代码如下：
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;
}
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;
if (prev == null) {
// 上指向为空说明该节点是头节点 所以头节点要改成要移除节点的下指向节点
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
// 下指向为空说明该节点是尾节点 所以尾节点要改成要移除节点的上指向节点
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 把值置为null 便于GC
x.item = null;
// 长度-1
size--;
modCount++;
return element;
}