作为一个新手,我几乎没有在任何情况下使用过LinkedList,唯一用到的就是和ArrayList比较.但是这并不妨碍我学习它.LinkedList是双向链表的一个经典实现.作为一个链表,它的优点是显而易见的
- 采用动态存储,可以使用不连续的内存空间(数组要求连续),因此提高了内存的利用率.
- 插入和删除元素十分方便,只需要修改指针即可,不需要移动大量元素(数组需要).
从增删改查方面入手,我们很快就能了解到LinkedList是怎么实现的.
找到源码中的add方法
public boolean add(E e) {
linkLast(e);//调用linkLast方法,从字面上来讲是将实例对象e加入尾部
return true;
}
void linkLast(E e) {
final Node<E> l = last;//Node是LinkedList的内部类,用以表示链表内的节点,last表示LinkedList内的空的最后一个节点
final Node<E> newNode = new Node<>(l, e, null);//构造一个存有对象e的实例,以l即last为头节点,尾节点为null
last = newNode;//此时newNode成为链表的最后一个节点
if (l == null)//如果l为空,说明之前LinkedList是空的,所以newNode既是第一个节点,也是最后一个节点
first = newNode;
else
l.next = newNode;//不然就贯通双向链表,将l节点的指针指向newNode
size++;
modCount++;
}
简单来讲,就是把构造一个newNode对象,与last对象相连并置于last之后,这样newNode就成了新的last节点.这个时候,就要根据newNode是不是第一个加入的节点.如果不是,就把原来的last结点指向newNode节点,形成双向链表.注意final关键字.
同样地还有linkFirst方法,从头部加入对象e
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
remove方法
public boolean remove(Object o) {//因为非空对象才能使用equals方法,所以需要进行判断
//通过遍历得到符合要求的对象,使用unlink方法进行删除.
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节点的位置
first = next;
} else {
prev.next = next;//将头节点指向尾节点,就是绕过要删除的这个节点产生新的链
x.prev = null;//释放该节点储存的头节点信息
}
if (next == null) {
last = prev;//判断尾节点如果为空,那么确定last节点的位置
} else {
next.prev = prev;//将尾节点指向头节点,到这一步两个节点双向打通
x.next = null;//释放该节点储存的尾节点信息
}
x.item = null;//到此释放要删除节点的所有内容
size--;
modCount++;
return element;
}
get方法
public E get(int index) {//根据索引获得节点储存的内容
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(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;
}
}