数据结构 模拟实现LinkedList单向不循环链表

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

目录

一、链表的简单介绍

二、链表的接口

三、链表的方法实现

(1)display方法

(2)size得到单链表的长度方法

(3)addFirst头插方法

(4)addLast尾插方法

(5)addIndex指定位置插入方法

(6)contains方法

(7)remove删除第一个key值节点的方法

(8)removeAllKey删除所有值为key的方法

(9)clear方法

四、最终代码


一、链表的简单介绍

概念:链表是一种物理存储结构不连续,逻辑上是连续的;链表类似现实中的火车,一节车厢连着一节车厢,而链表是通过链表之间的引用进行连接,构成一节一节的数据结构。如图:

数据结构 模拟实现LinkedList单向不循环链表,数据结构,链表,java数据结构 模拟实现LinkedList单向不循环链表,数据结构,链表,java


二、链表的接口

代码如下:

public interface Ilist {
    //头插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
    void addIndex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);
    //删除第一次出现关键字为key的节点
    void remove(int key);
    //删除所有值为key的节点
    void removeAllKey(int key);
    //得到单链表的长度
    int size();
    void clear();
    void display();
}

三、链表的方法实现

创建一个类,实现接口,重写方法,链表中的方法都在里面实现。类里面有链表类,也是内部类,有val值,next域,还有记录第一个节点的头结点,代码如下:

public class MyLinkedList implements Ilist{

    public ListNode head;

    static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
}

我们先创建一个方法,方法里面会创建几个节点,代码如下:

public void createList() {
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;
    }

调用这个方法,就会创建出含有5个节点的链表,在test类里面创建main方法,调用此方法后的结果,结果如图:

数据结构 模拟实现LinkedList单向不循环链表,数据结构,链表,java

(1)display方法

此方法可以显示链表中所有元素,也就是遍历一遍链表,打印val值,代码如下:

public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

调用该方法执行结果如下:
数据结构 模拟实现LinkedList单向不循环链表,数据结构,链表,java

(2)size得到单链表的长度方法

要得到链表的长度,就要遍历一遍链表,定义一个变量进行统计个数,代码如下:

public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

执行结果:

数据结构 模拟实现LinkedList单向不循环链表,数据结构,链表,java

(3)addFirst头插方法

头插就要把要插入的节点当做头结点,要插入的元素next域指向当前头结点,再把头结点定成插入的元素。

代码:

public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(this.head == null) {
            this.head = node;
        } else {
            node.next = this.head;
            this.head = node;
        }
    }

调用此方法,多条语句后的执行结果如下:
数据结构 模拟实现LinkedList单向不循环链表,数据结构,链表,java

(4)addLast尾插方法

尾插就是要在链表的尾节点后插入节点,代码如下:

