【数据结构】实现单链表的增删查

这篇具有很好参考价值的文章主要介绍了【数据结构】实现单链表的增删查。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.定义接口

public interface SeqList<E>{
    //默认尾插
    void add(E element);
    // 在线性表中插入新元素,插入后的元素下标为index
    void add(int index,E element);
    //头插
    public void addFirst(E val);
    // 删除当前线性表中索引为index的元素,返回删除的元素值
    E removeByIndex(int index);
    // 删除当前线性表中第一个值为element的元素
    void removeByValue(E element);
    // 删除当前线性表中所有值为element的元素
    void removeAllValue(E element);
    // 将当前线性表中index位置的元素替换为element,返回替换前的元素值
    E set(int index,E element);
    //返回索引位index的元素
    E get(int index);
    //查询是否包含element元素
    boolean contains(E element);
}

2.无头单链表实现接口

链表类和节点类的定义:

public class SingleLinkedList<E> implements SeqList<E>{
    private Node head ;//第一节车厢的地址
    private int size;//车厢节点的个数,保存的元素个数

    //定义一个车厢类,车厢作为火车的私有内部类,对外部完全隐藏
    private class Node{
        E val;//保存的元素
        Node next;//下一节车厢的地址
        //构造方法
        Node(E val){
            this.val=val;
        }
    }
 }

2.1 头插addFirst

public void addFirst(E val){
	Node node=new Node(val);
	node.next=head;
	node=head;
	size++;
}

图解:

【数据结构】实现单链表的增删查,数据结构,数据结构,java,链表

2.2 尾插add

从中间位置插入:

	@Override
    public void add(int index, E element) {
        if(index<0||index>size){
            throw new IllegalArgumentException("add index ILLegal");
        }
        //判断没有前驱的情况
        if(index==0){
            addFirst(element);
            return;
        }
        //中间位置插入
        Node prey=head;
        for(int i=0;i<index-1;i++){
            prey=prey.next;
        }
        Node node=new Node(element);
        node.next=prey.next;
        prey.next=node;
        size++;
    }

图解:假定index=2
【数据结构】实现单链表的增删查,数据结构,数据结构,java,链表

尾插:

    @Override
    public void add(E element) {
        add(size,element);
    }

2.3 删除元素remove

删除当前线性表中索引为index的元素,返回删除的元素值:

    @Override
    public E removeByIndex(int index) {
        if(rangeCheck(index)){
            throw new IllegalArgumentException("remove index Illegal");
        }
        //头节点的删除
        if(index==0){
            Node node=head;
            head=head.next;
            node.next=null;
            size--;
            return node.val;
        }
        //中间位置删除
        Node prey=head;
        for(int i=0;i<index-1;i++){
            prey=prey.next;
        }
        Node node=prey.next;
        prey.next=node.next;
        node.next=null;
        size--;
        return node.val;
    }

图解:

【数据结构】实现单链表的增删查,数据结构,数据结构,java,链表

删除当前线性表中第一个值为element的元素:

    @Override
    public void removeByValue(E element) {
        //1.base case
        if(head==null){
            return;
        }
        //2.判断头节点恰好是待删除的节点
        if(head.val.equals(element)){
            head=head.next;
            size--;
            return;
        }
        //3.此时头节点不为空其一定不是待删除的节点
        Node prey=head;
        while(prey.next!=null){
            if(prey.next.equals(element)){
                prey.next=prey.next.next;
                size--;
                return;
            }
            prey=prey.next;
        }
        //4.当前链表不存在值为element的元素
        System.out.println("当前链表不存在值为"+element+"的元素");
    }

删除当前线性表中所有值为element的元素:

    @Override
    public void removeAllValue(E element) {
        //1.base case
        if(head==null){
            return;
        }
        //2.若头节点就是待删除的节点且出现连续的待删除的节点
        while(head!=null && head.val.equals(element)){
            head=head.next;
            size--;
        }
        //整个链表已经删完了
        if(head==null){
            return;
        }
        //3.头节点一定不是待删除的元素且链表不为空
        Node prey=head;
        while(prey.next!=null){
            if(prey.next.val.equals(element)){
                prey.next=prey.next.next;
                size--;
            }else{
                //只有后继节点不是待删除的节点才能移动Prey的引用
                prey=prey.next;
            }
        }
    }

2.4 修改元素set

将当前线性表中index位置的元素替换为element,返回替换前的元素值:

    // 将当前线性表中index位置的元素替换为element,返回替换前的元素值
    @Override
    public E set(int index, E element) {
        if(!rangeCheck(index)){
            throw new IllegalArgumentException("set index illegal");
        }
        Node x=head;
        //遍历,走到index对应的元素
        for (int i = 0; i < index; i++) {
            x=x.next;
        }
        E oldVal=x.val;
        x.val=element;
        return oldVal;
    }
    //合法性校验
    private boolean rangeCheck(int index){
        if(index<0||index>=size){
            return false;
        }
        return true;
    }

2.5 获取元素get

返回索引为index的元素:

    @Override
    public E get(int index) {
        if(!rangeCheck(index)){
            throw new IllegalArgumentException("get index illegal");
        }
        Node x=head;
        for(int i=0;i<index;i++){
            x=x.next;
        }
        return x.val;
    }

3.带头单链表实现接口

【数据结构】实现单链表的增删查,数据结构,数据结构,java,链表

