阅读 854

看得见的数据结构Android版之双链表篇

零、前言

1.上一篇分析了单链表,链表是一种数据结构,用来承载数据,每个表节点装载一个数据元素
2.双链表是每个节点除了数据元素外还分别持有前、后两个节点的引用
3.为了统一节点的操作,一般在真实链表的首尾各加一个虚拟节点,称为头节点和尾节点
4.如果说单链表是一列火车,那双链表就是一辆双头加固版火车,java中的LinkedList底层便是此结构
5.本例操作演示源码:希望你可以和我在Github一同见证:DS4Android的诞生与成长,欢迎star

1.留图镇楼:双链表的最终实现的操作效果:

双链表操作合集.gif

2.对于双链表简介:
双链表是对节点(Node)的操作,而节点(Node)又承载数据(T)  
总的来看,双链表通过操作节点(Node)从而操作数据(T),就像车厢运送获取,车厢只是载体,货物是我们最关注  
双链表不同于单链表至处在于一个节点同时持有前、后两个节点的引用,使得对头尾操作都方便 

Node只不过是一个辅助工具,并不会暴露在外。它与数据相对应,又使数据按链式排布,
操纵节点也就等于操纵数据,就像提线木偶,并不是直接操作木偶的各个肢体本身(数据T)。

为了统一节点的操作,通常在链表最前面添加一个虚拟头(headNode)和虚拟尾(tileNode)(封装在内中,不暴露)
复制代码

双链表.png


3.双链表的实现:本文要务

本文要务.png


一、双链表结构的实现: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的连接

双链表添加.png

/**
 * 根据目标节点插入新节点--目标节点之前
 *
 * @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孤独的离去...

双链表删除节点.png

/**
 * 移除目标节点
 *
 * @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)开始,不带你们玩了,
于是火车头和火车尾,手牵手,走向远方...

双链表清空.png

/**
 * 清空所有节点
 */
private void clearNode() {
    //实例化头结点
    headNode = new Node<T>(null, null, null);
    //实例化尾节点,并将prev指向头
    tailNode = new Node<T>(headNode, null, null);
    headNode.next = tailNode;
    //链表长度置零
    size = 0;
}
复制代码

二、利用链表实现对数据的操作

链表只是对节点的操作,只是一种结构,并非真正目的,最终要让链表对外不可见,就像人的骨骼之于躯体
躯体的任何动作是骨骼以支撑,而骨骼并不可见,从外来看只是躯体的动作而已。
我们需要的是按照这种结构对数据进行增删改查等操作,并暴露接口由外方调用

1、定点添加操作--add

定点添加.gif

@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

定点删除.gif

@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

双链表更新与查询.gif

@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);
    }
}
复制代码

本系列后续更新链接合集:(动态更新)

后记:捷文规范


2.本文成长记录及勘误表
项目源码 日期 备注
V0.1--github 2018-11-23 看得见的数据结构Android版之双链表的实现
3.更多关于我
笔名 QQ 微信 爱好
张风捷特烈 1981462002 zdl1994328 语言
我的github 我的简书 我的掘金 个人网站
4.声明

1----本文由张风捷特烈原创,转载请注明
2----欢迎广大编程爱好者共同交流
3----个人能力有限,如有不正之处欢迎大家批评指证,必定虚心改正
4----看到这里,我在此感谢你的喜欢与支持


icon_wx_200.png

关注下面的标签,发现更多相似文章
评论