1.上一篇分析了单链表,链表是一种数据结构,用来承载数据,每个表节点装载一个数据元素 2.双链表是每个节点除了数据元素外还分别持有前、后两个节点的引用 3.为了统一节点的操作,一般在真实链表的首尾各加一个虚拟节点,称为头节点和尾节点 4.如果说单链表是一列火车,那双链表就是一辆双头加固版火车,java中的LinkedList底层便是此结构 5.本例操作演示源码:希望你可以和我在Github一同见证:DS4Android的诞生与成长,欢迎star
双链表是对节点(Node)的操作,而节点(Node)又承载数据(T)
总的来看,双链表通过操作节点(Node)从而操作数据(T),就像车厢运送获取,车厢只是载体,货物是我们最关注
双链表不同于单链表至处在于一个节点同时持有前、后两个节点的引用,使得对头尾操作都方便
Node只不过是一个辅助工具,并不会暴露在外。它与数据相对应,又使数据按链式排布,
操纵节点也就等于操纵数据,就像提线木偶,并不是直接操作木偶的各个肢体本身(数据T)。
为了统一节点的操作,通常在链表最前面添加一个虚拟头(headNode)和虚拟尾(tileNode)(封装在内中,不暴露)
这里给出实现接口后的LinkedChart以及简单方法的实现
/**
* 作者:张风捷特烈<br/>
* 时间:2018/11/22 0022:15:36<br/>
* 邮箱:1981462002@qq.com<br/>
* 说明:双链表实现表结构
*/
public class LinkedChart<T> implements IChart<T> {
private Node headNode;//虚拟尾节点--相当于头部火车头
private Node tailNode;//虚拟尾节点--相当于尾部火车头
private int size;//元素个数
public SingleLinkedChart() {//一开始两个火车头彼此相连
headNode = new Node(null, null, null);//实例化头结点
tailNode = new Node(headNode, null, null);//实例化尾节点,并将prev指向头
headNode.next = tailNode;//头指尾
size = 0;//链表长度置零
}
@Override
public void add(int index, T el) {
}
@Override
public void add(T el) {
add(size, el);
}
@Override
public T remove(int index) {
return null;
}
@Override
public T remove() {
return remove(size);
}
@Override
public int removeEl(T el) {
return 0;
}
@Override
public boolean removeEls(T el) {
return false;
}
@Override
public void clear() {
headNode = new Node(null, null, null);//实例化头结点
tailNode = new Node(headNode, null, null);//实例化尾节点,并将prev指向头
headNode.next = tailNode;//头指尾
size = 0;//链表长度置零
}
@Override
public T set(int index, T el) {
return null;
}
@Override
public T get(int index) {
return null;
}
@Override
public int[] getIndex(T el) {
return null;
}
@Override
public boolean contains(T el) {
return getIndex(el).length != 0;
}
@Override
public IChart<T> contact(IChart<T> iChart) {
return null;
}
@Override
public IChart<T> contact(int index, IChart<T> iChart) {
return null;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
@Override
public int capacity() {
return size;
}
LinkedChart相当于一列双头火车,暂且按下,先把车厢的关系弄好,最后再拼接列车会非常方便 这里将Node作为LinkedChart的一个私有内部类,是为了隐藏Node,并能使用LinkedChart的资源 就像心脏在身体内部,外面人看不见,但它却至关重要,并且还能获取体内的信息与资源
一节双链车厢,最少要知道里面的
货物(node.T)
是什么, 它的下一节车厢(node.next)
是哪个,以及上一节车厢(node.prev)
是哪个
private class Node {
/**
* 数据
*/
private T el;
/**
* 前节点
*/
private Node prev;
/**
* 后节点
*/
private Node next;
private Node(Node prev, Node next, T el) {
this.el = el;
this.prev = prev;
this.next = next;
}
}
上一篇的单链表查询:相当于在一个视口一个一个挨着找车厢 双链表有两个火车头,这就代表两头都能操作,所以为了尽量高效,判断一下车厢在前半还是后半 这样比起单链表要快上很多(越往后快得越明显)
/**
* 根据索引获取节点
*
* @param index 索引
* @return 索引处节点
*/
private Node<T> getNode(int index) {
Node<T> targetNode;//声明目标节点
if (index < 0 || index > size - 1) { //索引越界处理
throw new IndexOutOfBoundsException();
}
//如果索引在前半,前序查找
if (index < size / 2) {
targetNode = headNode.next;
for (int i = 0; i < index; i++) {
targetNode = targetNode.next;
}
} else { //如果索引在后半,反序查找
targetNode = tailNode.prev;
for (int i = size - 1; i < index; i++) {
targetNode = targetNode.prev;
}
}
return targetNode;
}
还是想下火车头:想在T0和T1车厢之间插入一节T3车厢怎么办? 第一步:将T0的后链栓到T3上,T3的前链栓到T0上-----完成了T0和T3的连接 第二步:将T3的后链栓到T2上,T1的前链栓到T3上-----完成了T1和T3的连接
/**
* 根据目标节点插入新节点--目标节点之前
*
* @param target 目标节点
* @param el 新节点数据
*/
private void addNode(Node target, T el) {
//想在T0和T1车厢之间插入一节T3车厢为例:
//新建T3,将前、后指向分别指向T0和T1
Node newNode = new Node(target.prev, target, el);
//T0的next指向T3
target.prev.next = newNode;
//T1的prev指向T3
target.prev = newNode;
//大功告成:链表长度+1
size++;
}
还是想下火车头:如何删除T1: 很简单:T0和T2手拉手就行了,然后再让T1孤独的离去...
/**
* 移除目标节点
*
* @param target 目标节点
* @return 目标节点数据
*/
private T removeNode(Node target) {
//目标前节点的next指向目标节点后节点
target.prev.next = target.next;
//目标后节点的prev指向目标节点前节点
target.next.prev = target.prev;
target.prev = null;//放开左手
target.next = null;//放开右手---挥泪而去
//链表长度-1
size--;
return target.el;
}
/**
* 修改节点
*
* @param index 节点位置
* @param el 数据
* @return 修改后的节点
*/
private T setNode(int index, T el) {
Node node = getNode(index);
T tempNode = node.el;
node.el = el;
return tempNode;
}
思路和删除一样:首尾虚拟节点互指,中间没有元素,形式上看,当前链表上全部删除 重新实例化头结点------火车头说:老子从头(null)开始,不带你们玩了, 重新实例化尾节点------火车尾说:老娘从头(null)开始,不带你们玩了, 于是火车头和火车尾,手牵手,走向远方...
/**
* 清空所有节点
*/
private void clearNode() {双链表删除节点.png
//实例化头结点
headNode = new Node<T>(null, null, null);
//实例化尾节点,并将prev指向头
tailNode = new Node<T>(headNode, null, null);
headNode.next = tailNode;
//链表长度置零
size = 0;
}
链表只是对节点的操作,只是一种结构,并非真正目的,最终要让链表对外不可见,就像人的骨骼之于躯体 躯体的任何动作是骨骼以支撑,而骨骼并不可见,从外来看只是躯体的动作而已。 我们需要的是按照这种结构对数据进行增删改查等操作,并暴露接口由外方调用
@Override
public void add(int index, T el) {
// index可以取到size,在链表末尾空位置添加元素。
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index");
}
addNode(getNode(index), el);
}
@Override
public T remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Remove failed. Illegal index");
}
return removeNode(getNode(index));
}
@Override
public T get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Get failed. Illegal index");
}
return getNode(index).el;
}
@Override
public T set(int index, T el) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("ISet failed. Illegal index");
}
return setNode(index, el);
}
和单链表基本一致,就不演示了。
@Override
public boolean contains(T el) {
Node target = headNode;
while (target.next != null) {
if (el.equals(target.next)) {
return true;
}
}
return false;
}
@Override
public int[] getIndex(T el) {
int[] tempArray = new int[size];//临时数组
int index = 0;//重复个数
int count = 0;
Node node = headNode.next;
while (node.next != null) {
if (el.equals(node.el)) {
tempArray[index] = -1;
count++;
}
index++;
node = node.next;
}
int[] indexArray = new int[count];//将临时数组压缩
int indexCount = 0;
for (int i = 0; i < tempArray.length; i++) {
if (tempArray[i] == -1) {
indexArray[indexCount] = i;
indexCount++;
}
}
return indexArray;
}
@Override
public int removeEl(T el) {
int[] indexes = getIndex(el);
int index = -1;
if (indexes.length > 0) {
index = indexes[0];
remove(indexes[0]);
}
return index;
}
@Override
public boolean removeEls(T el) {
int[] indexArray = getIndex(el);
if (indexArray.length != 0) {
for (int i = 0; i < indexArray.length; i++) {
remove(indexArray[i] - i); // 注意-i
}
return true;
}
return false;
}
///////////////只是实现一下,getHeadNode和getLastNode破坏了Node的封装性,不太好/////////////
@Override
public IChart<T> contact(IChart<T> iChart) {
return contact(0, iChart);
}
@Override
public IChart<T> contact(int index, IChart<T> iChart) {
if (!(iChart instanceof LinkedChart)) {
return null;
}
if (index < 0 || index > size) {
throw new IllegalArgumentException("Contact failed. Illegal index");
}
LinkedChart linked = (LinkedChart) iChart;
Node targetNode = getNode(index);
Node targetNextNode = targetNode.next;
//目标节点的next指向待接链表的第一个节点
targetNode.next = linked.getHeadNode().next;
//向待接链表的第一个节点的prev指向目标节点
linked.getHeadNode().next.prev = targetNode;
//目标节点的下一节点指的prev向待接链表的最后一个节点
targetNextNode.prev = linked.getLastNode().prev;
//向待接链表的最后一个节点的next指向目标节点的下一节点的
linked.getLastNode().prev.next = targetNextNode;
return this;
}
public Node getHeadNode() {
return headNode;
}
public Node getLastNode() {
return tailNode;
}
///////////////////////////////////////////////////////////////
优点: 动态创建,节省空间
头部、尾部添加容易
定点插入/删除总体上优于数组表(因为最多找一半,数组表最多全部)
缺点: 空间上不连续,造成空间碎片化
查找相对困难,只能从头开始或结尾一个一个找(但比单链表优秀)
使用场景:[双链表]增删性能总体优于[数组表]和[单链表],频繁增删不定位置时[双链表]最佳
接口都是相同的,底层实现更换了,并不会影响视图层,只是把视图层的单体绘制更改一下就行了。
/**
* 绘制表结构
*
* @param canvas
*/
private void dataView(Canvas canvas) {
mPaint.setColor(Color.BLUE);
mPaint.setStyle(Paint.Style.FILL);
mPath.reset();
for (int i = 0; i < mArrayBoxes.size(); i++) {
LinkedNode box = mArrayBoxes.get(i);
mPaint.setColor(box.color);
canvas.drawRoundRect(
box.x, box.y, box.x + Cons.BOX_WIDTH, box.y + Cons.BOX_HEIGHT,
BOX_RADIUS, BOX_RADIUS, mPaint);
mPath.moveTo(box.x, box.y);
mPath.rCubicTo(Cons.BOX_WIDTH / 2, Cons.BOX_HEIGHT / 2,
Cons.BOX_WIDTH / 2, Cons.BOX_HEIGHT / 2, Cons.BOX_WIDTH, 0);
if (i < mArrayBoxes.size() - 1 ) {
LinkedNode box_next = mArrayBoxes.get(i + 1);
LinkedNode box_now = mArrayBoxes.get(i);
if (i % LINE_ITEM_NUM == LINE_ITEM_NUM - 1) {//边界情况
mPath.rLineTo(0, Cons.BOX_HEIGHT);
mPath.lineTo(box_next.x + Cons.BOX_WIDTH, box_next.y);
mPath.rLineTo(Cons.ARROW_DX, -Cons.ARROW_DX);
mPath.moveTo(box_next.x, box_next.y);
mPath.lineTo(box_now.x, box_now.y+Cons.BOX_HEIGHT);
mPath.rLineTo(-Cons.ARROW_DX, Cons.ARROW_DX);
} else {
mPath.rLineTo(0, Cons.BOX_HEIGHT / 2.2f);
mPath.lineTo(box_next.x+Cons.BOX_WIDTH * 0.2f, box_next.y + Cons.BOX_HEIGHT / 2f);
mPath.rLineTo(-Cons.ARROW_DX, -Cons.ARROW_DX);
mPath.moveTo(box_next.x, box_next.y);
mPath.rLineTo(0, Cons.BOX_HEIGHT / 1.2f);
mPath.lineTo(box_now.x + Cons.BOX_WIDTH * 0.8f, box_now.y + Cons.BOX_HEIGHT * 0.8f);
mPath.rLineTo(Cons.ARROW_DX, Cons.ARROW_DX);
}
}
canvas.drawPath(mPath, mPathPaint);
canvas.drawText(box.index + "",
box.x + Cons.BOX_WIDTH / 2,
box.y + 3 * OFFSET_OF_TXT_Y, mTxtPaint);
canvas.drawText(box.data + "",
box.x + Cons.BOX_WIDTH / 2,
box.y + Cons.BOX_HEIGHT / 2 + 3 * OFFSET_OF_TXT_Y, mTxtPaint);
}
}