02--图解数据结构之单链表实现集合

链表是一种线性的数据结构 是一种最简单的动态数据结构

优点:  动态创建,节省空间  
        头部添加容易  
缺点:空间上不连续,查找困难。只能从头开始一个一个找
对于单链表:
链表类Node的成员变量有:T类型的数据和Node类型的节点,并且成员变量node指向下一个节点。
为了统一节点的操作,通常在链表最前面添加一个虚拟头结点

链表.png

一个链表.png

我想再强调一下数据结构的作用是为数据寻找一个合适的载体,让数据的操作更加快捷。
Node只不过是一个辅助工具,并不会暴露在外。它与数据相对应,又使数据按链式排布,
操纵节点也就等于操纵数据,就像提线木偶,我们操作的是"观众"所看不见的线,而不是木偶的各个肢体本身。

一、单链表实现集合:SingleLinkedGroup

1.节点类的设计
 /**
  * 内部私有节点类
  * @param <T>
  */
 private class Node<T>{
     /**
      * 节点数据元素
      */
     public T el;
     
     /**
      * 下一节点的引用
      */
     public Node next;
     
    public Node(T el, Node next) {
        this.el = el;
        this.next = next;
    }
    
    @Override
    public String toString() {
        return el.toString();
    }
 }
2.SingleLinkedGroup继承自Group 基类见第一篇
public class SingleLinkedGroup<T> extends Group<T> {

    /**
     * 虚拟头结点
     */
    private Node headNode;

    public SingleLinkedGroup() {
        clear();
    }

    @Override
    public void add(int index, T el) {

    }

    @Override
    public T remove(int index) {
        return null;
    }

    @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 new int[0];
    }

    @Override
    public Group<T> contact(int index, Group<T> group) {
        return null;
    }
    /////Node类见上方
}

二、底层节点操作

1.定点插入

1---新节点的next指向目标节点 2---目标节点的上一节点(即data1)的next指向新节点 3---增加size

添加节点.png

/**
 * 在指定链表前添加节点
 *
 * @param index 索引
 * @param el    数据
 */
private void addNode(int index, T el) {
    Node<T> target = getNode(index - 1);
    //新建节点,同时下一节点指向target的下一节点
    Node<T> tNode = new Node<>(target.next, el);
    //目标节点的next指向新节点
    target.next = tNode;
    size++;
}
2.定点获取

思路:链表查找只能一个一个挨着找,就像排队报数样。

/**
 * 根据索引寻找节点
 * @param index 索引
 * @return 节点
 */
private Node<T> getNode(int index) {
    //声明目标节点
    Node<T> targetNode = headNode;
    for (int i = 0; i < index; i++) {
        //一个挨着一个找,直到index
        targetNode = targetNode.next;
    }
    return targetNode;
}
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.定点移除

思路:目标节点的前一节点的next指向目标节点的下一节点(即把元素孤立) 把目标节点的next指向为null

链表移除节点.png

/**
 * 移除指定索引的节点
 *
 * @param index 索引
 * @return 删除的元素
 */
private T removeNode(int index) {
    //目标节点前一节点
    Node<T> targetPrev = getNode(index - 1);
    //目标节点
    Node<T> target = targetPrev.next;
    //目标节点前一节点的next指向目标节点下一节点
    targetPrev.next = target.next;
    target.next = null;
    size--;
    return target.el;
}

三、集合类外部访问接口实现

1、增:添加--add
@Override
public void add(int index, T el) {
    // index可以取到size,在链表末尾空位置添加元素。
    if (index+1 < 0 || index > size) {
        throw new IllegalArgumentException("Add failed. Illegal index");
    }
    addNode(index + 1, el);
}
2.删:移除--remove
@Override
public T remove(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Remove failed. Illegal index");
    }
    return removeNode(index + 1);
}
3.该:修改--set
@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;
}
4.查:获取--get
@Override
public T get(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Get failed. Illegal index");
    }
    //消除headNode影响,所以+1
    return getNode(index + 1).el;
}
5.测试
SingleLinkedGroup<String> list = new SingleLinkedGroup<>();
list.addFirst("特");
list.addLast("烈");
list.addFirst("风");
list.addFirst("张");
list.add(2, "杰");
list.set(2, "捷");
System.out.println(list);
//head: 张->风->捷->特->烈->NULL
for (int i = 0; i < list.size(); i++) {
    System.out.print(list.get(i));//张风捷特烈
}
list.remove(2);
//head: 张->风->特->烈->NULL
System.out.println(list);
list.clear();
System.out.println(list);//head: NULL

四、其他操作

1.根据指定元素获取匹配索引
@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;
}
2.定点连接两个链表式集合
 @Override
 public Group<T> contact(int index, Group<T> group) {
     SingleLinkedGroup<T> linkedGroup = (SingleLinkedGroup<T>) group;
     //获取待接入链表 头结点
     Node firstNode = linkedGroup.getHeadNode().next;
     //获取待接入链表 尾结点
     Node lastNode = linkedGroup.getLastNode();
     //获取目标节点
     Node<T> target = getNode(index+1);
     //获取目标节点的下一节点
     Node targetNext = target.next;
     //获取目标节点的next连到 接入链表 头结点
     target.next = firstNode;
     //待接入链表 尾结点连到 目标节点的下一节点
     lastNode.next = targetNext;
     return this;
 }
 
