美文网首页手机移动程序开发Android开发Android进阶之路
看得见的数据结构Android版之单链表篇

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

作者: e4e52c116681 | 来源:发表于2018-11-24 11:18 被阅读8次

    零、前言

    1.前面用数组实现了表结构,也分析了数组表的局限性(头部修改困难)
    2.今天来讲另一种数据结构：单链表，它是一种最简单的动态数据结构
    3.链表有点像火车，一节拴着一节,想要在某节后加一节，打开连接处，再拴上就行了
    4.本例操作演示源码：希望你可以和我在Github一同见证：DS4Android的诞生与成长，欢迎star

    1.留图镇楼：单链表的最终实现的操作效果:
    单链表操作合集.gif
    2.对于单链表简介：
    单链表是对节点(Node)的操作，而节点(Node)又承载数据(T)  
总的来看，单链表通过操作节点(Node)从而操作数据(T)，就像车厢运送获取，车厢只是载体，货物是我们最关注

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

为了统一节点的操作，通常在链表最前面添加一个虚拟头结点(避免对头部单独判断)
    一个链表.png

    注意：单链表的实际使用场景并不多，因为有比他更厉害的双链表
    在某些特定场景，比如只是频繁对头结点进行操作，单链表最佳，
    单链表的讲解为双链表做铺垫，直接讲双链表肯跨度有点大。作为数据结构之一，还是要不要了解一下。

    3.单链表的实现：本文要务
    单链表实现表结构.png

    一、单链表结构的实现：SingleLinkedChart

    1.表的接口定义在数组表篇，这里就不贴了

    这里给出实现接口后的SingleLinkedChart以及简单方法的实现

    /**
 * 作者：张风捷特烈<br/>
 * 时间：2018/11/22 0022:15:36<br/>
 * 邮箱：1981462002@qq.com<br/>
 * 说明：单链表实现表结构
 */
public class SingleLinkedChart<T> implements IChart<T> {
    private Node headNode;//虚拟头结点
    private int size;//元素个数

    public SingleLinkedChart() {
        headNode = new Node(null, null);
        size = 0;
    }
    
    @Override
    public void add(int index, T el) {
    }

    @Override//默认添加到头部
    public void add(T el) {
        add(0, el);
    }

    @Override//默认删除头部
    public T remove(int index) {
        return null;
    }

    @Override
    public T remove() {
        return remove(0);
    }

    @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);
        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)的设计：

    SingleLinkedChart相当于一列火车，暂且按下，先把车厢的关系弄好，最后再拼接列车会非常方便
    这里将Node作为SingleLinkedChart的一个私有内部类，是为了隐藏Node，并能使用SingleLinkedChart的资源
    就像心脏在身体内部，外面人看不见，但它却至关重要，并且还能获取体内的信息与资源
    一节车厢，最少要知道里面的货物(node.T)是什么,它的下一节车厢(node.next)是哪个

     /**
 * 内部私有节点类
 */
private class Node {
    /**
     * 节点数据元素
     */
    private T el;
    /**
     * 下一节点的引用
     */
    private Node next;
    private Node(Node next, T el) {
        this.el = el;
        this.next = next;
    }
}

    二、节点(Node)的底层操作(CRUD)----链表的心脏

    1.查找车厢：

    比如你的可视区域就是一节车厢的长度，一开始只能看见火车头
    从火车头开始，你需要一节一节往下找，也就相当于，列车每次开一节，到你想要的位置，就停下来
    这是你就能查看车厢的货物(get到节点数据)，如何用代码来模拟呢?

    单链表查询.png 
    /**
 * 根据索引寻找节点
 *
 * @param index 索引
 * @return 节点
 */
private Node getNode(int index) {
    //声明目标节点
    Node targetNode = headNode;
    for (int i = 0; i < index; i++) {//火车运动驱动源
        //一节一节走，直到index
        targetNode = targetNode.next;
    }
    return targetNode;
}

    可以检测一下：index=0时，targetNode = targetNode.next 执行1次，也就获得了T0车厢
    index=1时，targetNode = targetNode.next 执行2次，也就获得了T1车厢...

    2.定点插入

    还是想下火车头：想在2号车厢(target)和1号车厢之间插入一节T4车厢怎么办?
    第一步：找到2号车厢的前一节车厢--1号厢(target-1)
    第二步：将1号厢(target-1)的链子(next)栓到T4车厢上，再把T4的链子栓到2号车厢(target)

    节点插入.png 
    /**
 * 在指定链表前添加节点
 *
 * @param index 索引
 * @param el    数据
 */
private void addNode(int index, T el) {
    Node preTarget = getNode(index - 1);//获取前一节车厢
    //新建节点,同时下一节点指向target的下一节点--
    //这里有点绕,分析一下:例子：2号车厢和1号车厢之间插入一节T4车厢
    //preTarget：1号车厢   preTarget.next：2号车厢
    //T4车厢:new Node(preTarget.next, el)---创建时就把链子拴在了：preTarget.next：2号车厢
    Node tNode = new Node(preTarget.next, el);
    //preTarget的next指向tNode--- 1号车厢栓到T4车厢
    preTarget.next = tNode;
    size++;
}
    3.定点修改

    你要把车厢的货物换一下，这还不简单，找到车厢，换呗

    /**
 * 修改节点
 * @param index 节点位置
 * @param el 数据
 * @return 修改后的节点
 */
