🥇为何要使用链表

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

• 逻辑上：具有连续性
• 物理上：具有连续性
• 当数据的存储空间不够的时候，会开辟一段与原空间等长的空间来存储数据
• 顺序表的优点：
• 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数据结构学习总结线性表之单链表(代码片段)
   一，回忆链表 　链表，别名链式存储结构或单链表，用于存储逻辑关系为"一对一"的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。&nbs...  查看详情  
                
线性表之单链表(代码片段)
在学完线性表之后，总结一下顺序表的优缺点优点无须为元素之间的逻辑结构增添额外的储存空间，自成一体。随机存取，十分方便。缺点空间利用率不高，容易造成“碎片”。插入删除操作需要移动大量的元素。当线性...  查看详情  
                
算法习题---线性表之单链表逆序打印(代码片段)
一：题目逆序打印单链表中的数据，假设指针指向单链表的开始结点二：思路1.可以使用递归方法，来进行数据打印2.可以借助数组空间，获取长度，逆序打印数组3.若是可以，对链表数据使用头插法，逆序排列，然后正序打印即...  查看详情  
                
数据结构线性表之实现单循环链表(代码片段)
数据结构线性表之实现单循环链表数据结构线性表之实现单循环链表相关文章单循环链表单循环链表定义数据结构线性表之实现单循环链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实...  查看详情  
                
数据结构与算法-线性表之循环链表(代码片段)
前言：前面几篇介绍了线性表的顺序和链式存储结构，其中链式存储结构为单向链表（即一个方向的有限长度、不循环的链表），对于单链表，由于每个节点只存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说...  查看详情  
                
数据结构之单链表(代码片段)
文章目录前言1.为何需要链表?2.清楚单链表结构3.定义单链表结构代码实现4.单链表的增删改查4.1单链表之尾插4.1.1单链表之开辟空间4.1.2单链表之打印值4.2单链表之头插4.3单链表之尾删4.4单链表之头删4.5单链表之查链表长度4.6单...  查看详情  
                
线性表之链表(代码片段)
单链表也是一种链式存取的线性表，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，以next指针指向下一个节点而链接起来，相比于顺序表，链表有着快速增加，删除节点的优势，其节点...  查看详情  
                
算法习题---线性表之单链表的查找(代码片段)
一：问题已知一个带头结点的单链表，结点结构为（data，link）假设该链表只给出了头指针list，在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该...  查看详情  
                
数据结构学习笔记二线性表之链表篇（双向链表）(代码片段)
链表根据带头不带头、单向或双向、循环非循环三个方面可组成成八种类型。这八种类型中仅有两种是我们常用的。第一种是单向不带头非循环链表，也就是单链表。单链表因为结构简单，但是实际操作比较复杂，所...  查看详情  
                
03线性表之链表(代码片段)
肚子饿了就要吃  ~  嗝 ———路飞 1.本章重点链表表示和实现（单链表+双链表）链表的常见OJ题顺序表和链表的区别和联系2.为什么需要链表引子：顺序表的问题及思考(1)动态顺序表特点：插入数据，...  查看详情  
                
数据结构与算法-线性表之静态链表(代码片段)
...针，那么在没有引用或指针的语言中，该怎么实现这个的数据结构呢？一、简介　　定义：用数组代替指针或引用来描述单链表，即用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法；　　上面的静态链表图有两个...  查看详情  
                
数据结构之双链表(代码片段)
文章目录前言为何要双链表?双链表的结构图示项目的建造双链表结点的定义双链表的各种方法实现双链表之新建结点双链表之初始化双链表之判空双链表之求具体元素数量双链表之打印链表内容双链表之尾插双链表之尾删双链...  查看详情  
                
线性表之单链表实现
for(循环）还是while(循环）循环之后，i和条件值相等。#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedefstructnode{	intdata;	structnode*next;}NODE,*PNODE;PNODEcreateList(PNODE);voidtravelList(PNO  查看详情  
                
数据结构之顺序表(代码片段)
...容SeqList.c文件内容前言讲完算法效率,就正式开始我们的数据结构  查看详情  
                
单链表之crud操作(代码片段)
package链表.单链表crud;publicclassSingleLinkedListDemopublicstaticvoidmain(String[]args)SingleLinkedListsll=newSingleLinkedList();HeroNodeheroNode1=newHeroNode(1,"虚空掠夺者");HeroNodeheroNode  查看详情  
                
线性表之链表(代码片段)
...一个数据元素。对于非线性的链表:可以参见相关的其他数据结构，例如树、图。另外有一种基于多个线性链表的数据结构：跳表，插入、删除和查找等基本操作的速度可以达到O(nlogn），和平衡二叉树一样。其中存储数据元素信...  查看详情  
                
数据结构学习总结线性表之顺序表(代码片段)
　　　　通过前面的学习知道，具有“一对一”逻辑关系的数据，最佳的存储方式是使用线性表。那么，什么是线性表呢？线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一...  查看详情  
                
数据结构之第二章线性表之静态链式存储
1～～特点：用一维数组来描述线性表，用游标代替指针指示节点在数组中的相对位置。不设“指针”类型的高级语言中适用链表结构。2～～线性表的静态链式存储结构 //// 静态单链表.h// 单链表的静态存储////6/...  查看详情