0


【数据结构与算法】LinkedList的模拟实现

✨hello,进来的小伙伴们,你们好耶!✨

🍔🍔系列专栏:【数据结构与算法】

🍬🍬本篇内容:LinkedList的模拟实现!

🍯🍯作者简介:一名双非本科大三在读的Java编程小白,星夜漫长,你我同行!

🍩🍩给大家推荐一个超级好用的刷题网站——牛客网!

点击链接注册,开启刷题之路!

bb68eb86ce134f2296916fad8ce3d837.png

目录


LinkedList底层就是一个双向链表,我们来实现一个双向链表。

1、首先定义一个静态内部类

    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode tail;

2、打印双向链表

    public void display(){//打印双向链表
        ListNode cur = this.head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }

头插打印结果:

3e7c984ad6eb46a09fe3da63859b6f99.png

** 尾插打印结果:**

dc7d0e753dab4c0e90ed49a0e2e87328.png

3、获取链表长度

    public int size(){//获取链表长度
        ListNode cur = this.head;
        int count = 0;
        while (cur!=null){
            count++;
            cur = cur.next;
        }
        return count;
    }

运行结果:

61189632589141688d2ea2a0e0bf82c8.png

4、判断关键字key是否在链表中

    public boolean contains(int key){//判断关键字key是否在该链表中
        ListNode cur = this.head;
        while (cur!=null){
        if(cur.val == key){
            return true;
            }
        }
        return false;
    }

主函数代码:

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.addLast(56);
        boolean b1 = myLinkedList.contains(12);
        System.out.println(b1);

运行结果:

558e40fa1d304613adf03f5e8aabbcac.png

5、头插法

    public void addFirst(int data){//头插法
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }else{
            node.next = this.head;
            this.head.prev = node;
            head = node;
        }
    }

6、尾插法

   public void addLast(int data){//尾插法
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }else{
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }

7、任意位置插入

  //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        //1、判断Index位置的合法性
        //2、判断特殊位置,头插 和 尾插
        //3、找到index位置节点的地址
        if(index<0 || index >size()){
            return;
        }
        if(index == 0){
            addFirst(data);
        }
        if(index == size()){
            addLast(data);
        }
        ListNode cur = findIndexListNode( index);
        ListNode node  = new ListNode(data);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

    private ListNode findIndexListNode(int index) {
        ListNode cur = head;
        while ((index != 0)) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

运行结果:(这里我们假如在2位置插入元素888)

f52ed7ab591644cdb37b1bba5642318f.png

8、删除第一次出现值为key的节点

 public void remove(int key){//删除第一次出现关键字为key的节点
        ListNode cur = head;
        while (cur!=null){
            if(cur.val == key){
                if(cur==head) {
                    head = head.next;
                    if(head!=null){//表示只有一个节点的情况下
                        head.prev = null;
                    }else{
                        tail = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    if(cur.next!=null){
                        cur.next.prev = cur.prev;
                    }else{
                        this.tail = cur.prev;
                    }
                }
               return;
            }
            cur = cur.next;
        }
    }

运行结果:(假如我们头插四个元素值都为12还有一个元素值为56)

ed55a4c44edf44098cefab17c6319f34.png

9、删除所有值为key的节点

  public void removeAllkey(int key){//删除所有值为key的节点
        ListNode cur = head;
        while (cur!=null){
            if(cur.val == key){
                if(cur==head) {
                    head = head.next;
                    if(head!=null){//表示只有一个节点的情况下
                        head.prev = null;
                    }else{
                        tail = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    if(cur.next!=null){
                        cur.next.prev = cur.prev;
                    }else{
                        this.tail = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

运行结果:(假如我们头插的元素有五个其中四个都为10 另一个为20)

0772488b519840e0b7d35661055a3165.png

10、置空

    public void clear(){//一个一个置空
        ListNode cur = head;
        ListNode curNext = cur.next;
        while(cur!=null){
            head.next = null;
            head.prev = null;
            cur = curNext;
        }
    }

运行结果:

8c0da36f33bd42049bb7df94c3b5d5d9.png


本文转载自: https://blog.csdn.net/m0_62426532/article/details/126995536
版权归原作者 令辰柒 所有, 如有侵权,请联系我们删除。

“【数据结构与算法】LinkedList的模拟实现”的评论:

还没有评论