private Node<T> setNode(int index, T el) {
    Node<T> node = getNode(index);
    node.el = el;
    return node;
}
    4.定点移除

    要把T1车厢移除：T0和T2手拉手，好朋友，T1被孤立了，把自己的链子拿掉，伤心地走开...

    单链表删除.png 
    /**
 * 移除指定索引的节点
 *
 * @param index 索引
 * @return 删除的元素
 */
private T removeNode(int index) {
    Node preTarget = getNode(index - 1);//获取前一节车厢
    Node target = preTarget.next;//目标车厢
    //前一节车厢的next指向目标车厢下一节点
    preTarget.next = target.next;//T0和T2手拉手
    target.next = null;//T1把自己的链子拿掉,伤心地走开...
    size--;
    return target.el;
}

    三、节点(Node)的操作完成了，下面拼火车吧(SingleLinkedChart)

    感觉真正的链表就是一个包装壳，暴漏了操作接口给外界，内部劳苦功高的还是Node
    这种封装在编程里非常常见，有些闻名遐迩的类中有很多都是默默无闻的大佬

    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(index + 1, el);
    //为了接口规范,计数从0开始,而链表没有索引概念，只是第几个,T0被认为是第一节车厢。
    //比如选中点2---说明是目标是第3节车厢，所以index + 1 =2+1
}
    2.定点移除操作--remove

    处于单链表的特点：头部删除容易，尾部删除要查询一遍，所以默认是删除在头部

    定点删除操作.gif 
    @Override
public T remove(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Remove failed. Illegal index");
    }
    return removeNode(index + 1);//同理
}
    3.获取和修改--get和set
    get和set操作.gif 
    @Override
public T set(int index, T el) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Set failed. Illegal index");
    }
    return setNode(index + 1, el).el;
}

@Override
public T get(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Get failed. Illegal index");
    }
    return getNode(index + 1).el;
}

    四、其他操作

    其他操作.gif
    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 != 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 SingleLinkedChart)) {
    return null;
    }

    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Contact failed. Illegal index");
    }
    SingleLinkedChart<T> linked = (SingleLinkedChart<T>) iChart;
    Node firstNode = linked.getHeadNode().next;//接入链表 头结点
    Node lastNode = linked.getLastNode();//接入链表 尾结点
    Node target = getNode(index + 1);//获取目标节点
    Node targetNext = target.next;//获取目标节点的下一节点
    target.next = firstNode;//获取目标节点的next连到 接入链表 头结点
    lastNode.next = targetNext; //待接入链表 尾结点连到 目标节点的下一节点
    return this;
}

public Node getHeadNode() {
    return headNode;
}
public Node getLastNode() {
    return getNode(size);
}
///////////////////////////////////////////////////////////////

    五、单链表小结：

    1.简单测试
    方法\数量 1000 10000 10W 100W 1000W
    add首 0.0002秒 0.0009秒 0.0036秒 0.5039秒 3.1596秒
    add尾 0.0029秒 0.1096秒 9.1836秒 ---- ----
    remove首 0.0001秒 0.0016秒 0.0026秒 0.0299秒 0.1993秒
    remove尾 0.0012秒 0.1009秒 8.9750秒 ---- ----
    2.优劣分析
    优点：  动态创建，节省空间  
        头部添加容易  
缺点：  空间上不连续，造成空间碎片化
        查找困难，只能从头开始一个一个找
使用场景：完全可用双链表替代，只对前面元素频繁增删，单链表优势最高。
    3.最后把视图一起说了吧

    接口都是相同的，底层实现更换了，并不会影响视图层，只是把视图层的单体绘制更改一下就行了。
    详细的绘制方案见这里

    /**
 * 绘制表结构
 *
 * @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++) {
        SingleNode 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) {
            SingleNode box_next = mArrayBoxes.get(i + 1);
            if (i % 6 == 6 - 1) {//边界情况
                mPath.rLineTo(0, Cons.BOX_HEIGHT);
                mPath.rLineTo(-Cons.BOX_WIDTH / 2, 0);
                mPath.lineTo(box_next.x + Cons.BOX_WIDTH / 2f, box_next.y);
                mPath.rLineTo(Cons.ARROW_DX, -Cons.ARROW_DX);
            } else {
                mPath.rLineTo(0, Cons.BOX_HEIGHT / 2f);
                mPath.lineTo(box_next.x, box_next.y + Cons.BOX_HEIGHT / 2f);
                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);
    }
}

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

    后记：捷文规范

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

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

    icon_wx_200.png

    相关文章

      网友评论

        本文标题：看得见的数据结构Android版之单链表篇

        本文链接：https://www.haomeiwen.com/subject/gnbeqqtx.html

        延伸阅读

        深度阅读

        • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

        栏目导航

        热点阅读

        手机移动程序开发

        Android开发

        Android进阶之路

        数据结构和算法分析

        数据结构

        图解数据结构

        关于我们|服务条款|联系我们|看得见的数据结构Android版之单链表篇|投稿指南|网站地图|RSS订阅|排版工具|手机版

        提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

        Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

        备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

        本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

        所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！