【数据结构】单向链表的模拟实现--Java

插入
void addFirst（int data）	头插入
void addLast（int data）	尾插入
void addindex（int indext，int data）	任意插入
查找
boolean contains（int key）	查找是否包含该元素
删除
void remove （int key）	删除第一次出现key元素
void removeAllKey（int key）	删除所有值为key的元素
void clear（）	清空
其他
int size（）	获取链表长度
void display（）	展示链表中的元素

接口中的代码：

public interface IList {
    //增
    public void addFirst(int data);
    public void addLast(int data);
    public void addindex(int index,int data);
    //查
    public boolean contains(int key);
    //删
    public void remove(int key);
    public void removeAllKey(int key);
    public void clear();
    //获取链表长度
    public int size();
    //展示链表元素
    public void display();
}

我们在建一个MySingleList类

首先我们重写接口中的方法

public class MySingleList implements IList{
    @Override
    public void addFirst(int data) {

    }
    @Override
    public void addLast(int data) {

    }
    @Override
    public void addindex(int key, int data) {

    }
    @Override
    public boolean contains(int key) {
        return false;
    }
    @Override
    public void remove(int key) {

    }
    @Override
    public void removeAllKey(int key) {

    }
    @Override
    public void clear() {

    }
    @Override
    public int size() {
        return 0;
    }
    @Override
    public void display() {

    }
}

