文章目录

• 前言
• 一、什么是单链表
• • 1.1如何定义一个结点类？（每节火车的车厢）
  • 1.2如何定义一个链表？
• 二、单链表的增删改查
• • 1.增(add)
  • • 1.1头插
    • 1.2在链表的index位置插入
    • 1.3尾插
  • 2.删(remove)
  • • 2.1删除当前链表中索引为index的结点值
    • 2.2头删
    • 2.3尾删
    • 2.4删除当前链表中第一个值为value的节点
    • 2.5删除当前链表中所有值为value的节点
  • 3.修改
  • 4.查询
  • • 4.1查询当前链表第一个值为value的索引
    • 4.2查询当前链表中是否存在值为value的节点
    • 4.3查询当前链表中索引为index的结点值
• 三、总结

前言

链表时大部分初学者的第一个坎，那么单链表我们可以类比为现实生活中的火车，火车的不同车间之间，都是通过一个挂钩连接的，当这两个车厢脱钩后，这两个车厢就没有任何关系了，可以类比一下数组，数组是相邻的两个元素之间不仅逻辑上连续，物理上也连续，而单链表是逻辑上连续，物理上不一定连续
单链表 —> 火车

数组 —> 物理逻辑都连续

一、什么是单链表

假设每个火车车厢只保存了一个int值，这个值就是我们要保存的数据，每节车厢还要保存下一节车厢的地址

这种链表叫做单向链表，只能从头结点开始从前往后遍历，每个结点只保存了下一个节点的地址，只能一个方向遍历。

1.1如何定义一个结点类？（每节火车的车厢）

class Node{    int val;//每个节点储存的值    Node next;//当前节点的下一个节点的地址    public Node(){}    public  Node(int val) { this.val = val;    }    public  Node(int val,Node next) { this.val = val; this.next = next;    }}

1.2如何定义一个链表？

什么是链表：
由若干个链表节点构成的对象称为链表，每一列火车由若干个车厢组成，每个车厢就是一个Node对象
由多个Node对象组成的大实体就是链表对象
只要知道火车的火车头 Node head; 就能遍历当前这个链表中的所有节点，从head开始向后遍历

/** * 基于int的单链表 * 真正被用户使用的时火车类-单链表对象 */public class SingleLinkedList {    //链表的头节点    private Node head;    //当前链表中Node节点的个数 = 有效数值的个数    private  int size;    }

二、单链表的增删改查

对于单链表的操作，我们有一个重要的思想，就是找前驱节点

1.增(add)

在一个单链表中插入一个节点，默认是在当前单链表的头部插入

1.1头插

代码如下：

 public void addFirst(int val){ Node newNode = new Node(); newNode.val = val; if (head == null){     head = newNode; }else{     //表示当前链表不为空     newNode.next = head;     head = newNode; } size++;    }

1.2在链表的index位置插入

代码如下：

 public void add(int index, int val){ //1·若index位置时非法的 if (index < 0 || index > size){     System.err.println("add index illegal");     return; } //2·插入任意位置要找到前驱节点，但是链表中有一个元素没有前驱节点 //头节点没有前驱节点 if (index == 0){     //头插     addFirst(val); }else{     Node newNode = new Node();     newNode.val = val;     //3·当前索引合法且不是在链表的头部插入，要找到插入位置的前驱节点     Node prev = head;     for (int i = 0; i < index - 1; i++) {  prev = prev.next;     }     //此时prev一定指向了待插入节点的前驱     newNode.next = prev.next;     prev.next = newNode;     size++; }    }

1.3尾插

就在链表的尾部插入，直接调用add方法在链表的size位置插入

public void addLast(int val){ add( size, val);    }

2.删(remove)

增删改查中，删除操作对于任何的数据结构都是最难的

2.1删除当前链表中索引为index的结点值

代码如下：

public int remove(int index){ if (rangeCheck(index)){     if (index == 0){  //删除头结点  Node x = head;  head = head.next;  x.next = null;  size--;  return x.val;     }else{  //删除的链表的中间结点  //找前驱  Node prev = head;  for (int i = 0; i < index - 1; i++) {      prev = prev.next;  }  //prev就是待删除结点的前驱结点  Node node = prev.next;  prev.next = node.next;  node.next = null;  size--;  return node.val;     } } System.err.println("remove index illegal"); return -1;    } private boolean rangeCheck(int index) { if (index < 0 || index >= size){     return false; } return true;    }

2.2头删

代码如下：

 public int removeFirst(){ return remove(0);    }

2.3尾删

代码如下：

 public int removeLast(){ return remove(size - 1);    }

2.4删除当前链表中第一个值为value的节点

代码如下：

public void removeValueOnce(int val) { if (head == null) {     System.err.println("链表位空，无法删除");     return ; } if (head.val == val) {     Node x = head;     head = head.next;     x.next = null;     size--; } else {     Node prev = head;     while (prev.next != null) {  if (prev.next.val == val) {      Node node = prev.next;      prev.next = node.next;      node.next = null;      size--;      return;  }  prev = prev.next;     } }    }    }

2.5删除当前链表中所有值为value的节点

代码如下：

  public void removeAllValue(int val){while (head != null && head.val == val) {    //头结点就是待删除结点     Node x = head;     head = head.next;     x.next = null;     size--; }//头结点一定不是待删除结点 //判空 if (head == null){     return; }else {     Node prev = head;     while (prev.next != null) {  if (prev.next.val == val) {      Node node = prev.next;      prev.next = node.next;      node.next = null;      size--;  } else {      //只有当prev.next.next != val才能移动prev指针      prev = prev.next;  }     } }    }

3.修改

代码如下：

/**     * 修改索引为index的结点值为newVal,返回修改前的值     * @param index     * @param newVal     * @return     */    public int set(int index,int newVal){ if (rangeCheck(index)){     Node x = head;     for (int i = 0; i < index; i++) {  x = x.next;     }     int oldVal = x.val;     x.val = newVal;     return oldVal; } System.err.println("index illegal set error"); return -1;    } private boolean rangeCheck(int index) { if (index < 0 || index >= size){     return false; } return true;    }

4.查询

4.1查询当前链表第一个值为value的索引

 public int getByValue(int val){ int index = 0; for (Node x = head;x != null;x = x.next){     if(x.val == val){  //第一个值为val的节点  return index;     }     index++; } //说明当前链表中没有值为val的结点，返回-1 return -1;    }

4.2查询当前链表中是否存在值为value的节点

代码如下：

 public boolean contains(int val){ int index = getByValue(val); if (index == -1){     return false; } return true;    }

4.3查询当前链表中索引为index的结点值

代码如下：

 public int get(int index){ //1·判断index的合法性 if (rangeCheck(index)){     Node x = head;     for (int i = 0; i < index; i++) {  x = x.next;     }     return x.val; } System.err.println("index illegal get error"); return -1;    } private boolean rangeCheck(int index) { if (index < 0 || index >= size){     return false; } return true;    }

三、总结

以上就是今天要讲的内容，本文仅仅简单介绍了什么是单链表，以及单链表的增删改查操作，希望对大家有所帮助，欢迎各位大佬指正。