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

✨hello，进来的小伙伴们，你们好耶！✨

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

🍬🍬本篇内容：LinkedList的模拟实现！

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

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

点击链接注册，开启刷题之路！

目录

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;
        }
    }

头插打印结果：

** 尾插打印结果：**

3、获取链表长度

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

运行结果：

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);

运行结果：

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)

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）

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）

10、置空

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

运行结果：