当前位置：首页 > article >正文

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

article 2024/11/9 6:17:55

一、 🍰 简单了解链表

二、 🍰 单向链表的模拟实现

一、🧆接口IList

二、🧆MySinngleList方法

0.🥧其他

1.🥧增加

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

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

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

2.🥧查找

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

编辑

3.🥧删除

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

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

3.🧇clear：清空链表

一、 🍰 简单了解链表

什么是链表？

链表是一种常见的数据结构。他是由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。

他有多种链表结构，如双向链表，单向链表结构等，这次我们要实现的就是单向链表结构。

链表有很多种，他们也有着许多共同的方法，所以我们可以把这些方法放到接口中

二、 🍰 单向链表的模拟实现

一、🧆接口IList

接口中的方法：

插入
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();
    }

结果：