数据结构之单链表基本操作

2024-01-08 13:22:11

🤷?♀?🤷?♀?🤷?♀??今天给大家分享的是单链表的基本操作。

清风的个人主页

🎉欢迎👍点赞?评论??收藏

😛😛😛希望我的文章能对你有所帮助,有不足的地方还请各位看官多多指教,大家一起学习交流!

动动你们发财的小手,点点关注点点赞!在此谢过啦!哈哈哈!😛😛😛

目录

?一、接口定义

二、类定义

三、方法实现

3.1创建单链表(初始化创建)

3.2头插法插入节点

3.3尾插法插入节点

3.4指定位置插入节点

3.5判断节点是否包含在链表中

3.6删除值为key的节点

?3.7删除所有值为key的节点

3.8得到链表长度

3.9清空链表

3.10显示链表(打印)


源码链接:>清风的Gitee主页

?一、接口定义

还是和之前的顺序表一样,定义一个接口。后续通过链表类去实现这个定义的接口。

interface SingleLinkedList {
    //头插法
    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();
}

二、类定义

定义一个链表类,它是由各个节点构成的,因此还需要在链表类内定义一个关于节点的内部类。代码如下:
?

public class MyLinkedList implements SingleLinkedList {

    class LinkNode {
        public int val;
        public LinkNode next;

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

    public LinkNode head;
}

三、方法实现

3.1创建单链表(初始化创建)

每次通过LinkNode类定义的节点去new一个新的节点并通过构造函数设置初始值,节点定义完成后,通过各个节点的next域把各个节点之间联系起来,便成功创建了一个单链表。

    public void creatLinkedList() {
        LinkNode node1 = new LinkNode(12);
        LinkNode node2 = new LinkNode(23);
        LinkNode node3 = new LinkNode(34);
        LinkNode node4 = new LinkNode(45);
        LinkNode node5 = new LinkNode(56);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;

    }

3.2头插法插入节点

    //头插法
    public void addFirst(int data) {
        LinkNode newnode = new LinkNode(data);
        if (this.head == null) {
            this.head = newnode;
        } else {
            newnode.next = this.head;
            this.head = newnode;
        }
    }

3.3尾插法插入节点

尾插法插入节点时,首先要找到单链表的最后一个节点,再去插入。?

  • 注意,找到单链表的最后一个节点,在while循环里面的控制条件是:cur.next!=null,而不是cur!=null,这一点要切记!!!在我们刷题的时候,很多情况下都要去遍历找节点,因此一定要注意。(cur是一个引用,从head开始遍历)
  • 下图是while(cur.next!=null),循环条件结束的时候,cur所指向的位置:>

  • 下图是while(cur!=null),循环条件结束的时候,cur所指向的位置:>?

    public void addLast(int data) {
        LinkNode newnode = new LinkNode(data);
        if (this.head == null) {
            this.head = newnode;
            return;
        }
        LinkNode cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newnode;

    }

3.4指定位置插入节点

在指定位置插入,首先要判断插入位置是否合法。其次,若是在头节点插入,调用头插法即可,若是在尾节点插入,调用尾插法即可。然后,就需要找到指定的位置,此时应该找的是指定位置的前驱节点,通过指定位置的前驱节点的next域指向要插入的节点即可。当然在执行这一步骤之前,我们还需要先把前驱节点的next域所指向的节点交给要插入的节点的next域。

    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            System.out.println("插入位置不合法:>" + index);
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        LinkNode cur = this.head;
        LinkNode newnode = new LinkNode(data);
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }
        newnode.next = cur.next;
        cur.next = newnode;
    }

3.5判断节点是否包含在链表中

只需遍历链表,比较节点的值是否和要判断节点的值相等即可。

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

3.6删除值为key的节点

要先找到值为key的节点的前驱节点:

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

以下图为例,假设删除34:>

    public void remove(int key) {
        if (this.head == null) {
            System.out.println("链表为空,无法删除!!!");
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
/*        while(cur.next!=null){
            //找到要删除节点的前驱
            if(cur.next.val==key){
                LinkNode del=cur.next;
                cur.next=del.next;
                return;

            }else {
                cur=cur.next;
            }
        }*/
        LinkNode prev = findPrev(key);
        if (prev == null) {
            System.out.println("无要删除的数字:>" + key);
            return;
        }
        LinkNode del = prev.next;
        prev.next=del.next;
    }

?3.7删除所有值为key的节点

方法是通过双指针来解决:>

假设删除值为23的所有节点。

cur往前走,发现值为23的节点,进行删除操作:>

删除之后,prev指向了23的下一个节点。

删除完成后,prev不动,cur继续往后遍历:>

当cur这个引用所指向的节点的值不是23是,prev也要继续往前挪:>

如此进行下去,即可删除所有值为23的节点。

下面是实现代码:>?

    public void removeAllKey(int key) {
        if (this.head == null) {
            System.out.println("链表为空!");
            return;
        }
        LinkNode prev = head;
        LinkNode cur = head.next;
        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;
        }
    }

3.8得到链表长度

很简单,只需通过一个引用遍历即可。如果引用所指的对象不是空,那么计数器+1。

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

3.9清空链表

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

3.10显示链表(打印)

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

🎉好啦,今天的分享就到这里!!

?创作不易,还希望各位大佬支持一下!

👍点赞,你的认可是我创作的动力!

?收藏,你的青睐是我努力的方向!

??评论:你的意见是我进步的财富!

文章来源:https://blog.csdn.net/m0_73920844/article/details/134306526
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。