devbox
在线问答5
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

从零实现单链表（增删查改）_listnode* list1

作者：在线问答5 | 2024-07-28 07:42:17

赞

踩

listnode* list1

本篇博客只是简单实现单链表（不带头节点），此类链表头节点会改变，面试遇到的会比较多。此外，只是简单的实现单链表，和原码有很大差距，目的是为了通过简单的实现单链表，对链表的各种操作更加熟悉。以便以后刷链表的题更加的得心应手。

目录

全部代码

MySIngleList

增删查改详解

遍历打印单链表

链表节点个数

头插法：

尾插法：

在指定位置插入节点

查看链表是否包含某个元素

 删除第一次出现关键字为key的节点

 删除所有值为key的节点

清空链表

全部代码

MySIngleList

  1. public class MySingleList {
  2.     //写一个内部类ListNode，表示单链表的节点
  3.     static class ListNode{
  4.         public int vale;//节点里面的值域
  5.         public ListNode next;//节点里面放下一个节点的地址域
  6.         //写一个构造方法
  7.         public ListNode(int vale) {
  8.             this.vale = vale;
  9.         }
  10.     }
  11.     public ListNode head;//头节点
  12.  
  13.     //这里用比较low的方法先创建一个链表，以便学习。
  14.     // 下面会写add方法，到时候可以拿add方法创建一个链表
  15.     public void creatList(){
  16.         ListNode list1 = new ListNode(20);
  17.         ListNode list2 = new ListNode(22);
  18.         ListNode list3 = new ListNode(10);
  19.         ListNode list4 = new ListNode(01);
  20.         list1.next = list2;
  21.         list2.next = list3;
  22.         list3.next = list4;
  23.         this.head = list1;
  24.     }
  25.     //遍历打印单链表
  26.     public void display(){
  27.         ListNode cur = this.head;
  28.         while(cur != null){
  29.             System.out.print(cur.vale+" ");
  30.             cur = cur.next;
  31.         }
  32.         System.out.println();
  33.     }
  34.     //链表节点个数
  35.    public int size(){
  36.         int count = 0;
  37.        ListNode cur = this.head;
  38.        while(cur != null){
  39.            count++;
  40.            cur = cur.next;
  41.        }
  42.        return count;
  43.    }
  44.     //头插法
  45.    public void addFirst(int data){
  46.         ListNode node = new ListNode(data);
  47.         node.next = this.head;
  48.         head = node;
  49.     }
  50. // 尾插法
  51.    public void addLast(int data){
  52.         ListNode node = new ListNode(data);
  53.         if(head == null){
  54.             head = node;
  55.         }else{
  56.             ListNode cur = this.head;
  57.             while (cur.next != null){
  58.                 cur = cur.next;
  59.             }
  60.             cur.next = node;
  61.         }
  62.    }
  63.    //任意位置插入,第一个数据节点为0号下标
  64.   public void addIndex(int index,int data){
  65.         if(index<0 || index > this.size()){
  66.             throw new PosWrongFulException("index位置不合法");
  67.         }
  68.         if(index == 0){
  69.             addFirst(data);
  70.             return;
  71.         }
  72.         if(index == this.size()){
  73.             addLast(data);
  74.             return;
  75.         }
  76.         ListNode cur = findIndexSubOne(index);
  77.         ListNode node = new ListNode(data);
  78.         node.next = cur.next;
  79.         cur.next = node;
  80.   }
  81.   private ListNode findIndexSubOne(int index){
  82.         ListNode cur = this.head;
  83.         while (index-1 != 0){
  84.             cur = cur.next;
  85.             index--;
  86.         }
  87.         return cur;
  88.   }
  89.     //查找是否包含关键字key是否在单链表当中
  90.    public boolean conains(int key){
  91.         ListNode cur = head;
  92.         while(cur != null){
  93.             if(cur.vale == key){
  94.                 return true;
  95.             }
  96.             cur = cur.next;
  97.         }
  98.         return false;
  99.    }
  100. // 删除第一次出现关键字为key的节点
  101.    public void remove(int key){
  102.         if(head.vale == key){
  103.             head = head.next;
  104.             return;
  105.         }
  106.         ListNode cur = findPrevOfKey(key);
  107.         if(cur == null){
  108.             System.out.println("没有你要删除的值");
  109.             return;
  110.         }
  111.         cur.next = cur.next.next;
  112.    }
  113.    private ListNode findPrevOfKey(int key){
  114.         ListNode cur = head;
  115.         while(cur.next != null){
  116.             if(cur.next.vale == key){
  117.                 return cur;
  118.             }
  119.             cur = cur.next;
  120.         }
  121.         return null;
  122.    }
  123. // 删除所有值为key的节点
  124.    public void removeAllKey(int key){
  125.         ListNode pre = head;
  126.         ListNode cur = head.next;
  127.         while (cur != null){
  128.             if(cur.vale == key){
  129.                 pre.next = cur.next;
  130.                 cur = cur.next;
  131.             }else {
  132.                 pre = cur;
  133.                 cur = cur.next;
  134.             }
  135.         }
  136.         if(head.vale == key){
  137.             head = head.next;
  138.         }
  139.    }
  140.    public void clear(){
  141.         head = null;
  142.    }
  143. }

增删查改详解

遍历打印单链表

思路：创建一个cur代替head遍历这个链表，把里面的每个元素打印出来

代码

  1. public void display(){
  2.         ListNode cur = this.head;
  3.         while(cur != null){
  4.             System.out.print(cur.vale+" ");
  5.             cur = cur.next;
  6.         }
  7.     }

