[数据结构与算法]数据结构(线性表之单链表)

🥇为何要使用链表

博主在上一篇博客中详细介绍了线性表的顺序结构，也就是顺序表的各种功能，例如增删除改等，详细请看上一篇博客顺序表
在这里先让博主为大家回顾一下上一章的顺序表的存储结构

• 逻辑上：具有连续性
• 物理上：具有连续性
• 当数据的存储空间不够的时候，会开辟一段与原空间等长的空间来存储数据
• 顺序表的优点：
• 1.无须为表示表中元素逻辑关系而增添额外的存储空间
• 2.可以快速的存取表中的任意位置的元素。
• 顺序表的缺点：
• 1.插入和删除操作需要移动大量的数据，耗费时间
• 2.当线性表长度变化较大时，难以确定空间容量，比如说，线性表的原存1储空间为100个单位，现在要存储101个数据，先让空间不够用，就在开辟一倍等长的数据空间，储存空间变为200，那么未被利用的有99个空间，就会造成储存空间碎片。
  今天博主介绍的是单链表，相比顺序表，它在插入和删除方面，具有很大的优势。

🥇 单链表是什么

反观顺序表要存储数据，每次的都要一次性开辟非常大的空间，存储数据，怎样解决这个问题呢？

链表做出了以下回应，要利用数据时，需要一个数据，开辟一个空间。那有些童鞋就会问为什么不在顺序表中这样做呢？解答：如果利用一个数据，开辟一个空间，就会造成逻辑上的不连续，就不能成为线性表。

• 我们可以在第一个元素时，就知道第二个元素的位置(内存地址),而找到第二个元素的时候，就知道第三个元素的地址，这样所有的元素我们就可以通过遍历来找到
  
  可能在上述的链表图中，大家有点迷糊，那下来就看看博主的介绍：
  在链表中，有数据域和指针域两个概念
• 数据域：存放将要进行被操作的数据
• 指针域：存放下一个元素的地址
• 一个数据域和一个指针域合起来成为一个链表的节点(node)，在读取到一个节点时，我们会知道这个节点所对应的数据，同时也会知道下一个节点的地址

单链表的数据存储方式

特点：用一组任意的存储单元，存储顺序表的元素，这组存储元素可以是连续的，也可以是不连续的，这就意味着这些元素可以存在内存中未被占用的任意位置
链表的存储结构：

🥇单链表之创建链表

说到实现这个链表，这也相当于一个小项目吧，那我们就创建一个测试文件 TestDemo.java 来测试创建链表的功能，实现一个MyLinkedList.java文件，来实现链表的各个功能

