LinkedList结构图
image.png
LinkedList主要方法
- public E get(int index)
- public E set(int index, E element)
- public void add(int index, E element)
- public E remove(int index)
LinkedList解读主要方法
来看一下public E get(int index)源码：
//第一步
public boolean add(E e) {
linkLast(e);
return true;
}
//第二步
void linkLast(E e) {
//保存last节点
final Node<E> l = last;
//创建一个新的节点，它的前一个节点为l，后一个节点为null
final Node<E> newNode = new Node<>(l, e, null);
//把新的节点标记为last节点
last = newNode;
//如果之前的last节点为空，那么新的节点既是头结点也是尾节点
if (l == null)
first = newNode;
else
//把新的节点加入到原尾节点的后面
l.next = newNode;
//修改size大小
size++;
//修改count值
modCount++;
}
看一下public E set(int index, E element)的源码
public E set(int index, E element) {
//校验index位置
checkElementIndex(index);
//找到index
Node<E> x = node(index);
//获取原节点值，修改为新值，返回原节点的值
E oldVal = x.item;
x.item = element;
return oldVal;
}
//校验index，index需在0到size之间
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//找到index节点
Node<E> node(int index) {
// assert isElementIndex(index);
//小技巧，判断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;
}
}
来看一下public void add(int index, E element) 源码
public void add(int index, E element) {
//这个还是和set一样的判断，index位置是否合理
checkPositionIndex(index);
//在末尾添加
if (index == size)
linkLast(element);
else
//非末尾添加
linkBefore(element, node(index));
}
//在末尾添加，这个前面我已经讲过了
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++;
}
//在index节点前插入element元素
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//保存index位置之前的节点为pred
final Node<E> pred = succ.prev;
//创建一个节点，它的前一个节点为pred它的后一个节点为index对应的节点
final Node<E> newNode = new Node<>(pred, e, succ);
//index节点的前一个节点为element对于的新节点了
succ.prev = newNode;
//index的前一个节点pred如果是空的证明就没有首节点，将前一个节点设置为首节点
if (pred == null)
first = newNode;
else
//前一个节点不为空的话，把它的下一个节点设置为新节点
pred.next = newNode;
//修改size和modCount值
size++;
modCount++;
}
来看一下public E remove(int index)源码
public E remove(int index) {
//这个还是和set一样的判断，index位置是否合理
checkElementIndex(index);
//删除index对应的节点
return unlink(node(index));
}
//删除index节点
E unlink(Node<E> x) {
// assert x != null;
//获取index元素，找到index的前一个节点prev和后一节点next
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//如果待删除节点的前一个节点为空的话，将next节点设置为first节点，也就说明就两个节点，删除的就是首节点
if (prev == null) {
first = next;
} else {
//将前一个节点的next指向待删除节点的下一个节点(next)
prev.next = next;
//将待删除节点的前一个节点设置为空
x.prev = null;
}
//如果待删除节点的后一个节点为空，将pred节点设置为last节点，也就说明只有两个节点，删除节点就是尾节点
if (next == null) {
last = prev;
} else {
//将后一个节点的prev指向待删除节点的前一个节点(prev)
next.prev = prev;
//将待删除节点的下一个节点设置为空
x.next = null;
}
//待删除节点内容设置为空，修改size和modCount，返回待删除元素
x.item = null;
size--;
modCount++;
return element;
}
LinkedList遍历介绍
常用的三种遍历方式：
//one foreach 遍历
for (Object o : list) {
System.out.println(o);
}
// two 随机访问
for (int i = 0; i <list.size(); i++) {
System.out.println(list.get(i));
}
//three 迭代器的遍历
Iterator iterator = list.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
LinkedList其他特性介绍
- LinkedList底层使用链表来实现的(并且是双向链表)，所以LinkedList在新增和删除的时候效率比较高，但是在随机访问的时候效率会比较低。
- LinkedList是无界的，还有LinkedList在多线程操作的时候当modCount!=expectedModCount会抛出ConcurrentModificationException异常。