这里while的终止条件是cur != null，而不是cur.next != null，是因为我们要打印每个节点里面的值。如果是cur.next!=null，最后一个节点不会被打印，且如果是空链表会空指针异常。

运行结果：

 （这里的creatList可以看上面写在一起的代码，就是用穷举的方法简单创建了一个单链表，很low,放下面辣）

  1. public void creatList(){
  2.         ListNode list1 = new ListNode(20);
  3.         ListNode list2 = new ListNode(22);
  4.         ListNode list3 = new ListNode(10);
  5.         ListNode list4 = new ListNode(01);
  6.         list1.next = list2;
  7.         list2.next = list3;
  8.         list3.next = list4;
  9.         this.head = list1;
  10.     }

链表节点个数

思路：和上面一样，创建一个count用来计数，遍历一下这个链表。

代码：

  1.    //链表节点个数
  2.    public int size(){
  3.         int count = 0;
  4.        ListNode cur = this.head;
  5.        while(cur != null){
  6.            count++;
  7.            cur = cur.next;
  8.        }
  9.        return count;
  10.    }

运行结果：

头插法：

思路

代码：

  1. //头插法
  2.    public void addFirst(int data){
  3.         ListNode node = new ListNode(data);
  4.         node.next = this.head;
  5.         head = node;
  6.     }

运行结果：

尾插法：

思路：

代码：

  1. public void addLast(int data){
  2.         ListNode node = new ListNode(data);
  3.         if(head == null){
  4.             head = node;
  5.         }else{
  6.             ListNode cur = this.head;
  7.             while (cur.next != null){
  8.                 cur = cur.next;
  9.             }
  10.             cur.next = node;
  11.         }
  12.    }

 运行结果：

在指定位置插入节点

思路：

代码

  1. public void addIndex(int index,int data){
  2.         if(index<0 || index > this.size()){
  3.             throw new PosWrongFulException("index位置不合法");
  4.         }
  5.         if(index == 0){
  6.             addFirst(data);
  7.             return;
  8.         }
  9.         if(index == this.size()){
  10.             addLast(data);
  11.             return;
  12.         }
  13.         ListNode cur = findIndexSubOne(index);
  14.         ListNode node = new ListNode(data);
  15.         node.next = cur.next;
  16.         cur.next = node;
  17.   }
  18.   private ListNode findIndexSubOne(int index){
  19.         ListNode cur = this.head;
  20.         while (index-1 != 0){
  21.             cur = cur.next;
  22.             index--;
  23.         }
  24.         return cur;
  25.   }

 PosWrongFulException

  1. public class PosWrongFulException extends RuntimeException{
  2.     public PosWrongFulException() {
  3.     }
  4.  
  5.     public PosWrongFulException(String message) {
  6.         super(message);
  7.     }
  8. }

运行结果：

查看链表是否包含某个元素

思路：遍历链表

代码：

  1. public boolean conains(int key){
  2.         ListNode cur = head;
  3.         while(cur != null){
  4.             if(cur.vale == key){
  5.                 return true;
  6.             }
  7.             cur = cur.next;
  8.         }
  9.         return false;
  10.    }

运行结果：

 删除第一次出现关键字为key的节点

思路：

 假设我们现在要删除值为22这个节点，那么需要找到值为22的前一个节点，把它的next的域改为22这个节点next域指向的节点。我们可以写一个函数来找到前一个节点pre
pre.next = pre.next.next。还要考虑如果删除的是头节点，则只需要把头节点指向头节点next域指向的节点：head = head.next；

代码

  1. // 删除第一次出现关键字为key的节点
  2.    public void remove(int key){
  3.         if(head.vale == key){
  4.             head = head.next;
  5.             return;
  6.         }
  7.         ListNode cur = findPrevOfKey(key);
  8.         if(cur == null){
  9.             System.out.println("没有你要删除的值");
  10.             return;
  11.         }
  12.         cur.next = cur.next.next;
  13.    }
  14.    private ListNode findPrevOfKey(int key){
  15.         ListNode cur = head;
  16.         while(cur.next != null){
  17.             if(cur.next.vale == key){
  18.                 return cur;
  19.             }
  20.             cur = cur.next;
  21.         }
  22.         return null;
  23.    }

运行结果：

 删除所有值为key的节点

思路：

 假设我现在要删除所有值为20的节点，我们需要2个ListNode变量，因为如果只定义一个 cur，那么如果是连续俩个都是20的节点在一起，就会漏删。原因是当我们把第一个20节点删掉后，cur必须向后走一步，如果此时cur指向的节点的值刚好还是20就删除不了了。

我们可以先判断cur的值是否等于20，如果等于:pre的next域指向cur的next域。cur继续往后走，如果不等于，pre指向cur，cur往后走。

为什么要等cur的值不等于20时再让pre指向cur,cur再往后走。是因为如果cur的值是20，cur需要删除。如果此时另pre = cur，那么pre就不是cur的前驱了。

最后我还需要判断头节点是否等于20，如果需要删除再把头节点删除。head = head.next

代码：

  1. // 删除所有值为key的节点
  2.    public void removeAllKey(int key){
  3.         ListNode pre = head;
  4.         ListNode cur = head.next;
  5.         while (cur != null){
  6.             if(cur.vale == key){
  7.                 pre.next = cur.next;
  8.                 cur = cur.next;
  9.             }else {
  10.                 pre = cur;
  11.                 cur = cur.next;
  12.             }
  13.         }
  14.         if(head.vale == key){
  15.             head = head.next;
  16.         }
  17.    }

运行结果：

清空链表

思路：当节点没有对象引用时就会被回收。此时只需要另头结点为空就好。

代码：

  1. public void clear(){
  2.         head = null;
  3.    }

运行结果

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/893297
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号