• 在MyLinkedList.java文件中，先创建一个节点类class Node，里面包括一个节点的数据元素，和下一个节点的地址。
• ??代码：

 class Node {
    public int val;
    public Node next;//节点中的next地址，默认为空
    public Node(int val) {
        this.val = val; //为节点中的数据进行初始化
    }

然后随机利用一些数据进行对链表的定义，并且把每一个节点都连接起来，实现创建一个单链表方法
??代码：

  public void createList() {
        Node node1 = new Node(12);
        Node node2 = new Node(3);
        Node node3 = new Node(5);
        Node node4 = new Node(2);
        node1.next = node2;
        //连接每一个节点
        node2.next = node3;
        node3.next = node4;
        this.head = node1; //定义一个头节点，指向第一个节点
    }

在TestDemo.java文件中，创建一个对象，引用MyLinkedList.java文件中的功能方法。

🥇单链表之打印链表

遍历整个链表，直到链表结束，在MyLinkedList.java文件实现print方法
📄算法思想：

1. 如果链表为空链表，即this.head == null ,那么链表为空，就直接返回
2. 创建一个跟随节点，cur ，指向头结点，每遍历一个节点，cur = cur.next，就指向下一个节点
3. 链表跟随节点的结束标志为：cur != null ,如果是cur.next != null 只能遍历到倒数第二个节点，因为当倒数第一格节点为null时，就不会进入循环打印元素。
   
   ??代码：

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

打印新创建的单链表
在TestDemo.java文件中调用print方法

🥇单链表之计算链表长度

在MyLinkedList.java文件实现size方法
算法思想：
1. 创建跟随节点，遍历整个链表
2. 创建一个计数器，每遍历一个节点，count就加1，统计count
3. 当链表为空时，即this,head == null 时，返回0，证明链表长度为0

??代码：

     //得到单链表的长度
    public int size() {
        if(this.head == null){
            System.out.println("头结点为空");
            return -1;
        }
        Node cur = this.head;
        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

🥇单链表之增删查改

单链表之头插法

在MyLinkedList.java文件中实现addFirst()函数功能
📄算法思想：

1. 判断这个单链表是否为空，即this.head == null,如果等于的话，那么新插入的节点就是头节点，即 this.head = node(要插入节点的地址)
2.在链表的头部插入节点，也就是让链表的头结点的地址赋给新插入节点的next，即node.next = this.head,然后让新链表的头结点等于新插入的节点node的地址，即this.head = node.

看图说话

??代码：

     //头插法
    public void addFirst(int data) {
        Node node = new Node(data);
        //如果链表本身为空
        if(this.head == null){
            this.head = node;
        }else{
            node.next = this.head;
            this.head = node;
        }
    }

单链表之尾插法

在MyLinkedList.java文件中实现addLast()函数功能
📄算法思想：

1. 判断这个单链表是否为空，即this.head == null,如果等于的话，那么新插入的节点就是头节点，即 this.head = node(要插入节点的地址)
2.新建一个跟随节点cur，遍历链表
2.找到链表中的尾节点，并返回此节点
3.让cur.next = node,这样就把插入的节点，放到了链表尾部
看图说话：

??代码：

 //尾插法
    public void addLast(int data) {
     Node node = new Node(data);
     //如果链表头结点为空，就等于说链表本身为空
     if(this.head == null){
         this.head = node;
         return;
     }
     Node cur = this.head;
     //找到链表最后一个节点，让最后一个节点，的next等于所在尾插点的地址
     while(cur.next != null){
         cur = cur.next;
     }
     cur.next = node;
    }

单链表之把一个节点插到链表中的任意位置

在MyLinkedList.java文件中实现addIndex(int Index,int data)函数功能

📄算法思想：
1. 判断这个单链表是否为空，即this.head == null,如果等于的话，那么新插入的节点就是头节点，即 this.head = node(要插入节点的地址)
2.判断下标Index的合法性，如果Index等于0,那么就调用addFirst方法，如果Index等于size()-调用size方法,那么就调用addLast方法，如果Index < 0 或者 Index > size(),那么就打印下标不合法，直接return 退出。
3.如果Index合法，且要出入节点，不在链表首尾，那么就要找到所插节点的前驱节点，并返回此节点，让node.next = cur.next,然后让cur.next = node，就可以连接所插节点。

看图说话：

??代码：

 //找到插入节点的前一个位置
    public Node find_cur(int index){
        Node cur = this.head;
        int count = 0;
        while(count!=index-1){
            count++;
            cur = cur.next;
        }
        return cur;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
    //判断indxx的合法性
        if(index < 0 || index >size()){
            System.out.println("下标不合法");
        }
        //插入头结点
        if(index == 0){
            addFirst(data);
            return;
        }
        //插入尾节点
        if(index == size()){
            addLast(data);
            return;
        }
        //插入其他节点
        Node node = new Node(data);
        Node cur = find_cur(index);
        node.next = cur.next;
        cur.next = node;

    }

单链表之查找链表中是否某个元素

在MyLinkedList.java文件中实现contans(int data)函数功能
📄算法思想：

1. 创建一个跟随节点，cur 初始化为cur = this.head
2. 如果链表为空，即this,head == null ,就返回false退出
3. 如果在链表中找不到要找的元素，也返回false并退出
4. 遍历链表，直到cur == null,每次循环cur = cur.next 寻找对应的元素cur.next == value，找到返回true，找不到返回false.

看图说话：

单链表之删除的一次出现value值的节点

在MyLinkedList.java文件中实现remove(int data)函数功能
📄算法思想：
1. 判断链表是否为空，如果为空，就没有必要删除
2. 如果不为空，就遍历该链表，找到要删除的值的节点，返回它的前驱节点
3.这个前驱节点的next 等于下下一个节点的地址，即cur.next = cur.next.next 这样就巧妙的跳过了要删除的节点

看图说话：

??代码：

     public Node seaarchPrevNode(int value){
        Node cur = this.head;
        while(cur!=null){
            if(cur.next.val == value){
                return cur;
            }else{
                cur = cur.next;
            }
        }
        return null;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int value) {
        //如果链表为空，头结点为空
        if(this.head == null){
            System.out.println("链表为空，没有删除的节点");
        }
        //如果头结点为要删除的节点
        if(this.head.val == value){
            this.head = this.head.next;
        }
     //先找到这个要删除的节点
        Node cur = seaarchPrevNode(value);  //前驱节点
//        Node del = cur.next;
//        cur.next = del.next;
        cur.next = cur.next.next;
    }

单链表之删除链表中出现value值的所有节点

在MyLinkedList.java文件中实现removeAllkey(int data)函数功能
📄算法思想：

1. 设置头结点head,前驱节点prev = this.head,跟随节点 cur = this.head.next
2. 遍历链表，依靠cur节点，遍历除头结点，以外的节点，如果某个节点的value值等于所要删除的value值，即cur.value == value，就让前驱节点prev.next = cur.next,跳过cur节点，然后cur = cur.next 再向后遍历，当cur.value不等于value时，让前驱节点prev等于cur,最后如果头结点等于前驱节点，那么删除头结点，this.head = this.head.next

看图说话：

??代码

    //删除所有值为key的节点
    public void removeAllKey(int value) {
    Node prev = this.head;
    Node cur = this.head.next;
    //判断前面是否为要删除节点
        while(cur!=null){
            if(cur.val == value){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        //如果头结点为可删节点
        if(this.head.val == value){
            this.head = this.head.next;
        }
    }

单链表之清空链表

在MyLinkedList.java文件中实现clear(int data)函数功能
📄算法思想：

1. 建立一个节点保存head.next curNext = head.next
2. 将head.next 置为 null
3. 利用head = curNext循环
4. 直到遍历到做后一个节点为为止。
看图说话

??代码

     //清空单链表
    public void clear(){
        while(head != null){
            Node curNext = this.head.next;
            this.head.next = null;
            this.head = curNext;
        }
    }

总汇：

💯TestDemo.java文件：

 public class TestDemo {
    public static void main(String[] args) {
        MyLinkList myLinkList = new MyLinkList();
        myLinkList.createList();  //创建链表
        myLinkList.addIndex(0,5);
        System.out.print("原链表");
        myLinkList.print();
        myLinkList.clear();
        System.out.print("新链表");
        myLinkList.print();

    }
}

💯MyLinkedList.java文件

 class Node {
    public int val;
    public Node next;//null
    public Node(int val) {
        this.val = val;
    }
}
//链表
public class MyLinkList {
    public Node head;//标识单链表的头节点
    /**
     * 穷举的方式 创建链表  当然很low。此处只是为了好理解
     */
    public void createList() {
        Node node1 = new Node(12);
        Node node2 = new Node(3);
        Node node3 = new Node(5);
        Node node4 = new Node(2);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        this.head = node1;
    }

    /**
     * 打印单链表
     */
    public void print() {
        Node cur = this.head;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //得到单链表的长度
    public int size() {
        if(this.head == null){
            System.out.println("头结点为空");
            return -1;
        }
        Node cur = this.head;
        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int value) {
        if(this.head == null){
            System.out.println("链表为空");
            return false;
        }
        Node cur = this.head;
        while(cur!=null){
            if(cur.val == value){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //头插法
    public void addFirst(int data) {
        Node node = new Node(data);
        //如果链表本身为空
        if(this.head == null){
            this.head = node;
        }else{
            node.next = this.head;
            this.head = node;
        }
    }
    //尾插法
    public void addLast(int data) {
     Node node = new Node(data);
     //如果链表头结点为空，就等于说链表本身为空
     if(this.head == null){
         this.head = node;
         return;
     }
     Node cur = this.head;
     //找到链表最后一个节点，让最后一个节点，的next等于所在尾插点的地址
     while(cur.next != null){
         cur = cur.next;
     }
     cur.next = node;
    }
    //找到插入节点的前一个位置
    public Node find_cur(int index){
        Node cur = this.head;
        int count = 0;
        while(count!=index-1){
            count++;
            cur = cur.next;
        }
        return cur;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
    //判断indxx的合法性
        if(index < 0 || index >size()){
            System.out.println("下标不合法");
        }
        //插入头结点
        if(index == 0){
            addFirst(data);
            return;
        }
        //插入尾节点
        if(index == size()){
            addLast(data);
            return;
        }
        //插入其他节点
        Node node = new Node(data);
        Node cur = find_cur(index);
        node.next = cur.next;
        cur.next = node;

    }
    public Node seaarchPrevNode(int value){
        Node cur = this.head;
        while(cur!=null){
            if(cur.next.val == value){
                return cur;
            }else{
                cur = cur.next;
            }
        }
        return null;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int value) {
        //如果链表为空，头结点为空
        if(this.head == null){
            System.out.println("链表为空，没有删除的节点");
        }
        //如果头结点为要删除的节点
        if(this.head.val == value){
            this.head = this.head.next;
        }
     //先找到这个要删除的节点
        Node cur = seaarchPrevNode(value);  //前驱节点
//        Node del = cur.next;
//        cur.next = del.next;
        cur.next = cur.next.next;
    }

    //删除所有值为key的节点
    public void removeAllKey(int value) {
    Node prev = this.head;
    Node cur = this.head.next;
    //判断前面是否为要删除节点
        while(cur!=null){
            if(cur.val == value){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        //如果头结点为可删节点
        if(this.head.val == value){
            this.head = this.head.next;
        }
    }
    //清空单链表
    public void clear(){
        while(head != null){
            Node curNext = this.head.next;
            this.head.next = null;
            this.head = curNext;
        }
    }
}