接下来，我们要知道链表中包含什么东西，链表由一系列的节点组成，而节点中包含着数据以及指向下一个节点的指针。我模拟实现的是单向有头链表，所以MySingleList里面还有一个头节点。

 //节点：数据和下一个节点的指针
    public class ListNode {
        //数据
        public int val;
        //下一个节点的指针
        public ListNode next;
        //构造初始化
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

接下来就是实现MySinngleList中的方法了

二、🧆MySinngleList方法

我们先初始化链表和先写展示diaplay方法以及获取链表长度size，以便好测试代码：

0.🥧其他

createList：初始化链表

 public void createList(){
        ListNode node1=new ListNode(11);
        ListNode node2=new ListNode(22);
        ListNode node3=new ListNode(33);
        ListNode node4=new ListNode(44);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        head=node1;
    }

display（打印链表数据）：

 public void display() {
        //将cur从头节点开始
        ListNode cur=head;
        //遍历链表，直到链表为空为止
        //只要节点不为空，打印，到下一个节点
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    //换行：更方便一点
    System.out.println();
    }

size（获取长度）：

  public int size() {
        //从头遍历到末尾
        ListNode cur=head;
        int len=0;
        while(cur!=null){
            len++;
            cur=cur.next;
        }
        return len;
    }

假如链表数据如下：

1.🥧增加

1.🧇头插法（addFirst）：在头节点前插入一个节点；

在头节点前插入一个节点：

思路：

将该节点插入在头节点之前，所以该节点指向的下一个指针是原本的头节点；
将该节点插入在头节点之前，插入的节点变为头节点

注意：是先指向下一个指针，在变为头节点，如果反过来那么将会造成死循环，一直指向的是自己，下一个还是自己

addFirst代码：

   public void addFirst(int data) {
        ListNode cur=new ListNode(data);
        if(head==null){
            head=cur;
            return;
        }
        cur.next=head;
        head=cur;
    }

测试：

  //头插    
  public static void main(String[] args) {
        MySingleList mySingleList=new MySingleList();
        mySingleList.createList();
        mySingleList.display();
        mySingleList.addFirst(56);
        mySingleList.display();
    }

结果：

2.🧇尾插法（addLast）：在末尾插入一个节点

在末尾插入一个节点：

思路：

1.将cur从头遍历到倒数第一个；

2.将遍历到末尾的cur的下一个节点指向插入的节点。

注意：

这里要讨论head是否为null，如果为null直接插入；
将cur先从头遍历到倒数第二个，而不是遍历到末尾；

为什么cur遍历到倒数第二个，而不是最后一个？

如果遍历到最后一个节点：

当while（cur！=null）遍历到这个节点，随后又要跳到下一个节点，下一个节点是null，如果将null设置为插入的节点，插入的节点也无法与最后的节点衔接上；

如果遍历到倒数第二个节点：

while(cur.next!=null)遍历到倒数第二个节点，随后cur=cur.next他要跳到最后一个节点，跳出循环后将最后一个的下一个节点（指针）指向插入的节点。

addLast代码：

    //尾插
    public void addLast(int data) {
        ListNode node=new ListNode(data);
        //如果head等于null，直接将插入节点为头节点
        if(head==null){
            head=node;
            return;
        }
        //从头遍历到末尾
        ListNode cur=head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }

测试：

    public static void main(String[] args) {
        MySingleList mySingleList=new MySingleList();
        mySingleList.createList();
        mySingleList.display();
        mySingleList.addFirst(56);
        mySingleList.display();
        mySingleList.addLast(111);
        mySingleList.display();
    }

结果：

3.🧇任意插入（addindex）：在链表中任意插入一个节点；

既然是任意插入，那就有头插入和尾插入，以及中间插入，所以这里我们要想的是我们应该怎么进行中间插入。

思路：

1.遍历到插入下标的前一个节点；

2.将插入节点的下一个指针指向原本该位置的节点，和插入节点的前一个节点的下一个节点指向插入节点。

注意：

1.查看插入位置是否合法；

具体：

第一步：

链表的下标同样是从0开始，图中，我们是要将该节点插入到3下标下，既然如此，我们要先将下边遍历到插入的前一个节点的位置

第二步：

将插入位置的前一个节点的下一个指针指向插入节点，也就是将插入节点原来的下一个节点的指针，给插入节点的下一个节点，以及插入节点的指针指向原本所在该位置的节点。

addindex代码：

 public void addindex(int index, int data) {
        ListNode node=new ListNode(data);
        ListNode cur=head;
        //下标位置不合法
        if(index<0 || index>size()){
            System.out.println("插入位置不合法");
            return;
        }
        //头插入
        if(index==0){
            addFirst(data);
            return;
        }
        //尾插
        if(index==size()){
            addLast(data);
            return;
        }
        //中间插入
        if(index>0 || index<size()){
            //遍历到插入下标的前一个位置
            while(index-1!=0){
                cur=cur.next;
                index--;
            }
            //将原来的前一个节点的下一个指向的指针给插入的下一个指向的节点
            node.next=cur.next;
            //将原来的前一个节点的指向下一个指针指向插入节点
            cur.next=node;
        }
    }

测试：

   public static void main(String[] args) {
        MySingleList mySingleList=new MySingleList();
        mySingleList.createList();
        mySingleList.display();
        mySingleList.addindex(4,90);
        mySingleList.addindex(2,24);
        mySingleList.addindex(0,35);
        mySingleList.display();
    }

结果：

2.🥧查找

🧇查找是否包含元素（contains）：

思路：

1.遍历链表节点，查找是否有相同元素；

contians代码：

 public boolean contains(int key) {
        //从头遍历，查找是否有相同的元素
        ListNode cur=head;
        while (cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

测试：

    public static void main(String[] args) {
        MySingleList mySingleList=new MySingleList();
        mySingleList.createList();
        mySingleList.display();
        boolean ret= mySingleList.contains(22);
        System.out.println(ret);
    }

结果：

3.🥧删除

1.🧇remove：删除第一次出现的元素；

删除元素：

思路：

1.遍历链表节点，查找是否有相同元素；

2.遍历到删除节点的前一个节点，将原本删除该节点的上一个节点的下一个节点指向原本删除节点所在的下一个节点；

3.如果删除节点在头节点将原来的头节点设为头节点的下一个节点。

注意：
1.链表是否为空，如果为空，返回；

具体：

遍历到删除节点的前一个节点：

将原本删除该节点的上一个节点的下一个节点指向原本删除节点所在的下一个节点：

如果删除节点在头节点将原来的头节点设为头节点的下一个节点：

remove代码：

 public void remove(int key) {
        ListNode cur=head;
        ListNode del=new ListNode(key);
        //如果链表为空，直接返回
        if(head==null){
            return ;
        }
        //查看是否包含该元素
        if(!contains(key)){
            System.out.println("没有该元素，删除失败");
            return;
        }
        //如果要删除的元素在头节点
        if(head.val==key){
            //直接将头节点的下一个节点设为头节点
            head=head.next;
            return;
        }
        //遍历到要删除节点的上一个节点
        while(cur.next.val!=key){
            cur=cur.next;
        }
        del=cur.next;
        cur.next=del.next;
    }

测试：

  public static void main(String[] args) {
        MySingleList mySingleList=new MySingleList();
        mySingleList.createList();
        mySingleList.display();
        mySingleList.remove(22);
        mySingleList.remove(11);
        mySingleList.display();
        mySingleList.remove(12);
        mySingleList.display();
    }

结果：

2. 🧇removeAllkey：删除所有值为key的元素；

思路：

1.设置两个指针，一个从头指针开始，一个从头指针的下一个节点开始，遍历到要删除的元素位置，删除元素；

2.如果元素连续相同，同样的方法，元素不同，将cur的位置给prev，cur再跳到下一个节点

注意：

1.链表是否为空；

2.是否包含该指针；

3.如果元素在头节点，删除头节点；

删除一个元素后，元素连续的情况下：

删除一个元素后，元素不连续的情况下：

removeAllKey代码：

    public void removeAllKey(int key) {
        ListNode prev=head;
        ListNode cur=head.next;
        //链表是否为空
        if(head==null){
            return;
        }
        //是否包含该元素
        if(!contains(key)){
            System.out.println("没有该元素");
            return;
        }
        //删除元素
        while(cur!=null){
            if(cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        //如果元素在头节点
        if (head.val==key){
            head=head.next;
            return;
        }
        
    }

测试：

  public static void main(String[] args) {
        MySingleList mySingleList=new MySingleList();
        mySingleList.createList();
        mySingleList.addindex(3,33);
        mySingleList.display();
        mySingleList.removeAllKey(33);
        mySingleList.display();
    }

结果：

3.🧇clear：清空链表

思路：

第一种：将头节点设为null；（更直接）

第二种：所有节点为null；（更温柔）

第一种：

 public void clear() {
        head=null;
    }

第二种：

这里需要一个变量来记录一下cur.next，否则将其置为null，无法找到其下一个节点；

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

测试：

 public static void main(String[] args) {
        MySingleList mySingleList=new MySingleList();
        mySingleList.createList();
        mySingleList.display();
        mySingleList.clear();
        mySingleList.display();
    }

结果：

原文地址：https://blog.csdn.net/2301_80543957/article/details/143579649

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：diboot低代码中使用junit测试controller，入参不生效问题解决
下一篇：C语言第12节：指针(2)

MoneyPrinterTurbo - AI自动生成高清短视频
MoneyPrinterTurbo是一款基于AI大模型的开源软件，旨在通过一键操作帮助用户自动生成高清短视频。只需提供一个视频主题或 **关键词** ，就可以全自动生成视频文案、视频素材、视频字幕、
阅读更多2024-11-18
跨平台WPF框架Avalonia教程五
在 Avalonia 11 之前，控件主题是使用标准样式创建的。然而，这种方法存在一个根本性的问题：一旦样式被应用到控件上，就没有办法移除它。因此，如果你想为特定的控件实例或用户界面（UI）部分更改
阅读更多2024-11-18
Linux 下网络套接字(Socket) 与udp和tcp 相关接口
Linux下套接字的介绍与使用
阅读更多2024-11-18
react 中 useReducer Hook 作用
useState`是最基本的状态管理钩子。`useReducer`提供了一种更可预测的状态管理方式。
阅读更多2024-11-18
【自学笔记】推荐系统
（Retrieval）步骤的目的是从庞大的候选集合中快速筛选出一小部分最有可能满足用户需求的项目。这样做可以简化梯度计算，更显著的变化是，如果人没有为任何样本打分，那代入TA的初始参数。我们需要做的是
阅读更多2024-11-18
【jvm】方法区是否存在GC
6.在Hotspot虚拟机中，方法区对应的是持久代（PermGen space，在JDK 8及之后被元空间Metaspace取代），尽管持久代上的GC较少，但并不代表完全没有。2.在JVM（Java虚
阅读更多2024-11-18
2411rust,异步函数
2411rust,异步函数
阅读更多2024-11-18
用 Python 从零开始创建神经网络（八）：梯度、偏导数和链式法则
在我们继续编写我们的神经网络代码之前，最后两个需要解决的难题是梯度和偏导数的相关概念。我们到目前为止解决的导数案例都是函数中只有一个独立变量的情况——也就是说，结果完全依赖于xx（在我们的案例中）。然
阅读更多2024-11-18
深度学习之One Stage目标检测算法2
YOLO（You Only Look Once: Unified, Real-Time Object Detection）是one-stage detection的开山之作。之前的物体检测方法首先需要
阅读更多2024-11-18
TCP协议的代理IP是什么？
对于需要大量数据传输和高效通信的场景，代理IP技术提供了至关重要的支持。TCP协议作为互联网通信中最基础和最常用的协议之一，与代理IP技术的结合成为了许多企业和开发者进行网络操作时不可或缺的一部分。那
阅读更多2024-11-18