上一期 讲到了 顺序表与链表的基本知识 了解链表的基本知识。并且分析了ArrayList的源码。顺序表(随机访问速度快,插入和删除效率低)和链表(随机访问速度慢,插入和删除效率高)的优缺点。在开始写双链表之前我们分析一下LinkedList(典型的双链表)源码,来看一下Java 中是如何实现双链表的。
在分析一个类时,首先分析类的继承关系,再分析构造方法和属性。
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable
关键字transient 标识的字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。 我们都知道一个对象只要实现了Serilizable接口,这个对象就可以被序列化,java的这种序列 化模式为开发者提供了很多便利,我们可以不必关系具体序列化的过程,只要这个类实现了Seril izable接口,这个类的所有属性和方法都会自动序列化。 然而在实际开发过程中,我们常常会遇到这样的问题,这个类的有些属性需要序列化,而其他属 性不需要被序列化,打个比方,如果一个用户有一些敏感信息(如密码,银行卡号等),为了安 全起见,不希望在网络操作(主要涉及到序列化操作,本地序列化缓存也适用)中被传输,这些信 息对应的变量就可以加上transient关键字。换句话说,这个字段的生命周期仅存于调用者的内存 中而不会写到磁盘里持久化。 总之,java 的transient关键字为我们提供了便利,你只需要实现Serilizable接口,将不需要 序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会序列化到指定的目 的地中。
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
每个节点都是存储对象Node,包括(E item;Node next;Node prev;)这就意味着LinkedList 占用的内存会比较大,ArrayList 只包括 E,LinkedList 比ArrayList 占用内存大
private static class Node<E> {
//当前节点的 item
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;
}
}
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
LinkedList 有两个构造方法,第一个就不必说了,第二个构造一个链表,传入的是一个list(interface List extends Collection) addAll(c) 方法
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
//判断 index >= 0 && index <= size;
checkPositionIndex(index);
//将list 转换成一个数组
Object[] a = c.toArray();
int numNew = a.length;
//若数组的长度为0 返回false 不能构造链表
if (numNew == 0)
return false;
Node<E> pred, succ;
//若插入的位置 == 链表的大小
if (index == size) {
succ = null;
//准备要插入的节点 == last 链表的最后一个节点,准备循环从最后一个节点添加
pred = last;
} else {
//若插入的位置 != 链表的大小 找到要插入的位置
succ = node(index);
//准备插入的节点 == 插入位置的前一个节点
pred = succ.prev;
}
//循环数组中的Object 创建Node 节点
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//创建新的节点Node
Node<E> newNode = new Node<>(pred, e, null);
//若准备插入的节点为null 说明 index == size 而 pred = last链表为空
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//succ == null 说明 index == size
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
public E remove(int index) {
checkElementIndex(index);
//要删除某个节点 同样要找到该位置的节点
return unlink(node(index));
}
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 {
//删除的节点前一个不为空 删除节点的前一个节点的next
//指向删除节点的下一个节点
prev.next = next;
//将删除节点 prev 置为null
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
//将删除节点的item 置为null
x.item = null;
//链表减一
size--;
modCount++;
return element;
}
查找节点为耗时较长,算法复杂度为 o(n) = n
Node<E> node(int index) {
// assert isElementIndex(index);
//插入的位置 < 链表大小的一半 则从左侧 first 节点查找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//插入的位置 > 链表大小的一半则从右侧 last 节点查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
从上述分析我们可以得出,链表(LinkedList)的尾插效率高,中间插入和删除算法复杂度为 o (n) = n,对比顺序表(ArrayList )插入删除都用到了复制System.arraycopy( elementData, index, elementData, index + 1,size - index); 算法复杂度要比双链表的插入和删除复杂度高。如果频繁的插入和删除操作建议用链表的存储结构; 如果要想快速的查找到某条数据建议用顺序表的存储结构。
如何手写一个双链表,我们可以仿照LinkedList 的源码写一个简单的双链表
首先双链表的模型类:
class Node{
Object data;
Node next;
Node per;
}
需要的属性
int size;
Node frist;
Node last;
Node静态类
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;
}
}
完整的代码如下:
public class LinkedList<E> {
public LinkedList() {
}
Node<E> frist;
Node<E> last;
int size;
/**
* 向链表的尾部添加一个元素
*
* @param e
*/
public void add(E e) {
linkLast(e);
}
public void add(int index, E e) {
if (index < 0 || index > size) return;
if (index == size) {//插入尾部
linkLast(e);
} else {
Node<E> currentNode = node(index);//拿到当前位置要插入的节点
Node<E> prev = currentNode.prev;
Node<E> newNode = new Node<>(prev, e, currentNode);
if (prev == null) {//头部插入
frist = newNode;
} else {//中间插入
prev.next = newNode;//Note : 这里两个位置不能换
}
currentNode.prev = newNode;//Note: 查到的节点prev 要指向新的节点
size++;
}
}
public void remove(int index) {
if (index < 0 || index > size) return;
unLinkNode(node(index));
}
private void unLinkNode(Node<E> node) {
Node<E> prev = node.prev;
Node<E> next = node.next;
if (prev == null){
frist = next;
}else {
prev.next = next;
node.prev = null;
}
if (next == null){
last = prev;
}else {
next.prev = prev;
node.next = null;
}
size --;
}
/**
* 获取某个节点的元素
*
* @param index
* @return
*/
public E get(int index) {
if (index < 0 || index > size) return null;
return node(index).item;
}
private Node<E> node(int index) {
if ((size >> 1) < index) {//从尾部开始循环
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = last.prev;
}
return node;
} else {//从头部开始循环
Node<E> node = frist;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
}
private void linkLast(E e) {
Node<E> newNode = new Node<>(last, e, null);
Node<E> l = last;//拿到之前的最后一个节点
last = newNode;//将添加的新节点newNode 赋给last 最后一个节点
if (l == null) {//如果之前的最后一个节点为空
frist = newNode;
} else {//如果之前的最后一个节点不为空
l.next = newNode;
}
size++;
}
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;
}
}
}
知道如何写一个双链表,那么写一个单链表就更简单了。
在实现逆置之前我们写一个单链表,代码如下:
public class SingleList<E> {
private static class Node<E> {
E item;
Node<E> next;
public Node(E item, Node<E> next) {
this.item = item;
this.next = next;
}
}
private Node<E> frist;
private Node<E> last;
public int size;
/**
* 向尾部添加一个元素
*
* @param e
*/
public void add(E e) {
lastList(e);
}
/**
* 在某个位置插入一个元素
*
* @param e
* @param index
*/
public void add(E e, int index) {
if (index < 0 || index > size) return;
if (index == size) {//插入尾部
lastList(e);
} else {
if (index == 0) {
Node<E> l = frist;
Node<E> newNode = new Node<>(e, l);//新的元素在插入位置的前一个位置
frist = newNode;
} else {
Node<E> fNode = node(index - 1);//找到要插入位置的前一个位置
Node<E> lNode = fNode.next;
Node<E> newNode = new Node<>(e, lNode);
fNode.next = newNode;
}
size++;
}
}
/**
* 删除某个节点
*
* @param index
*/
public void remove(int index) {
unLink(index);
}
private void unLink(int index) {
if (index < 0 || index > size) return;
if (index == size) {//删尾部
Node<E> node = node(index - 1);
node.next = null;
last = node;
} else if (index == 0) {//删头部
Node<E> l = this.frist;
frist = l.next;
} else {
Node<E> node = node(index - 1);//要删除的前一个节点
Node<E> removeNode = node.next;//要删除的节点
Node<E> lNode = removeNode.next;//要删除的后一个节点
node.next = lNode;
}
size--;
}
public void remove(E e) {
Node<E> newNode = frist;
int index = -1;
for (int i = 0; i < size; i++) {
newNode = newNode.next;
if (e.equals(newNode.item)) {
index = i;
break;
}
}
if (index != -1)
unLink(index);
}
private void lastList(E e) {
Node<E> newNode = new Node<>(e, null);//一个新的节点
Node<E> l = last;
last = newNode;//将最后一个节点赋值
if (l == null) {
frist = newNode;
} else {
l.next = newNode;
}
size++;
}
/**
* 获取节点的某个元素
*
* @param index
* @return
*/
public E get(int index) {
if (index < 0 || index > size) {
return null;
}
return node(index).item;
}
public Node<E> node(int index) {
Node<E> newNode = frist;
for (int i = 0; i < index; i++) {
newNode = newNode.next;
}
return newNode;
}
}
测试单链表的添加个删除
SingleList<Integer> singleList = new SingleList<>();
singleList.add(1);
singleList.add(2);
singleList.add(3);
singleList.add(4);
singleList.add(5);
// singleList.add(9,0);
// singleList.add(8,5);
// singleList.add(7,2);
// singleList.remove(6);
// singleList.remove(3);
for (int i = 0; i < singleList.size; i++) {
System.out.print(singleList.get(i) + " ");
}
第一种方法,循环法
/**
* 单链表的逆置
* 第一种方法实现 循环
*/
public void inverse() {
Node<E> l = this.last;
Node<E> curr = this.frist;
Node<E> reve = null;
while (curr != null) {
Node<E> temp = curr;
curr = curr.next;
temp.next = reve;
reve = temp;
}
frist = reve;
}
如上图所示: 第一次循环后得到的 --》 temp = 1 curr =2 temp.next = null reve = temp = 1 ;链表的结构就变为 1 --> null 2 --> 3 --> 4. 第二次循环后得到的 --》 temp = 2 curr = 3 temp.next = 1 reve = temp = 2 ;链表的结构就变为 2 --> 1 --> null 3 --> 4 第三次循环后得到的 --》 temp = 3 curr = 4 temp.next = 2 reve = temp = 3 ;链表的结构就变为 3 --> 2 --> 1 --> null 4 …. 如此类推就可以得到一个逆置的单链表。
第二种方法,递归法
/**
* 递归的方式转置
*/
public Node<T> reverse(Node<T> head) {
if (head == null || head.next == null) {
return head;
}
Node<T> tail = reverse(head.next);
head.next.next = head;
head.next = null;
return tail;
}
public void transterReverse() {
this.frist = reverse(this.frist);
}
如上图所示递归法的逆置逻辑: 1 --> 2 --> 3 <-- 4
1 --> 2 <-- 3 <--4
1 <-- 2 <-- 3 <--4
至此,数据结构线性表的内容基本讲完。