public Node getHeadNode() {
    return headNode;
}
public Node getLastNode() {
    return getNode(size);
}
2.其他方法测试:
        SingleLinkedGroup<String> linkedGroup = new SingleLinkedGroup<>();
        linkedGroup.addLast("a");
        linkedGroup.addLast("b");
        linkedGroup.addLast("a");
        linkedGroup.addLast("c");
        linkedGroup.addLast("a");

        System.out.println(linkedGroup);
        //head: a->b->a->c->a->NULL

        //获取a元素的所有索引位置
        int[] as = linkedGroup.getIndex("a");
        for (int a : as) {
            System.out.print(a+" ");//0 2 4
        }

        //删除a元素第一次出现的地方---
        linkedGroup.removeEl("a");
        System.out.println(linkedGroup);
        //head: b->a->c->a->NULL

        //查看a元素是否存在
        boolean b = linkedGroup.contains("a");
        System.out.println(b);//true

        //删除所有a元素出现的地方---
        linkedGroup.removeEls("a");
        System.out.println(linkedGroup);
        //head: b->c->NULL
        
        SingleLinkedGroup<String> linkedGroup2 = new SingleLinkedGroup<>();
        linkedGroup2.addLast("1");
        linkedGroup2.addLast("3");
        linkedGroup2.addLast("2");
        linkedGroup.contact(1, linkedGroup2);
        System.out.println(linkedGroup);
        //head: b->c->1->3->2->NULL

五、时间测试:单链表式集合:SingleLinkedGroup测试

方法\数量

复杂度

1000

10000

10W

100W

1000W

addLast

O(n)

0.0029秒

0.1096秒

9.1836秒

----

----

addFirst

O(1)

0.0002秒

0.0009秒

0.0036秒

0.5039秒

3.1596秒

add

O(n)

--

--

--

--

--

removeLast

O(n)

0.0012秒

0.1009秒

8.9750秒

----

----

removeFirst

O(1)

0.0001秒

0.0016秒

0.0026秒

0.0299秒

0.1993秒

removeEl

O(n)

--

--

--

--

--

removeEls

O(n)

--

--

--

--

--

remove

O(n)

--

--

--

--

--

clear

O(1)

--

--

--

--

--

set

O(n)

--

--

--

--

--

get

O(n)

--

--

--

--

--

getIndex

O(n)

--

--

--

--

--


后记、

1.声明:

[1]本文由张风捷特烈原创,各图均由本人亲自所画,转载请注明 [2]欢迎广大编程爱好者共同交流 [3]个人能力有限,如有不正之处欢迎大家批评指证,必定虚心改正 [4]你的喜欢与支持将是我最大的动力

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

为什么跳槽加薪会比内部调薪要高?

之后的若干年加薪都是遵循企业内部晋升通道,如果企业加薪幅度赶不上同岗位市场薪酬回报的上涨幅度,就会出现题主所说的现象。

8510
来自专栏奇点大数据

话说量化(5)

钱是越多越好吗?这个问题似乎不用回答,那是肯定的啊。试问在座的各位看客哪位不是在挣钱,挣更多的钱,挣更多更多的钱的路上奔跑着的呢?钱是一种交换物质(当然也可以是...

10910
来自专栏奇点大数据

话说量化(2)

市场,是一个很古老的概念了,至少已经有三四千年以上的历史了。较早的关于市场的记录是在古埃及时期,公元前两千多年之前,就已经有“Bazar”这个概念了,汉语里面也...

12620
来自专栏奇点大数据

话说量化(4)

货币——也就是我们俗称的“钱”是世界上最可爱的东西之一,可以说没有它的刺激,也就没有我们现在这么繁荣的市场,也没有这么丰富的各类物质产品和幸福生活。

13120
来自专栏Grace development

“生于忧患,死于安乐”之程序员人生

没错,大多人的经历都是如此!这样艰苦的奋斗,不断的努力,使我们在这个行业立足。正是这份兴趣、这份毅力、这份坚持支撑着我们,才让我们走到了现在。

7410
来自专栏windealli

后台必备意识——柔性可用

柔性可用是指:当条件有限而不能向用户提供完美服务时,可以以柔性的方式提供有损的服务。

1.1K40
来自专栏编程坑太多

作为程序员,有没有让你感到既无语又崩溃的程序命名?

13930
来自专栏java一日一条

IT 已成为最疯狂的加班行业,没有之一

夜幕降临,当IT大楼里依然灯火通明时,那一刻,我仿佛王进喜、石传翔等劳模灵魂附体,我知道我不是一个在加班,我不是一个人!连续9个通宵加班都不是事,一点不夸张,这...

12520
来自专栏葡萄城控件技术团队

生产制造MES系统中,如何应用报表分析?

中国制造业产业结构逐步从低附加值传统加工制造业和资源密集型制造业向高附加值新型制造业转型升级。生产制造类企业为了监控项目进度和产品生产情况,会需要制作大量的报表...

34630
来自专栏奇点大数据

话说量化(1)

从今天开始,我来写一个叫做《话说量化》的随笔。主要是最近自己业余也在玩量化交易的模型,那就把一路玩的过程中的感想和碰到的问题记下来,和一起玩的朋友们做个分享。既...

13620

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励