看得见的数据结构Android版之双链表篇
零、前言
1.上一篇分析了单链表，链表是一种数据结构，用来承载数据，每个表节点装载一个数据元素 2.双链表是每个节点除了数据元素外还分别持有前、后两个节点的引用 3.为了统一节点的操作，一般在真实链表的首尾各加一个虚拟节点，称为头节点和尾节点 4.如果说单链表是一列火车，那双链表就是一辆双头加固版火车，java中的LinkedList底层便是此结构 5.本例操作演示源码：希望你可以和我在Github一同见证：DS4Android的诞生与成长，欢迎star
1.留图镇楼：双链表的最终实现的操作效果:
2.对于双链表简介：
双链表是对节点(Node)的操作，而节点(Node)又承载数据(T)
总的来看，双链表通过操作节点(Node)从而操作数据(T)，就像车厢运送获取，车厢只是载体，货物是我们最关注
双链表不同于单链表至处在于一个节点同时持有前、后两个节点的引用，使得对头尾操作都方便
Node只不过是一个辅助工具，并不会暴露在外。它与数据相对应，又使数据按链式排布，
操纵节点也就等于操纵数据，就像提线木偶，并不是直接操作木偶的各个肢体本身(数据T)。
为了统一节点的操作，通常在链表最前面添加一个虚拟头(headNode)和虚拟尾(tileNode)(封装在内中，不暴露)3.双链表的实现：本文要务
一、双链表结构的实现：LinkedChart
1.表的接口定义在数组表篇，这里就不贴了
这里给出实现接口后的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;
}2.单链节点类(Node)的设计：
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;
}
}二、节点(Node)的底层操作(CRUD)----链表的心脏
1.查询操作：getNode
上一篇的单链表查询：相当于在一个视口一个一个挨着找车厢 双链表有两个火车头，这就代表两头都能操作，所以为了尽量高效，判断一下车厢在前半还是后半 这样比起单链表要快上很多(越往后快得越明显)
/**
* 根据索引获取节点
*
* @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;
}2.插入操作：addNode()
还是想下火车头：想在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++;
}3.移除操作：removeNode()
还是想下火车头：如何删除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;
}3.修改节点：setNode
/**
* 修改节点
*
* @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;
}4.清空操作：clearNode()
思路和删除一样：首尾虚拟节点互指，中间没有元素,形式上看，当前链表上全部删除 重新实例化头结点------火车头说：老子从头(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;
}二、利用链表实现对数据的操作
链表只是对节点的操作，只是一种结构，并非真正目的，最终要让链表对外不可见,就像人的骨骼之于躯体 躯体的任何动作是骨骼以支撑,而骨骼并不可见，从外来看只是躯体的动作而已。 我们需要的是按照这种结构对数据进行增删改查等操作，并暴露接口由外方调用
1、定点添加操作--add
@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);
}2.定点移除操作--remove
@Override
public T remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Remove failed. Illegal index");
}
return removeNode(getNode(index));
}3.获取和修改--get和set
@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);
}四、其他操作
和单链表基本一致，就不演示了。
1.是否包含某元素：
@Override
public boolean contains(T el) {
Node target = headNode;
while (target.next != null) {
if (el.equals(target.next)) {
return true;
}
}
return false;
}2.根据指定元素获取匹配索引
@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;
}3.按元素移除：(找到，再删除...)
@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;
}4.定点连接两个单链表
///////////////只是实现一下，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;
}
///////////////////////////////////////////////////////////////五、小结：
1.优劣分析
优点： 动态创建，节省空间
头部、尾部添加容易
定点插入/删除总体上优于数组表(因为最多找一半，数组表最多全部)
缺点： 空间上不连续，造成空间碎片化
查找相对困难，只能从头开始或结尾一个一个找(但比单链表优秀)
使用场景：[双链表]增删性能总体优于[数组表]和[单链表]，频繁增删不定位置时[双链表]最佳2.最后把视图一起说了吧
接口都是相同的，底层实现更换了，并不会影响视图层，只是把视图层的单体绘制更改一下就行了。
/**
* 绘制表结构
*
* @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);
}
}举报
腾讯云开发者
