LinkedList
底层操作机制
- LinkedList底层维护了一个双向链表
- LinkedList中维护了两个属性first和last分别指向首节点和尾结点
- 每个节点(Node对象),里面又维护了prev、next、item三个属性,其中通过prev指向前一个,通过next指向后一个节点。最终实现双向链表
- 添加和删除不是通过数组完成的,相对来说效率比较高
实现代码
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
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;
}
}
添加一个e节点
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++;
}
遍历并找到index节点
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
if (index < (size >> 1)) { // size二进制右移一位,即size/2。从头往尾遍历
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;
}
}