单链表
线性表链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(存储单元可以连续，也可以不连续)，为了表示每个元素Ai与其直接后继A i+1之间的逻辑关系，对元素Ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据称为节点,他包括两个域:其中存储数据元素信息的域称为数据域;存储直接后继的存储位置的域称之为指针域。指针域中存储的信息称为指针或链。n个链结成一个链表。如图
单链表的逻辑状态
单向循环链表
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相连的单链表称为单循环链表，简称循环链表。如图
单循环链表逻辑状态
双向链表
上面讨论的链式存储结构的节点只有一个指示直接后继的指针域，由此。从某个节点出发只能顺着指针往后查找其他节点。若要查找节点的直接前驱，则需要从表头指针出发。换句话说。在单链表中，NextNode的时间为O(1),而PriorNode的执行时间为O(n)。为克服单链表的缺点，可以利用双链表。也就是在节点中有两个指针域，一个指向前驱,一个指向后继。 如图
双链表的逻辑状态
双向循环链表
双向循环链表是单向循环链表的每个结点中，再设置一个指向其前驱结点的指针域，如图
双向循环链表的逻辑状态
LinkedList源码分析
LinkedList的属性
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
一个双向链表有头结点，尾节点，还有节点的个数。
LinkedList的数据结构
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;
}
}
双向链表的节点的定义，只定义了存储的元素、前一个元素、后一个元素，每个节点只知道自己的前一个节点和后一个节点。
LinkedList的构造方法
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
第二个构造方法接收一个Collection参数c，调用第一个构造方法构造一个空的链表，之后通过addAll将c中的元素全部添加到链表中。
LinkedList的添加
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
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++;
}
LinkedList的添加过程都是在尾部添加，首先新创建一个节点，让last(也就是链表的尾节点)指向这个新加入的节点，如果last为空，说明是一个空链表，将新创建的节点作为头节点即可，此时头尾节点都指向这个新节点。如果不为空，尾节点的下一个节点指向该新节点。
LinkedList的删除
//从头结点遍历找到要删除的节点
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;
}
/**
* 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) {//prev=null说明该 要删的节点是头节点
first = next;//将删除节点的后继节点作为头结点
} else {
prev.next = next; //删除节点前驱的下一个节点指向删除节点的后继节点
x.prev = null;
}
if (next == null) {next=null说明该 要删的节点是尾节点
last = prev;将删除节点的前驱节点作为尾结点
} else {
next.prev = prev;//删除节点后继的前一个节点指向删除节点的前驱节点
x.next = null;
}
x.item = null;//数据域设置为null
size--; //数量-1
modCount++;//编辑次数+1
return element;
}
删除操作挺好理解，只需将删除节点的前驱节点指向删除节点的后继结点(①操作)，删除节点后继的前驱节点指向删除节点的前驱节点(②5操作)，看下面的图
删除操作
LinkedList的查找
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;
}
}
因为是双向链表，既可以从前往后查找，又可以从后往前查找，如果查找元素的位置小于链表节点个数的一半，就从头节点遍历到该节点的位置，反之，从尾节点遍历到该节点的位置。
LinkedList的修改
public E set(int index, E element) {
checkElementIndex(index);//检查下标
Node<E> x = node(index);//找到index位置的元素
E oldVal = x.item;//修改
x.item = element;
return oldVal;
}
修改操作无非就是找到该节点，重新设置数据域。
总结
ArrayList和LinkedList的比较
- 优点：头插，中间插，删除效率高。
- 缺点：不支持随机访问
- 插入效率ArrayList会比较高
- ArrayList的遍历效率会比LinkedList的遍历效率高
网友评论