几句话证明你看过LinkedList的源码
LinkedList同时实现了List接口和Deque接口，可以当做一个链表容器，也当做一个队列(Queue)，还可以当做一个栈(Stack)。
推荐栈和队列（即对两端进行操作）使用AarryDeque，根据索引位置增删使用LinkedList
链表（查询慢，增删快，线程不安全，允许元素重复和null，增删都是在中间效率会较低（源码遍历有从前或从后遍历，所以最慢的遍历是中间）)
关于循环删除元素，普通for循环，不会报错，会导致下标紊乱，产生数据错误或数组越界
增强for循环，由于删除修改了modCount，导致fail-fast，所以会报错ConcurrentModificationException
迭代器删除(iterator.remove()，而不是list.remove())，会更新modCount与expectedModCount，所以支持迭代删除。
1.双向链表
成员变量包含
first头节点 last尾节点 size长度
内部类
private static class Node<E> {
//上一节点
Node<E> prev;
//下一节点
Node<E> next;
//当前节点值
E item;
public Node(Node<E> prev, Node<E> next, E item) {
this.prev = prev;
this.next = next;
this.item = item;
}
}
2.头尾节点修饰符为transient
transient关键字了解
简单概括：实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中
3.获取node元素效率提升小细节
/**
* 获取指定角标元素
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//根据角标与长度一半对比，选择从头遍历还是从尾遍历到指定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;
}
}
4.add方法
插入新节点，处理前驱后继，完成链接
/**
* 插入元素-指定节点
* @param index
* @param element
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* 插入元素-默认尾节点
* @param e
* @return
*/
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;
size++;
modCount++;
}
/**
* Inserts element e before non-null Node succ.
*/
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++;
}
5.remove方法
处理前驱后继，隔p链接
/**
* 删除指定元素
* @param o
* @return
*/
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;
}
/**
* 删除指定角标元素
* @param index
* @return
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
* Unlinks non-null node x.
*/
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;
}
//方便垃圾回收
x.item = null;
size--;
modCount++;
return element;
}
6.fast-fail机制
linkedlist可正反双向迭代
/**
* ListItrItr-ListIterator是Iterator(迭代器)的实现类
*/
private class ListItr implements ListIterator<E> {
//上一次返回的节点
private Node<E> lastReturned;
//下一个节点
private Node<E> next;
//下一个节点角标
private int nextIndex;
//期望的改变计数。用来实现fail-fast机制。
private int expectedModCount = modCount;
//从index位置开始进行迭代
ListItr(int index) {
// assert isPositionIndex(index);
//半数以下 从前往后，半数以上 从前往后
next = (index == size) ? null : node(index);
nextIndex = index;
}
//是否存在下一个元素
public boolean hasNext() {
//通过元素角标是否等于“双向链表大小”判断
return nextIndex < size;
}
//获取下一个元素
public E next() {
//期望的改变计数与modCount比较
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
//是否存在上一个元素
public boolean hasPrevious() {
return nextIndex > 0;
}
//获取上一个元素
public E previous() {
//期望的改变计数与modCount比较
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() {
//期望的改变计数与modCount比较
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
//设置当前节点为e
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
//期望的改变计数与modCount比较
checkForComodification();
lastReturned.item = e;
}
//将e添加到当前节点
public void add(E e) {
//期望的改变计数与modCount比较
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
// 判断 “modCount和expectedModCount是否相等”，依次来实现fail-fast机制。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
7.队列，栈相关操作
https://www.cnblogs.com/skywang12345/p/3308807.html
8.自定义LinkedList练习
public class MyLinkedList<E> implements MyList<E> {
Node<E> first;
Node<E> last;
private int size;
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object o) {
return indexOf(o) == -1;
}
/**
* 创建以最后节点为前驱的 新节点
*
* @param e
* @return
*/
@Override
public boolean add(E e) {
//“原尾节点”
final Node<E> oldLast = last;
//创建以尾节点为前驱的 “新尾节点”
Node<E> newLast = new Node(last, null, e);
//将“新尾节点”赋值给 “尾节点”
last = newLast;
//空链表
if (oldLast == null) {
//既是头节点也是尾节点
first = newLast;
} else {
//将“原尾节点”的后置改为 “新尾节点”
oldLast.next = newLast;
}
size++;
return true;
}
@Override
public boolean remove(Object o) {
if (o == null) {
for (Node<E> node = first; node != null; node = node.next) {
if (node.item == null) {
unlink(node);
return true;
}
}
} else {
for (Node<E> node = first; node != null; node = node.next) {
if (o.equals(node.item)) {
unlink(node);
return true;
}
}
}
return false;
}
private void unlink(Node<E> node) {
//上一节点
Node<E> prev = node.prev;
//下一节点
Node<E> next = node.next;
//头节点
if (prev == null) {
first = next;
} else {
prev.next = next;
//方便垃圾回收
node.prev = null;
}
//尾节点
if (next == null) {
last = prev;
} else {
next.prev = prev;
//方便垃圾回收
node.next = null;
}
//方便垃圾回收
node.item = null;
size--;
}
@Override
public E get(int index) {
return node(index).item;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E oldItem = node.item;
node.item = element;
return oldItem;
}
@Override
public void add(int index, E e) {
//获取节点
Node<E> oldNode = node(index);
//尾部插入节点
if (index == size) {
add(e);
return;
}
final Node<E> prev = oldNode.prev;
Node newNode = new Node(prev, oldNode, e);
oldNode.prev = newNode;
//头部插入节点
if (prev == null) {
first = newNode;
} else {
//中间插入节点
prev.next = newNode;
}
size++;
}
private Node<E> node(int index) {
//LinkedList思想
//半数以下 从前往后
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;
}
}
@Override
public E remove(int index) {
final Node<E> delNode = node(index);
final E item = delNode.item;
unlink(delNode);
return item;
}
@Override
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
return index;
}
index++;
}
} else {
Node<E> x = first;
while (x != null) {
if (o.equals(x.item)) {
return index;
}
x = x.next;
index++;
}
}
return -1;
}
public static void main(String[] args) {
MyList<String> list = new MyLinkedList<>();
System.out.println(list.isEmpty());
list.add("0");
list.add("1");
System.out.println(list);
list.add(0, "new0");
System.out.println(list);
list.add(list.size(), "4");
System.out.println(list.size());
System.out.println(list.get(2));
System.out.println(list.indexOf("new0"));
list.set(0, "nn0");
list.remove(0);
System.out.println(list);
list.remove(list.size() - 1);
System.out.println(list);
}
private static class Node<E> {
//上一节点
Node<E> prev;
//下一节点
Node<E> next;
//当前节点值
E item;
public Node(Node<E> prev, Node<E> next, E item) {
this.prev = prev;
this.next = next;
this.item = item;
}
}
}
网友评论