由于单链表中都需要额外处理头结点的情况,引入一个虚拟头结点,这个节点不存在具体的值,就作为链表的头来使用,使每个有值的节点都有一个前驱。(所有操作都统一了,无论是插入还是删除,都可以看作是中间位置的插入和删除)

链表类和节点类的定义:

public class SingleLinkedListWithHead <E> implements SeqList<E>{
    //当前链表一定存在火车头且不存储任何元素
    private Node dummyHead=new Node(null);
    //具体的元素个数
    private int size;
    private class Node{
        E val;
        Node next;
        Node(E val){
            this.val=val;
        }
    }
}

3.1 头插addFirst

    public void addFirst(E val){
        Node node=new Node(val);
        node.next=dummyHead.next;
        dummyHead.next=node;
        size++;
    }

图解:

【数据结构】实现单链表的增删查,数据结构,数据结构,java,链表文章来源地址https://www.toymoban.com/news/detail-628706.html

3.2 尾插add

    @Override
    public void add(E element) {
        add(size,element);
        return;
    }

    @Override
    public void add(int index, E element) {
        if(index<0||index>size){
            throw new IllegalArgumentException("Remove index illegal");
        }
        Node prey=dummyHead;
        for(int i=0;i<index;i++){
            prey=prey.next;
        }
        Node node=new Node(element);
        node.next=prey.next;
        prey.next=node;
        size++;
    }

3.3 删除元素remove

    @Override
    public void removeAllValue(E element) {
        //prey一定指向不是待删除的节点
        Node prev=dummyHead;
        while(prev.next!=null){
            if(prev.next.val==element){
                prev.next=prev.next.next;
                size--;
            }else{
                prev=prev.next;
            }
        }
    }

3.4 判断是否包含元素element

    @Override
    public boolean contains(E element) {
        while(dummyHead.next!=null){
            if(dummyHead.next.val.equals(element)){
                return true;
            }
            dummyHead.next=dummyHead.next.next;
        }
        return false;
    }

到了这里,关于【数据结构】实现单链表的增删查的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构—单链表的实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 1. 链表的概念及结构 2. 单链表的实现 2.1单链表头文件——功能函数的定义 2.2单链表源文件——功能函数的实现 2.3 单链表源文件——功能的测试 3.具体的理解操作图 4. 链表的分类 总结 世上

    2024年02月05日
    浏览(65)
  • 【数据结构】单链表的实现

    🌇个人主页:平凡的小苏 📚学习格言:别人可以拷贝我的模式,但不能拷贝我不断往前的激情 🛸C语言专栏:https://blog.csdn.net/vhhhbb/category_12174730.html 🚀数据结构专栏:https://blog.csdn.net/vhhhbb/category_12211053.html         家人们更新不易,你们的👍点赞👍和⭐关注⭐真的对我

    2023年04月09日
    浏览(65)
  • 【(数据结构)— 单链表的实现】

    概念: 链表是⼀种 物理存储结构上非连续、 非顺序的存储结构,数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的 。 链表的结构跟⽕⻋⻋厢相似,淡季时⻋次的⻋厢会相应减少,旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上,不会影响

    2024年02月08日
    浏览(51)
  • 【数据结构】-- 单链表的实现

    在前面我们学习了顺序表,顺序表在数组的基础上提供了很多现成的方法,方便了我们对数据的管理,但是我们也发现顺序表有着许多不足: 在处理大型的数据时,需要频繁的增容且在中间删除或插入数据时需要遍历顺序表,这些性质导致了顺序表的 效率较低 。这时我们就

    2024年04月27日
    浏览(52)
  • 【数据结构】单链表的层层实现!! !

    关注小庄 顿顿解馋(●’◡’●) 上篇回顾 我们上篇学习了本质为数组的数据结构—顺序表,顺序表支持下标随机访问而且高速缓存命中率高,然而可能造成空间的浪费,同时增加数据时多次移动会造成效率低下,那有什么解决之法呢?这就得引入我们链表这种数据结构 概念

    2024年03月12日
    浏览(162)
  • 【数据结构】单链表的简单实现

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元

    2024年02月04日
    浏览(57)
  • 【数据结构】双向链表的增删查改(C 代码实现)

    引入双向链表:关于单链表的问题与讨论 单链表存在的毛病: 因为单链表 只能单向 遍历链表, 对于 前插 这个操作,单链表必 须得找到所需前插节点位置的前一个 ,那么这时就得 从头指针重新遍历一次 链表,会造成时间复杂度大大增加。 没有头节点(哨兵位)无法删除

    2024年02月08日
    浏览(54)
  • 数据结构:单链表的实现(C语言)

    个人主页 : 水月梦镜花 个人专栏 : 《C语言》 《数据结构》 本博客将要实现的无头单向不循环链表。 我们将节点定义为如下结构: 其成员变量有data,next。 将int重命名为STLDataType,方便我们以后修改数据域的内容。 动态申明一个空间,来放置数据。如下: 将data的内容置

    2024年02月14日
    浏览(59)
  • 【数据结构】 链表简介与单链表的实现

    在【数据结构】 ArrayList简介与实战中我们已经熟悉了ArrayList的使用,并且进行了简单模拟实现。通过源码知道,ArrayList底层使用数组来存储元素 由于其底层是一段连续空间, 当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为

    2024年02月12日
    浏览(202)
  • 初阶数据结构之单链表的实现(四)

    链表的概念 :链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 所谓的逻辑结构其实就是能让我们自己能够更好的理解这个东西是什么?那么我们就用画图来理解理解吧!!在单链表中,存放着两个量,一个

    2024年02月06日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包