public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(this.head == null) {
            this.head = node;
        } else {
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

执行结果如下:

数据结构 模拟实现LinkedList单向不循环链表,数据结构,链表,java

(5)addIndex指定位置插入方法

我们这里规定第一个节点的位置是0,第二个节点位置为1,依次往后推,我们要指定某一位置插入节点,先要检查插入位置是否合法,不合法抛出异常;合法在指定位置插入节点,如果指定位置是0,就是头插,指定位置是节点个数的size,就是尾插;中间位置,我们要找到指定位置的前一个节点,插入节点的next域指向前一个节点的next节点,前一个节点的next域指向插入节点,代码如下:

    public void addIndex(int index, int data) {
        try {
            if(index < 0 || index > size()) {
                throw new IndexException("下标异常,下标:" + index);
            } else {
                if(index == 0) {
                    //头插
                    addFirst(data);
                    return;
                }
                if (index == size()) {
                    //尾插
                    addLast(data);
                    return;
                }
                ListNode node = new ListNode(data);
                ListNode cur = searchPrev(index);
                node.next = cur.next;
                cur.next = node;
            }
        } catch (IndexException e) {
            e.printStackTrace();
        }
    }
    //找到链表前一个的位置
    private ListNode searchPrev(int index) {
        ListNode cur = this.head;
        int count = 0;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

public class IndexException extends RuntimeException{
    public IndexException(String e) {
        super(e);
    }
}

(6)contains方法

查找是否包含关键字key是否在单链表当中,遍历一遍链表,有该元素就返回true,没有就返回false,代码如下:

public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

(7)remove删除第一个key值节点的方法

删除一个节点,先要判断该链表为不为空,为空就退出;不为空,看要删的节点是不是头结点,是头结点就直接把头结点改成头结点的next域;要删除的节点可能在中间,就要扎到要删除节点的前一个节点,把前一个节点的next域指向要删除节点的next域就好了,代码如下:

public void remove(int key) {
        if(this.head == null) {
            //一个节点都没有,无法删除
            return;
        }
        if(this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = findPrev(key);
        if(cur == null) {
            System.out.println("没有要删除的点");
        } else {
            ListNode del = cur.next;
            cur.next = del.next;
        }
    }

    private ListNode findPrev(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                break;
            }
            cur = cur.next;
        }
        return cur == this.head ? null : cur;
    }

执行结果如下:

数据结构 模拟实现LinkedList单向不循环链表,数据结构,链表,java

(8)removeAllKey删除所有值为key的方法

如果头结点是空的,就不用进行下面操作,直接返回。

两个节点,一个的前节点,一个是前节点的后一个节点,遍历后一个节点,判断后一个节点的val值是不是key,是key就把前一个节点的next域指向后一个节点的next域,后一个节点向后移,没有命中后一个节点==key这条件,前一个节点和后一个节点都要往后移动一步。

最后还要判断头结点的val值是否等于key值,是就要把head标记成head的next域。

代码入如下:

public void removeAllKey(int key) {
        if(this.head == null) {
            return;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while (cur != null) {
            if(cur.val == key) {
                prev.next =cur.next;
                cur = cur.next;
            } else {
                cur = cur.next;
                prev = prev.next;
            }
        }
        if(this.head.val == key) {
            this.head = this.head.next;
        }
    }

执行结果如下:

数据结构 模拟实现LinkedList单向不循环链表,数据结构,链表,java

(9)clear方法

清除所有节点,有两种解决方案,第一种是直接把头结点设为空,这种方法比较暴力;第二种是把每个节点的next域设为空,同时val也要设为空,因为这里的val类型是int,所以就设置不了空了,最后再把head节点设为空,代码如下:

 public void clear() {
        ListNode cur = this.head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        head = null;
    }

执行结果如下:

数据结构 模拟实现LinkedList单向不循环链表,数据结构,链表,java文章来源地址https://www.toymoban.com/news/detail-773316.html


四、最终代码

public class MyLinkedList implements Ilist{

    public ListNode head;

    static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public void createList() {
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;
    }

    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(this.head == null) {
            this.head = node;
        } else {
            node.next = this.head;
            this.head = node;
        }
    }

    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(this.head == null) {
            this.head = node;
        } else {
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        try {
            if(index < 0 || index > size()) {
                throw new IndexException("下标异常,下标:" + index);
            } else {
                if(index == 0) {
                    //头插
                    addFirst(data);
                    return;
                }
                if (index == size()) {
                    //尾插
                    addLast(data);
                    return;
                }
                ListNode node = new ListNode(data);
                ListNode cur = searchPrev(index);
                node.next = cur.next;
                cur.next = node;
            }
        } catch (IndexException e) {
            e.printStackTrace();
        }
    }
    //找到链表前一个的位置
    private ListNode searchPrev(int index) {
        ListNode cur = this.head;
        int count = 0;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(this.head == null) {
            //一个节点都没有,无法删除
            return;
        }
        if(this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = findPrev(key);
        if(cur == null) {
            System.out.println("没有要删除的点");
        } else {
            ListNode del = cur.next;
            cur.next = del.next;
        }
    }

    private ListNode findPrev(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                break;
            }
            cur = cur.next;
        }
        return cur == this.head ? null : cur;
    }

    @Override
    public void removeAllKey(int key) {
        if(this.head == null) {
            return;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while (cur != null) {
            if(cur.val == key) {
                prev.next =cur.next;
                cur = cur.next;
            } else {
                cur = cur.next;
                prev = prev.next;
            }
        }
        if(this.head.val == key) {
            this.head = this.head.next;
        }
    }

    @Override
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    @Override
    public void clear() {
        ListNode cur = this.head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        head = null;
    }

    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

//自定义异常类
public class IndexException extends RuntimeException{
    public IndexException(String e) {
        super(e);
    }
}

点个赞再走吧,谢谢谢谢谢!

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

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

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

相关文章

  • 指针穿梭,数据流转:探秘C语言实现单向不带头不循环链表

    本篇博客会讲解链表的最简单的一种结构:单向+不带头+不循环链表,并使用C语言实现。 链表是一种线性的数据结构,而本篇博客讲解的是链表中最简单的一种结构,它的一个结点的声明如下: 一个Node中包含2个部分:data用来存储数据,被称作“数据域”;next用来存储一个

    2024年02月05日
    浏览(50)
  • 数据结构——实现单向链表

    单链表是一种常见的数据结构,用于存储一系列的数据元素,每个节点包含数据和指向下一个节点的指针。 单链表通常用于实现某些算法或数据结构,如链式前向星、哈希表、链式栈、队列等等。 单链表在程序设计中的作用不可忽略,是很多基础算法的核心数据结构之一。

    2024年02月07日
    浏览(57)
  • 【数据结构】单向链表实现 超详细

    目录 一. 单链表的实现 1.准备工作及其注意事项 1.1 先创建三个文件 1.2 注意事项:帮助高效记忆和理解 2.链表的基本功能接口 2.0 创建一个 链表 2.1 链表的 打印  3.链表的创建新节点接口 4.链表的节点 插入 功能接口 4.1 尾插接口 4.2 头插接口     4.3 指定位置 pos 之前  插入

    2024年02月19日
    浏览(66)
  • 【数据结构和算法】使用数组的结构实现链表(单向或双向)

    上文我们通过结构体的结构实现了队列 、以及循环队列的实现,我们或许在其他老师的教学中,只学到了用结构体的形式来实现链表、队列、栈等数据结构,本文我想告诉你的是,我们 可以使用数组的结构实现链表、单调栈、单调队列 目录 前言 一、用数组结构的好处 1.数

    2024年01月20日
    浏览(74)
  • 数据结构(Java实现)LinkedList与链表(上)

    链表 逻辑结构 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。 链表的实现 创建一个链表 遍历单链表 、 得到

    2024年02月11日
    浏览(53)
  • 数据结构(Java实现)LinkedList与链表(下)

    ** ** 结论 让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。 LinkedList的模拟实现 单个节点的实现 尾插 运行结果如下: 也可以暴力使用 全部代码 MyLinkedList IndexOut

    2024年02月11日
    浏览(46)
  • 数据结构:详解【链表】的实现(单向链表+双向链表)

    1.顺序表的问题和思考 问题: 中间/头部的插入删除,时间复杂度为O(N)。 增容需要申请新空间,拷贝数据,释放旧空间,会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据

    2024年03月26日
    浏览(65)
  • 【数据结构】_4.List接口实现类LinkedList与链表

    目录 1.链表的结构与特点 1.1 链表的结构: 1.2 链表的特点: 2. 不带头单链表的模拟实现 3. 单链表OJ 3.1 题目1:移除链表元素:  3.2 题目2:反转一个单链表 3.3 题目3:返回链表的中间结点 3.4 题目4:链表的倒数第k个结点 3.5 题目5:合并两个有序链表 3.6 题目6:链表的回文结构

    2024年02月15日
    浏览(45)
  • 数据结构单向循环链表,创建以及增删改查的实现

    循环链表: 是另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向头节点,整个链表形成一个环。 单向循环链表的操作和单链表操作基本一致,差别在于:当链表遍历时,判别当前指针p是否指向表尾结点的终止条件不同。在单链表中,判别条件一般为p!=

    2024年02月16日
    浏览(50)
  • 数据结构三:线性表之单链表(带头结点单向)的设计与实现

            线性表的链式存储结构正是所谓的单链表,何谓单链表?通过地址将每一个数据元素串起来,进行使用,这可以弥补顺序表在进行任意位置的插入和删除需要进行大量的数据元素移动的缺点,只需要修改指针的指向即可;单链表的种类又可划分为很多种,本篇博客详

    2024年02月19日
    浏览(62)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包