【Java数据结构】实现单链表

╰+攻爆jí腚メ 2024-04-03 09:09 83阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：渴望力量的土狗
> 
> 博客主页：[渴望力量的土狗的博客主页][Link 1]
> 
> 专栏：[数据结构与算法][Link 2]
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 3]

![b5eef3d53dd74ac399636343463fbf2c.png][]

MySingleLinkedList.java

public class MySingleLinkedList {
    
        static class ListNode {
            public int value;
            public ListNode next;
    
            public ListNode(int value) {
                this.value = value;
            }
        }
    
    
        public ListNode head;
    
        //头插法
        public void addFirst(int data) {
            ListNode node = new ListNode(data);
            node.next = head;
            head = node;
        }
    
        //尾插法
        public void addLast(int data) {
            ListNode node = new ListNode(data);
            //1.链表为空
            if(this.head == null) {
                this.head = node;
            } else {
                //2.链表不为空
                ListNode cur = this.head;
                while(cur.next != null) {
                    cur = cur.next;
                }
                cur.next = node;
            }
        }
    
        public void addIndex(int index,int data) throws MySingleListIndexOutOfException{
            //1.先检查插入位置是否合法
            checkAddIndex(index);
            //2.分两种情况：1.头插 2.中间位置和尾插
            ListNode node = new ListNode(data);
            if(this.head == null) {
                this.head = node;
                return;
            }
            if(index == 0) {
                addFirst(data);
                return;
            }
            ListNode cur = findAddIndexSubOne(index);
            node.next = cur.next;
            cur.next = node;
        }
        private void checkAddIndex(int index) {
            if(index < 0 || index > this.size()) {
                throw new MySingleListIndexOutOfException("任意位置插入时，index不合法！");
            }
        }
        //找到待插入位置的前一个结点
        private ListNode findAddIndexSubOne(int index) {
            ListNode cur = this.head;
            while(index - 1 != 0) {
                cur = cur.next;
                index--;
            }
            return cur;
        }
    
        public boolean contains(int key) {
            if(this.head == null) {
                System.out.println("链表为空！");
                return false;
            }
            ListNode cur = this.head;
            while(cur != null) {
                if(cur.value == key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
    
        //删除第一次出现关键字为key的节点
        public void remove(int key) {
            //1.判断有无结点
            if(this.head == null) {
                System.out.println("链表为空，不能删除！");
                return;
            }
    
            //2.删第一个
            if(this.head.value == key) {
                this.head = this.head.next;
                return;
            }
            //3.删后面的
            ListNode cur = this.head;
            cur = removeSubOne(key,cur);
            if(cur == null) {
                System.out.println("链表中没有这个元素！");
                return;
            }
            cur.next = cur.next.next;
        }
        private ListNode removeSubOne(int key, ListNode cur) {
            while(cur.next != null) {
                if(cur.next.value == key) {
                    return cur;
                }
                cur = cur.next;
            }
            return null;
        }
    
        public void removeAllKey(int key) {
            //1.判断有无结点
            if (this.head == null) {
                System.out.println("链表为空，不能删除！");
                return;
            }
    
            //处理中间和尾巴
            ListNode cur = this.head;
            while (cur != null) {
                //removeSubOne函数在上一个删除方法里头
                cur = removeSubOne(key, cur);
                if (cur != null) {
                    cur.next = cur.next.next;
                }
            }
    
            //处理头
            if (this.head.value == key) {
                this.head = this.head.next;
            }
        }
    
        //得到单链表的长度
        public int size() {
            ListNode cur = this.head;
            int count = 0;
            while(cur != null) {
                count++;
                cur = cur.next;
            }
            return count;
        }
        public void display() {
            ListNode cur = this.head;
            while(cur != null) {
                System.out.print(cur.value+" ");
                cur = cur.next;
            }
            System.out.println();
        }
        public void clear() {
            this.head = null;
        }
    
    }

MySingleListIndexOutOfException.java

public class MySingleListIndexOutOfException extends RuntimeException{
        public MySingleListIndexOutOfException() {
        }
    
        public MySingleListIndexOutOfException(String message) {
            super(message);
        }
    }

Test.java

public class Test {
        public static void main(String[] args) {
            MySingleLinkedList mySingleLinkedList=new MySingleLinkedList();
            mySingleLinkedList.addFirst(1);
            mySingleLinkedList.addFirst(2);
            mySingleLinkedList.addFirst(3);
            mySingleLinkedList.display();
            System.out.println("=============================");
            mySingleLinkedList.addLast(9);
            mySingleLinkedList.addLast(10);
            mySingleLinkedList.addLast(10);
            mySingleLinkedList.display();
            System.out.println("================================");
            System.out.println(mySingleLinkedList.size());
            System.out.println("==================================");
            mySingleLinkedList.addIndex(0,999);
            mySingleLinkedList.addIndex(2,888);
            mySingleLinkedList.addIndex(7,10001);
            mySingleLinkedList.display();
            System.out.println("=================================");
            mySingleLinkedList.remove(2);
            mySingleLinkedList.display();;
            mySingleLinkedList.removeAllKey(10);
            mySingleLinkedList.display();
            System.out.println("===================================");
            System.out.println(mySingleLinkedList.contains(888));
    
        }
    }

测试结果：

![6c59f43fb02d4b509cfd7ccf91d09404.png][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/e6d790a30d03467d9c7de2e3d5d27b41.gif
[Link 1]: https://blog.csdn.net/m0_67995737?type=blog
[Link 2]: https://blog.csdn.net/m0_67995737/category_12000344.html
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_ylcxx_c
[b5eef3d53dd74ac399636343463fbf2c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/eb861b33dedd4f42b608cf10bc61ea1b.png
[6c59f43fb02d4b509cfd7ccf91d09404.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/bbea94690f1944aa9cd03e584d628a1e.png