文章目录

• 前言
• 一、什么是单链表？
• 二、单链表相关操作（不带虚拟头节点）
• • 1.插入数据
  • 2.查询数据
  • 3.修改元素
  • 4.删除元素
• 总结

前言

在学习顺序表时，我们就了解到虽然它查询和修改元素，根据其下标索引就可以立马实现，但要删除和增加元素，就比较耗时和浪费空间(因为需要移动大量元素)。所以，就有了链表的学习,而链式存储是最常用的动态存储方法。

一、什么是单链表？

链表是用一组任意的存储单元来存放线性表的节点，这组存储单元可以是连续的，也可以是非连续的，甚至可以零散分布在内存的任何位置上。
因此，链表中节点的逻辑顺序和物理顺序不一定相同。

这个节点由两部分组成，一是数据域，用来存放这个节点的值，二是存储下一个节点的地址。

我们可以这样来理解：
链表：逻辑上连续，多个节点采用挂载的方式进行连接，物理上不连续。

我们可以把链表类比做火车，当数据不够时，就新增一节车厢挂载在火车尾。
假设一节车厢只能存储一个元素，要存储5个元素，需要5个车厢，当增加一个元素，就只需要再挂载一个车厢，而不用像顺序表那样，去扩容一倍的空间。
火车结构，都是从头开始遍历，走到火车尾部（报数）
单向遍历：默认从前向后遍历。

二、单链表相关操作（不带虚拟头节点）

准备工作：
1.创建节点类（车厢类，一个车厢存储一个元素）

 class Node{
        int val;//存储具体数据
        Node next;//保存下一个车厢的地址
        public  Node(int value){
            
            this.val=value;
    }

2.创建链表类（火车类–若干个车厢拼接起来,可以将多个车厢连接和断开连接））
具体的增删查改操作都在这个类中实现

public class SingleLinkedList {
    private int size;//当前火车中车厢的节点个数（实际上就是具体元素的个数）
    private Node head;//指向当前火车的第一个节点

1.插入数据

• 头插法（在链表的头部插入）

 public void addFirt(int val){
        Node node=new Node(val);//创建一个车厢节点
        //判断当前的火车是否为空
        if(head==null){
            head=node;
        }else{
            node.next=head;
            head=node;
        }
        size++;
    }

• 任意位置插入元素

public void addIndex(int index,int val){
        //1.合法性
        if(index<0||index>size){
            System.err.println("add index illegal!");
            return;
        }
        //头插法
        if(index==0){
            addFirst(val);
            return;
        }
        //插入元素
        Node node=new Node(val);
        //需要找到待插入位置的前驱--从头开始走index-1步
        Node prev=head;
        for (int i = 0; i <index-1 ; i++) {
             prev=prev.next;
        }
        //此时prev指向待插入位置的前驱节点
        node.next=prev.next;
        prev.next=node;
        size++;
    }

• 尾部插入元素

public void addLast(int val){
        addIndex(size,val);
    }
    public int get(int index){
        if(rangeCheck(index)){
            //index合法，从头节点开始遍历链表，走到index位置
            Node node=head;
        //规定了node节点走的步数
            for (int i = 0; i <index; i++) {//注意边界
                node=node.next;
            }
            return node.val;
        }else{
            System.err.println("get index illegal!");
            return -1;
        }
    }

2.查询数据

判断当前链表中是否包含值为val的节点

 public boolean contains(int val){
        for (Node temp=head;temp!=null;temp=temp.next){
            if(temp.val==val){
                return true;
            }
        }
        return  false;
    }

3.修改元素

将链表中索引为index的节点值改为newVal，并返回原来旧节点的值

public int set(int index,int newVal){
        if(rangeCheck(index)){
            Node node=head;
            for (int i = 0; i < index; i++) {
                node=node.next;
            }
            int oldVal=node.val;
            node.val=newVal;
            return oldVal;//改成功后返回旧的值
        }
        else{
            System.err.println("set index illegal!");
            return -1;
        }
    }

注意：查和改都不能走到size.

4.删除元素

1. 删除任意元素节点
   引入临时变量存储原先head节点的地址，如果用头节点来遍历，最后会丢失头节点。

  public void removeIndex(int index){
        //1.判断合法性
        if(rangeCheck(index)){
            if(index==0){
                //删除头节点
                Node temp=head;
                head=head.next;
                temp.next=null;
                size--;
            }else{
                //inde为中间位置，然后找待删除位置的前驱
                Node prev=head;
                for (int i = 0; i < index-1; i++) {
                    prev=prev.next;
                }
                //待删除节点
                Node cur=prev.next;
                prev.next=cur.next;
                cur.next=null;
                size--;
            }
        }else{
            System.err.println("remove index illegal!");
        }
    }

如果只写head=head.next,而不写其他两个，则只是保证了原先的头节点访问不到而已，但头节点是实实在在存在的，依旧挂在链表上。
2.删除第一个元素

public void removeFirst(){
        removeIndex(0);
        }

3.删除最后一个元素

 public void removeLast() {
         removeIndex(size - 1);
     }

4.删除第一个值为value的节点

  public void removeValueOnce(int val){
        //遍历链表，找到值为value的节点，然后删除（正常删除都需要找到前驱，只有头节点没有前驱）
         if(head!=null&&head.val==val){
             //头节点就是待删除的节点
             Node temp=head;
             head=head.next;
             temp.next=null;
             size--;
         }else{
             //此时head一定不是待删除的节点
             Node prev=head;
             //判断前驱的下一个节点值是否等于value
           while(prev.next!=null){//看你取值用的是哪个引用，就判断哪个引用不为空
              if(prev.next.val==val){
                  Node cur=prev.next;
                   prev.next=cur.next;
                   cur.next=null;
                   size--;
                   return;
                   }
                   //prev不是待删除节点的前驱，prev向后移动
                   prev=prev.next;
               }
         }
     }

5.删除所有值为val的节点

public  void removeValueAll(int val){
        //判断头节点是否是待删除节点
         while (head!=null&&head.val==val){
             head=head.next;
             size--;
         }
         if(head==null){
             //此时链表中的值全是val,及删空了链表
             return;
         }else{
             //此时head一定不是待删除节点，并且链表中还有节点
             Node prev=head;
             while(prev.next!=null){
                if(prev.next.val==val){
                   Node cur=prev.next;
                  prev.next=cur.next;
                   cur.next=null;
                   size--;
                 }else{
                  prev=prev.next;//确保prev.next不是待删除的节点时才能移动prev指向
                 }
             }
         }
     }

关键点：

1. 因为要通过head引用取得val值–head.val，所以为了避免空指针异常，循环中必须要满足head!=null。
2. 只有当确保prev.next不是待删除的节点时才能移动prev=prev.next;指向
   prev一定不是待删除的节点

总结

在单链表的插入与删除，都需要找到前驱节点（只有头节点没有前驱，因此需要特殊处理），那么找到前驱便找到插入与删除的钥匙。

优点：1.对链表进行增加元素时，只要内存够用，就不会发生溢出。
2.增加和删除元素时，会比顺序表更方便。
缺点：查寻和更新元素需要从头向后遍历，会比较耗时。