文章目录

前言
链表的设计
单链表复杂度分析
总结-推荐一个神奇的网站

前言

动态数组有一个很明显的缺点，就是可能会造成内存空间的大量浪费。

那么能否做到用到多少内存就申请多少内存呢？

那么链表就可以办到这一点。

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的。

一、链表的设计

1.打印

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

2.获取长度

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

3.查找元素

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

4.头插

  public void addFirst(int data){
        NodeList node = new NodeList(data);
        node.next = this.head;
        this.head = node;
    }

5.尾插

    public void addLast(int data){
        NodeList node = new NodeList(data);
        if(this.head == null){
            this.head = node;
        }else {
            NodeList cur = this.head;
            while (cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }

6.插入元素

    //找到要插入位置的前一个节点
    public NodeList Findindex(int index){
        NodeList cur = this.head;
        while (index-1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }
    //插入元素
    public void addIndex(int index,int data){
        NodeList node = new NodeList(data);
        if(index<0 || index>size()){
            System.out.println("index位置不合法！");
            return;
        }
        if(index == 0){
            addFirst(data);
            return;
        }
        if(index == size()){
            addLast(data);
            return;
        }
        NodeList cur = Findindex(index);
        node.next = cur.next;
        cur.next = node;
    }

7.删除第一次出现该元素的节点

    //寻找删除节点的前驱
    public NodeList searchPre(int key){
        NodeList cur = this.head;
        while (cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除第一次出现key的节点
    public void delKey(int key){
        if(this.head == null){
            System.out.println("单链表为空");
            return;
        }
        if(this.head.val == key){
            this.head = this.head.next;
            return;
        }
        NodeList cur = searchPre(key);
        if(cur == null){
            System.out.println("没有删除的节点！");
            return;
        }
        NodeList del = cur.next;
        cur.next = del.next;
    }

8.删除所有出现该元素的节点

    //删除所有出现key的节点
    public NodeList delAllkey(int key){
        if(this.head == null){
            return null;
        }
        NodeList pre = this.head;
        NodeList cur = this.head.next;
        while (cur != null){
            if(cur.val == key){
                pre.next = cur.next;
                cur = cur.next;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        if(this.head.val == key){
            this.head = this.head.next;
        }
        return this.head;
    }

9.清空

    public void clear(){
        //this.head = null;
        while (this.head != null){
            NodeList curNest = this.head.next;
            this.head.next = null;
            this.head = curNest;
        }
    }