【数据结构篇】手写双向链表、单向链表（超详细）

文章目录

  • 链表
    • 1、基本介绍
    • 2、单向链表
      • 2.1 带头节点的单向链表
        • 测试类：
        • 链表实现类：
      • 2.2 不带头节点的单向链表
      • 2.3 练习
        • 测试类：
        • 链表实现类：
    • 3、双向链表
        • 测试类：
        • 双向链表实现类：
    • 4、单向环形链表
        • **测试类**：
        • **实现类**：

链表

1、基本介绍

  • 什么是链表？

    链表（Linked List）是用链式存储结构实现的线性表。链表示意图：

    image-20220814112509739

  • 链表的组成：数据域+引用域（数据域和引用域合称结点或元素）

    • 数据域存放数据元素自身的数据
    • 引用域存放相邻结点的地址

  • 链表的特点：

    • 链表中元素的联系依靠引用域

    • 具有线性结构的特点，链表所使用的逻辑结构是线性结构

    • 具有链式存储结构的特点，所使用的物理存储结构是链式存储

  • 链表的分类：

    • 单向链表：单链表是一种最简的链表，只有一个引用域1next

      特点：通过next可以访问到后继结点，终端结点的引用域指向null

    • 双向链表：具有两个引用域prev和next，prev用来保存前驱结点的地址，next用来保存后继结点的地址

      特点：通过next可以访问后继结点，终端结点的next指向null；通过prev可以访问到前驱节点，起始结点的prev指向null

    • 循环链表：循环链表本质是一种特殊的单向链表，只是它的终端结点指向了开始结点（也就是next存放了开始结点的地址）

      特点：所有结点都能具有前驱节点和后继结点

  • 链表的使用场景：对查找速度要求不高，但对插入和删除速度要求高时，可以使用链表。常见的比如：

2、单向链表

单向链表（简称单链表）有带头结点的单链表，也有不带头链表的单链表。

image-20220814212948169

image-20220814213046211

  • 单链表的基本操作：

    • 非空判断：判断链表中是否含有元素
    • 求表长度：获取链表中所有元素的个数
    • 插入结点：在单链表中添加一个新的结点
    • 删除结点：删除单链表中的结点
    • 取表元素：更具所给索引，确定该索引所在链表的结点
    • 定位元素：根据所给值，确定该元素所在链表的索引号
    • 修改元素：根据所给索引，修改对应的结点
    • 清空链表：清空链表中所有的元素

2.1 带头节点的单向链表

带头结点就是先固定一个头节点，用来标识链表的初始位置，它的data域不存任何东西，它的next域用来第一个结点的地址，每次遍历链表或定位结点都需要借助一个辅助变量temp来实现。

  • 插入结点示意图：

  • 删除结点示意图：

  • 修改结点示意图：

遍历经验总结：当我们想要进行的操作的结点依赖于前一个结点时，比如插入、删除、修改等操作操作，就必须从head结点开始遍历，否则会出现空指针异常；当我们想要进行的操作不依赖前一个结点时，就无须从head结点开始遍历，比如根据id获取结点，非空判断、获取链表长度、展示链表等操作。

测试类：

package com.hhxy.linkedlist;import java.util.Scanner;import com.hhxy.queue.ArrayQueue2;
/*** 单向链表测试类* @author ghp* 测试数据：* 1 宋江 及时雨* 2 林冲 豹子头* 3 鲁智深 花和尚* 4 吴用 智多星*/
public class SingleLinkedListTest {public static void main(String[] args) {Scanner sc = new Scanner(System.in);SingleLinkedListDemo1 sll = new SingleLinkedListDemo1();//创建链表OUT:while(true) {System.out.println("-------------------单向链表操作界面-----------------");System.out.println("请输入操作指令：");System.out.println("0 : 退出程序");System.out.println("1 : 在链尾添加结点");System.out.println("2 : 按id从小到大的顺序添加结点");System.out.println("3 : 根据id获取结点");System.out.println("4 : 根据id删除结点");System.out.println("5 : 获取链表中元素的个数");System.out.println("6 : 展示链表中所有的元素");System.out.println("7 : 根据id修改结点");System.out.println("8 : 清空链表");//用于接收用户输入int id;String name="";String alias="";Student student = null;switch(sc.next()) {case "0": //退出程序System.out.println("正在退出程序~~~");break OUT;case "1": //在链尾添加结点System.out.println("请按照 id name alias 的格式输入要添加的元素：");id = sc.nextInt();name = sc.next();alias = sc.next();student = new Student(id,name,alias);if(sll.add(student)) System.out.println("结点："+student+"添加成功！");break;case "2"://按id从小到大的顺序添加结点System.out.println("请按照 id name alias 的格式输入要添加的元素：");id = sc.nextInt();name = sc.next();alias = sc.next();student = new Student(id,name,alias);if(sll.addById(student)) System.out.println("结点："+student+"添加成功！");break;case "3"://根据id获取结点System.out.println("请输入要获取结点的id号：");id = sc.nextInt();try {student  = sll.get(id);System.out.println(id+"号结点为："+student);}catch(Exception e){System.out.println(e.getMessage());}break;case "4"://根据id删除结点System.out.println("请输入要删除结点的id号：");id = sc.nextInt();try {if(sll.remove(id)) System.out.println("结点删除成功！");}catch(Exception e) {System.out.println(e.getMessage());}break;case "5"://获取链表中结点的个数（不包括头节点）System.out.println("链表中的结点个数为："+sll.size());break;case "6"://展示链表中所有的结点（不包括头节点）sll.show();break;case "7"://根据id修改结点System.out.println("请按照 id name alias 的格式输入要修改的元素：");student = new Student(sc.nextInt(),sc.next(),sc.next());try {if(sll.update(student)) System.out.println("修改成功");}catch(Exception e) {System.out.println(e.getMessage());}break;case "8"://清空链表if(sll.clear()) System.out.println("链表已成功清空！");break;default:System.out.println("请输入有效指令！");break;}}System.out.println("程序已退出");}
}

image-20220816094057645

链表实现类：

package com.hhxy.linkedlist;//结点类
class Student{//数据域（将成员变量设置为public方便外部访问）public int id;public String name;public String alias;//引用域public Student next;public Student(int id, String name, String alias) {this.id = id;this.name = name;this.alias = alias;}@Overridepublic String toString() {return "[id=" + id + ", name=" + name + ", alias=" + alias + "]";}
}//链表类
public class SingleLinkedListDemo1 {//初始化头结点Student head = new Student(-99,"","");/*** 判断链表是否为空* @return true表示链表为空*/public boolean isEmpty() {//因为头节点是链表位置的标识，不能动，所以使用一个辅助引用来遍历链表Student temp = head.next;if(temp!=null) {//head后面存在至少一个元素，所以链表不为空return false;}return true;}/*** 在链尾添加结点* @param student 待添加的结点* @return true表示添加成功*/public boolean add(Student student) {//同理，因为链表头节点不能动。//注意：需要是从头节点开始遍历，因为链表可能为空，如果从头节点后一个遍历，当链表为空时会报空指针异常Student temp = head;//遍历寻找尾结点。因为temp=head，所以是从头节点开始遍历while(temp.next != null) {temp = temp.next;}//已找到链表尾结点，进行指向temp.next = student;return true;}/*** 按照id从小到大的顺序添加结点* @param student 待添加的结点* @return true表示添加成功*/public boolean addById(Student student) {Student temp = head;boolean flag = true;//用于判断链表是加在尾结点，还是加在结点之间while(temp.next != null) {if(student.id < temp.next.id) {//说明是添加在结点之间flag = false;break;}temp = temp.next;}if(flag) {//如果添加的结点是在尾结点temp.next = student;}else {//添加的结点是在结点之间student.next = temp.next;//切记：先改变后一个指向，再改变前一个指向temp.next = student;}return true;}/*** 根据id获取结点* @param id * @return 返回对应id的结点*/public Student get(int id) {if(isEmpty()) {throw new RuntimeException("该链表为空！");}Student temp = head.next;//从head结点后面开始遍历boolean flag = false;//判断链表中是否存在待获取的结点while(temp != null) {if(temp.id == id) {//找到id对应的结点flag = true;break;}temp = temp.next;}if(flag) {//如果找到id对应结点return temp;}else {//如果没有找到id对应的结点throw new RuntimeException("待获取的结点不存在！");}}/*** 根据id删除结点* @param id 待删除结点的id* @return true表示删除成功*/public boolean remove(int id) {if(isEmpty()) {throw new RuntimeException("链表为空！");}Student temp = head;//删除结点需要依赖前一个结点，所以从头节点开始遍历boolean flag = false;//判断链表中是否存在待删除的结点while(temp.next != null) {if(temp.next.id == id) {//找到该结点flag = true;break;}temp = temp.next;}if(flag) {//如果找到了要删除的结点temp.next = temp.next.next;}else {//如果没有找到id对应的结点throw new RuntimeException("待删除的结点不存在！");}return true;}/*** 获取链表中结点的个数（不包括头节点）*/public int size() {Student temp = head;int count = 0;//这里虽然遍历了头节点，但是没有遍历尾结点while(temp.next != null) {count++;temp = temp.next;}return count;}/*** 展示链表中所有的结点（不包括头节点）*/public void show() {if(isEmpty()) {System.out.println("链表为空！");return;}//注意：不需要展示头节点！Student temp = head;while(temp.next != null) {System.out.println(temp.next);temp = temp.next;}}/*** 根据id修改结点* @param student 待修改的结点* @return true表示修改成功*/public boolean update(Student student) {if(isEmpty()) {throw new RuntimeException("链表为空！");}Student temp = head;boolean flag = false;//判断链表是否修改成功while(temp.next != null) {if(temp.next.id == student.id) {//找到要修改的链表flag = true;student.next = temp.next.next;temp.next = student;break;}temp = temp.next;}if(flag) {//如果修改成功return true;}else {//如果链表中没有找到待删除的结点throw new RuntimeException("链表中不存在该结点");}}/*** 清空链表* @return true表示清空成功*/public boolean clear() {/*方式一：直接将头节点指向空(节约时间，但占内存)* head.next = null;* 除头节点以外其它结点存在引用，JVM不会回收结点内存，仍然会占据内存* 这种清楚方法很费内存！ *///方式二：将所有结点占据的内存都进行释放（耗时，但不占内存）Student2 temp = head;//这里需要从后往前遍历，逐步去掉所有结点的引用，否则无法遍历下取while(head.next != null) {for (int i = size(); i > 1; i--) {temp = temp.next;}temp.next = null;}return true;}
}

2.2 不带头节点的单向链表

略……逻辑思路都差不多，只是将头节点换成一个头指针

不带头节点和带头结点的主要区别：带头结点遍历的时候、不能将头节点进行计数；而不带结点能够直接进行遍历

本质上两者并没有什么太大区别，带头节点的链表没有指针，头结点就相当于头指针，而不带头节点的链表是由头指针的

注意：这里所谓的指针和结点其实都是结点对象，只是指针初始值为null，结点要进行初始化

2.3 练习

  • 反转链表示意图：

image-20220815155534532

  • 合并链表示意图：

测试类：

/*** 练习题1：获取链表倒数第k个结点* 练习题2：将链表反转* 练习题3：从尾到头打印链表的结点* 练习题4：合并两个有序链表，合并后仍然有序*/
//测试类：
public class SingleLinkedListDemo3{public static void main(String[] args) {Node node1 = new Node(1);Node node2 = new Node(2);Node node3 = new Node(3);SingleLinkedList sll = new SingleLinkedList();sll.add(node1);sll.add(node2);sll.add(node3);System.out.println("链表原始状态：");sll.show();System.out.println("------------------------");//测试1：测试获取链表倒数第k个结点Node t = sll.findLastIndexNode(sll, 1);System.out.println(sll.findLastIndexNode(sll,1));System.out.println(sll.findLastIndexNode(sll,2));System.out.println(sll.findLastIndexNode(sll,3));System.out.println("-------------------------");//测试2：测试将链表反转sll.reverset(sll);System.out.println("反转后的链表：");sll.show();System.out.println("-------------------------");//测试3：从头到位打印链表System.out.println("反向打印链表：");sll.reversetPrint(sll);System.out.println("-------------------------");//测试4：将两个有序链表合并，合并后仍然有序SingleLinkedList list1 = new SingleLinkedList();SingleLinkedList list2 = new SingleLinkedList();Node node4 = new Node(4);Node node5 = new Node(5);Node node6 = new Node(6);Node node7 = new Node(7);Node node8 = new Node(8);Node node9 = new Node(9);Node node10 = new Node(10);Node node11 = new Node(11);list1.add(node4);list1.add(node7);list1.add(node8);list1.add(node10);list1.add(node11);System.out.println("链表1：");list1.show();System.out.println("链表2：");list2.add(node5);list2.add(node6);list2.add(node9);list2.show();SingleLinkedList list = new SingleLinkedList();list = list.combine(list1, list2);System.out.println("合并后的链表：");list.show();}
}

image-20220816092954578

image-20220816093034382

链表实现类：

package com.hhxy.linkedlist;import java.util.Stack;//结点类
class Node {int n;Node next;public Node(int n) {this.n = n;}@Overridepublic String toString() {return "[n=" + n + "]";}
}
//链表类：
public class SingleLinkedList {//初始化头节点public Node head = new Node(-99);/*** 添加结点*/public void add(Node node) {Node current = head;while(current.next != null) {current = current.next;}current.next = node;}/*** 获取链表的长度* @return*/public int size() {Node current = head.next;int count = 0;while(current != null) {count++;current = current.next;}return count;}/*** 展示*/public void show() {Node current = head.next;while(current != null) {System.out.println(current);current = current.next;}	}/*--------------------核心方法-------------------------*//*** 寻找链表倒数第k个结点* @param index* @return*/public Node findLastIndexNode(SingleLinkedList sll,int index) {Node head = sll.head;if(index <0 || index>sll.size() || head.next == null) {return null;}Node current = head.next;//将指针从第二个结点开始往后移动index位for (int i = 0; i < size()-index; i++) {current = current.next;}return current;}/*** 将链表反转* @param sll 待反转的链表*/public void reverset(SingleLinkedList sll) {Node head = sll.head;if(head.next == null || head.next.next == null) {//当前链表为空，或者只有一个结点，直接返回return;}SingleLinkedList sllTemp = new SingleLinkedList();//创建一个新链表Node headTemp = sllTemp.head;Node temp = null;//用来存旧链表的引用，方便遍历旧链表Node current = head.next;//辅助遍历旧链表while(current != null) {temp = current.next;//不保存，新链表就会断开，就无法进行遍历了current.next = headTemp.next;//指向新创建的头结点的后面的结点headTemp.next = current;//新创建的头结点，指向插入的结点current = temp;//指针往后移}head.next = headTemp.next;}/*** 反向打印链表* @param sll*/public void reversetPrint(SingleLinkedList sll) {Node head = sll.head;if(head.next == null) {return;}/*//方式一：使用findLastIndexNode方法（要先实现findLastIndexNode方法，不值得推荐）for(int i=1;i<=sll.size();i++) {System.out.println(sll.findLastIndexNode(sll, i));}//方式二：使用reverset方法（要先实现reverset方法，并且改变了链表的结构，不值得推荐）reverset(sll);sll.show();*///方式三：使用栈（强烈推荐）Stack<Node> stack = new Stack<>();Node current = head.next;while(current != null) {stack.push(current);current = current.next;}while(stack.size()>0) {System.out.println(stack.pop());}}/*** 合并两个有序链表，合并后仍然有序(这里我是默认按从小到大排序的)*/public SingleLinkedList combine(SingleLinkedList sll1,SingleLinkedList sll2) {Node head1 = sll1.head.next;//用于遍历sll1链表Node head2 = sll2.head.next;if(head1 == null || head2  == null) {//只要有一个链表为空就直接返回return head1 != null ? sll1 : sll2;}SingleLinkedList sll = new SingleLinkedList();//合并后的链表Node temp=sll.head;//用来给sll链表添加结点的while (head1 != null && head2 != null){if (head1.n < head2.n){//链表1的结点是当前最小结点temp.next = head1;//新链表连接最小结点temp = temp.next;//每新增一个结点，temp就往后移一位，保证他在尾结点方便连接新结点head1 = head1.next;//链表1的指针也往后移一位}else{//链表2的结点是当前最小结点temp.next = head2;temp = temp.next;head2 = head2.next;}}if (head1 != null && head2 == null){//经过一一段时间的合并后，sll2的链表为空了，直接就将sll1链表后面的结点拼接上去temp.next = head1;}if (head1 == null && head2 != null){temp.next = head2;}return sll;}/*------------------------------------------------*/
}

3、双向链表

双向链表相对单向链表就较为简单了，因为每个结点既能往后遍历，又能往前遍历 ，对于插入、删除、修改都无需像单链表一样依靠前一个结点。

与单链表的主要区别：

  1. 遍历不仅可以往前遍历，还可以往后遍历

  2. 插入、删除、修改不需要依赖前一个结点（在链尾插入需要依赖尾结点）

  3. 添加的时候，需要进行双向绑定！

  • 双向链表插入示意图：

    链表插入演示

    image-20220816113620558

  • 双向链表删除示意图：

    链表删除演示

    image-20220816114235701

测试类：

和单向链表的测试方法相同

示意图：

image-20220816163415447

双向链表实现类：

其实只要理解了单向链表，再来看双向链表就会觉得so easy😄单向链表的方法双向链表都能使用，只是添加和修改的时候，需要多修改下prev的的指向。

package com.hhxy.linkedlist.doubles;
//结点类
class Student2{public int id;public String name;public String alias;public Student2 prev;//指向前一个结点public Student2 next;//指向后一个结点public Student2(int id, String name, String alias) {super();this.id = id;this.name = name;this.alias = alias;}@Overridepublic String toString() {return "Student [n=" + id + ", name=" + name + ", alias=" + alias + "]";}
}
//链表类
public class DoubleLinkedListDemo1 {//初始化头节点public Student2 head = new Student2(-99,"","");/*** 判断链表是否为空* @return true表示链表为空*/public boolean isEmpty() {//因为头节点是链表位置的标识，不能动，所以使用一个辅助引用来遍历链表Student2 temp = head.next;if(temp!=null) {//head后面存在至少一个元素，所以链表不为空return false;}return true;}/*** 在链尾添加结点* @param student2 待添加的结点* @return true表示添加成功*/public boolean add(Student2 student2) {//同理，因为链表头节点不能动。//注意：需要是从头节点开始遍历，因为链表可能为空，如果从头节点后一个遍历，当链表为空时会报空指针异常Student2 temp = head;//遍历寻找尾结点。因为temp=head，所以是从头节点开始遍历while(temp.next != null) {temp = temp.next;}//形成双向链表temp.next = student2;student2.prev = temp;return true;}/*** 按照id从小到大的顺序添加结点* @param student2 待添加的结点* @return true表示添加成功*/public boolean addById(Student2 student2) {Student2 temp = head;boolean flag = true;//用于判断链表是加在尾结点，还是加在结点之间while(temp.next != null) {if(student2.id < temp.next.id) {//说明是添加在结点之间flag = false;break;}temp = temp.next;}if(flag) {//如果添加的结点是在尾结点//形成双向链表temp.next = student2;student2.prev = temp;}else {//添加的结点是在结点之间，注意要形成双向指向student2.next = temp.next;//切记：先改变后一个指向，再改变前一个指向temp.next.prev = student2;//前面一根线temp.next = student2;student2.prev = temp;}return true;}/*** 根据id获取结点* @param id * @return 返回对应id的结点*/public Student2 get(int id) {if(isEmpty()) {throw new RuntimeException("该链表为空！");}Student2 temp = head.next;//从head结点后面开始遍历boolean flag = false;//判断链表中是否存在待获取的结点while(temp != null) {if(temp.id == id) {//找到id对应的结点flag = true;break;}temp = temp.next;}if(flag) {//如果找到id对应结点return temp;}else {//如果没有找到id对应的结点throw new RuntimeException("待获取的结点不存在！");}}/*** 根据id删除结点* @param id 待删除结点的id* @return true表示删除成功*/public boolean remove(int id) {if(isEmpty()) {throw new RuntimeException("链表为空！");}//使用双向链表可以进行自我删除Student2 temp = head.next;//删除结点需要依赖前一个结点，所以从头节点开始遍历boolean flag = false;//判断链表中是否存在待删除的结点while(temp != null) {if(temp.id == id) {//找到该结点flag = true;break;}temp = temp.next;}if(flag) {//如果找到了要删除的结点temp.prev.next = temp.next;//前一根线if(temp.next != null) {//要排除最后一个结点的可能，否则会出现空指针异常temp.next.prev = temp.prev;//后一根线}}else {//如果没有找到id对应的结点throw new RuntimeException("待删除的结点不存在！");}return true;}/*** 获取链表中结点的个数* @return*/public int size() {Student2 temp = head;int count = 0;while(temp.next != null) {count++;temp = temp.next;}return count;}/*** 展示链表中所有的结点*/public void show() {if(isEmpty()) {System.out.println("链表为空！");return;}Student2 temp = head;while(temp.next != null) {System.out.println(temp.next);temp = temp.next;}}/*** 根据id修改结点* @param student2 待修改的结点* @return true表示修改成功*/public boolean update(Student2 student2) {if(isEmpty()) {throw new RuntimeException("链表为空！");}Student2 temp = head.next;boolean flag = false;//判断链表是否修改成功while(temp != null) {if(temp.id == student2.id) {//找到要修改的链表flag = true;//后一根线student2.next = temp.next;if(temp.next!=null) {//排除最后一个节点temp.next.prev = student2;}//前一根线temp.prev.next = student2;student2.prev = temp.prev;break;}temp = temp.next;}if(flag) {//如果修改成功return true;}else {//如果链表中没有找到待删除的结点throw new RuntimeException("链表中不存在该结点");}}/*** 清空链表* @return*/public boolean clear() {/*方式一：直接将头节点指向空(节约时间，但占内存)* head.next = null;* 除头节点以外其它结点存在引用，JVM不会回收结点内存，仍然会占据内存* 这种清楚方法很费内存！ * return true;*///方式二：将所有结点占据的内存都进行释放（耗时，但不占内存）Student2 temp = head;//这里需要从后往前遍历，逐步去掉所有结点的引用，否则无法遍历下取Student2 current = head;while(current.next != null) {current = temp;current.next = null;current.prev = null;temp = temp.next;}return true;}
}

4、单向环形链表

基本和单向链表类似，也可以分为带头节点，和不带头结点点，这里演示的是不带头结点的单向环形链表，单向环形链表和单向链表唯一的区别：尾结点的next不指向空，而是指向开始节点。

主要思想还是在单链表那一节😄只要掌握单向链表，这些双向链表还有单向循环链表就是弟弟(′д｀ )…彡…彡直接套用第一节的接口，实现所有的方法

image-20220816150410003

测试类：

和2.1一样，换个对象就行了（这个测试类真渣😆）

image-20220816190136942

image-20220816190151341

image-20220816190201109

image-20220816190207580

实现类：

这里主要记录以下按顺序插入结点的思路，怕以后忘记了。其实主要思想还是和单向链表的addById方法的逻辑是一致的，主要是要考虑循环！思路主要如下：

  1. 先将链表添加分为两大类，首结点的添加 和 非首结点的添加，因为首结点的添加需要自动成环
  2. 再将非首结点的添加又分为在 添加在首结点之前 和 之后，之前需要移动first指针，之后不需要移动

示意图：

删除结点：

  1. 先将删除分为两大类，删除头结点 和 删除普通结点
  2. 删除头结点又可以分为两类，链表只有一个头结点 和 除了头结点还有其它结点
  3. 删除普通结点时需要注意链表是单向的，删除操作需要依赖待删除结点的前一个结点

修改结点的逻辑思路和删除类似，不在赘述，示意图：

  • 清空链表：链表的清空有两种方法，一种是直接让first=null，这种清空简单省事，但是是假清空，链表仍然存在内存中！

    第二种方法是让每个结点的next指向空，然后将first=null，这种费脑子但是省空间

package com.hhxy.linkedlist.circular;//结点类
class Student{public int id;public String name;public String alias;public Student next;public Student(int id, String name, String alias) {super();this.id = id;this.name = name;this.alias = alias;}@Overridepublic String toString() {return "[id=" + id + ", name=" + name + ", alias=" + alias + "]";}
}//链表类
public class CircularLinkedListDemo1 {private Student first = null;//注意这是头指针，不是头结点！/*** 非空判断* @return true表示为空*/public boolean isEmpty() {//因为是没有头结点，所以直接判断firstif(first != null) {return false;}else {return true;}}/*** 在尾结点添加结点* @param student* @return true表示结点添加成功*/public boolean add(Student student) {if(first == null) {//对第一个结点进行单独考虑first =  student;first.next = first;//构成环状return true;}else {Student current = first;//找到最后一个结点while(current.next != first) {current = current.next;}//找到后将节点加入环形链表中current.next = student;student.next = first;return true;}}/*** 根据id从小到大的顺序添加结点* @return true表示添加成功*/public boolean addById(Student student) {if(first == null) {//第一个结点单独成环first = student;first.next = first;}else {Student current = first;if(student.id < current.id && current == first) {//说明这个结点比头结点还要小，要将头指针移动位置current.next = student;student.next = current;first = student;//将first移动到student上return true;}while(current.next != first) {//寻早结点添加的位置if(student.id < current.next.id) {//已找到添加的位置break;}current = current.next;}student.next = current.next;//切记：一定要先改变后一根线，不然链表会断裂！current.next = student;}return true;}/*** 根据id获取结点*/public Student get(int id) {if(isEmpty()) {throw new RuntimeException("链表为空！");}Student current = first;boolean flag = false;while(true) {if(current.id == id) {//找到就直接结束遍历flag = true;break;}if(current.next == first) {//如果是最后一个结点，就表明还没有找到，直接结束遍历break;}current = current.next;//辅助指针后移，遍历链表}if(flag) {//找到就返回这个结点return current;}else {//没有找到，打印提示信息throw new RuntimeException("链表中不存在该结点！");}}/*** 根据id删除结点*/public boolean remove(int id) {if(isEmpty()) {throw new RuntimeException("链表为空！");}if(first.id == id) {//当头结点就是要删除的结点时，分类讨论if(first.next == first) {//如果链表只有头结点时first = null;return true;}else {//如果链表除了头结点还有其它结点时，需要移动first指针Student current = first;//找到尾结点while(current.next != first) {current = current.next;}current.next = current.next.next;first = current.next;//移动头指针return true;}}//删除普通结点Student current = first;boolean flag = false;//判断链表中是否存在该结点while(true) {if(current.next.id == id) {//这里使用current.next判断是为了使用前一个结点//找到结点直接退出flag = true;break;}if(current.next == first) {//遍历完成，直接退出break;}current = current.next;}if(flag) {//找到待删除的结点，利用前一个结点将其删除（思路和单项链表是一样的）current.next = current.next.next;return true;}else {throw new RuntimeException("该结点不存在！");}}/*** 获取链表长度*/public int size() {Student current = first;if(isEmpty()) {return 0;//这里要不要都无所谓，只是习惯了~~~}int count = 0;while(true) {count++;if(current.next == first) {break;}current = current.next;}return count;}/*** 展示链表*/public void show() {Student current = first;if(first == null) {//排除空链表throw new RuntimeException("链表为空！");}while(true) {System.out.println(current);if(current.next == first) {//当发现结点是最后一个结点直接退出打印break;}current = current.next;}}/*** 根据id修改结点*/public boolean update(Student student) {if(isEmpty()) {throw new RuntimeException("链表为空！");}if(student.id == first.id) {//修改的结点是头节点if(first.next == first) {//只有一个头节点first = student;first.next = student;return true;}else {//除了头节点还有其它结点Student current = first;//找到尾结点while(current.next != first) {current = current.next;}student.next = current.next.next;//修改后一根线current.next = student;//修改前一根线first = student;//修改头指针return true;}}//修改的结点是普通结点Student current = first;boolean flag = false;//判断链表中是否存在该结点while(current.next != first) {if(current.next.id == student.id) {//找到结点，直接退出flag = true;break;}current = current.next;}if(flag) {student.next = current.next.next;//修改后一根线，防止链表断裂current.next = student;return true;}else {throw new RuntimeException("不存在该结点！");}}/*** 	清空链表*/public boolean clear() {/*方式一：直接将头节点指向空(节约时间，但占内存)* first.next = null;* 除头节点以外其它结点存在引用，JVM不会回收结点内存，仍然会占据内存* 这种清楚方法很费内存！ * return true;*///方式二：将所有结点占据的内存都进行释放（耗时，但不占内存）if(isEmpty()) {return true;}if(first == first.next) {//只有一个结点first = null;return true;}Student temp = first;//临时存储current的引用，辅助遍历Student current = first;//将链表每个结点的引用都断开，这样每个结点都没有被引用，就能被JVM给回收while(current.next != first) {temp = temp.next;current.next = null;current = temp;}//将最后一个结点的引用 和头指针 设为空current.next = null;//不断开最后一个接待你的引用，头节点就不会被回收first = null;return true;}
}

  1. 引用域：是链表结点中一片很小的空间，用来存放后继结点的地址 ↩︎

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/78748.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

从零开始实现一个 mini-Retrofit 框架

从零开始实现一个 mini-Retrofit 框架

前言 本篇文章将采用循序渐进的编码方式&#xff0c;从零开始实现一个Retorift框架&#xff0c;在实现过程中不断提出问题并分析实现&#xff0c;最终开发出一个mini版的Retrofit框架 演示一个使用OkHttp的项目Demo 为了更好的演示框架的实现过程&#xff0c;这里我先创建了一…
阅读更多...
mongodb-win32-x86_64-2008plus-3.4.24-signed.msi

mongodb-win32-x86_64-2008plus-3.4.24-signed.msi

Microsoft Windows [版本 6.1.7601] 版权所有 (c) 2009 Microsoft Corporation。保留所有权利。C:\Users\Administrator>cd C:\MongoDB\Server\3.4\binC:\MongoDB\Server\3.4\bin>C:\MongoDB\Server\3.4\bin>mongod --help Options:General options:-h [ --help ] …
阅读更多...
【MySQL】增删查改基础

【MySQL】增删查改基础

文章目录 一、创建操作1.1 单行插入1.2 多行插入1.3 插入否则替换更新1.4 替换replace 二、查询操作2.1 select查询2.2 where条件判断2.3 order by排序2.4 limit筛选分页结果 三、更新操作四、删除操作4.1 删除一列4.2 删除整张表数据 五、插入查询结果 CRUD : Create(创建), R…
阅读更多...
CS 144 Lab Four 收尾 -- 网络交互全流程解析

CS 144 Lab Four 收尾 -- 网络交互全流程解析

CS 144 Lab Four 收尾 -- 网络交互全流程解析 引言Tun/Tap简介tcp_ipv4.cc文件配置信息初始化cs144实现的fd家族体系基于自定义fd体系进行数据读写的adapter适配器体系自定义socket体系自定义事件循环EventLoop模板类TCPSpongeSocket详解listen_and_accept方法_tcp_main方法_in…
阅读更多...
【雕爷学编程】Arduino动手做（188）---0.66寸OLED液晶屏模块

【雕爷学编程】Arduino动手做（188）---0.66寸OLED液晶屏模块

37款传感器与模块的提法&#xff0c;在网络上广泛流传&#xff0c;其实Arduino能够兼容的传感器模块肯定是不止37种的。鉴于本人手头积累了一些传感器和执行器模块&#xff0c;依照实践出真知&#xff08;一定要动手做&#xff09;的理念&#xff0c;以学习和交流为目的&#x…
阅读更多...
Source Insight显示行号

Source Insight显示行号

1、默认不显示行号 (1)Source Insight默认是不显示行号的&#xff0c;如下图所示。 2、配置显示行号 2.1、方法1 (1)点击View→Line Numbers。 2.2、方法2 (1)空白处鼠标右键&#xff0c;在点击"Line Numbers"。 (2)配置显示行号后如下图所示。
阅读更多...
使用hexo进行博客迁移

使用hexo进行博客迁移

本文不会从0开始介绍如何通过hexo去搭建一个github page。因为最近折腾了下&#xff0c;发现这玩意儿确实写个博客很费劲&#xff0c;打算把他拖管到github当作我的知识库网站&#xff0c;我的主要文章还是通过mweb写完一键发布到博客园&#xff0c;然后csdn记录一些杂文和思考…
阅读更多...
Liunx环境下git的详细使用（gitee版）

Liunx环境下git的详细使用（gitee版）

Liunx环境下git的详细使用&#xff08;gitee版&#xff09; 1.git是什么2.git操作2.1在gitee创建一个仓库2.2.gitignore2.3.git 3.git三板斧3.1add3.2 commit3.3push 4.git其他命令4.1查看当前仓库状态4.2查看提交日志4.3修改git里面文件名称4.4删除文件4.5修改远端仓库内容 1.…
阅读更多...
低碳 Web 实践指南

低碳 Web 实践指南

现状和问题 2023年7月6日&#xff0c;世界迎来有记录以来最热的一天。气候变化是如今人类面临的最大健康威胁。据世界卫生组织预测2030年至2050年期间&#xff0c;气候变化预计每年将造成约25万人死亡。这是人们可以真切感受到的变化&#xff0c;而背后的主要推手是碳排放。 …
阅读更多...
Java分布式微服务2——声明式Http客户端（Feign）与网关（Gateway）

Java分布式微服务2——声明式Http客户端（Feign）与网关（Gateway）

文章目录 Http声明式客户端FeignFeign介绍与使用Feign自定义配置Feign性能优化Feign最佳实践方案 网关Gateway网关Gateway的作用与搭建路由断言工厂Route Predicate Factory路由过滤器GatewayFilter全局过滤器过滤器执行顺序网关的跨域处理 Http声明式客户端Feign Feign介绍与…
阅读更多...
Python魔法解析：探索变量类型的丰富多彩世界！

Python魔法解析：探索变量类型的丰富多彩世界！

在Python这个魔法般的编程语言中&#xff0c;变量是连接你与计算机世界的神奇桥梁。然而&#xff0c;这些变量并不是单一的&#xff0c;它们有着丰富多彩的类型。无论你是刚刚踏入编程的大门&#xff0c;还是想要深入了解Python的高级特性&#xff0c;本篇博客将带你探索变量的…
阅读更多...
c++学习(特殊类设计)[30]

c++学习(特殊类设计)[30]

只能在堆上创建对象的类 如果你想要确保对象只能在堆上创建&#xff0c;可以通过将析构函数声明为私有&#xff0c;并提供一个静态成员函数来创建对象。这样&#xff0c;类的实例化只能通过调用静态成员函数来完成&#xff0c;而无法直接在栈上创建对象。 以下是一个示例&…
阅读更多...
【PCIE】PCIE的驱动和pcie的端口驱动关系

【PCIE】PCIE的驱动和pcie的端口驱动关系

pice驱动和pcie端口驱动区别 PCIe的端口服务驱动与PCIe驱动之间存在一定的关系&#xff0c;但它们是不同的概念。 PCIe驱动是用于管理和操作PCIe设备的驱动程序。它负责与硬件进行通信&#xff0c;并实现对PCIe设备的配置、数据传输以及其他相关操作。PCIe驱动通常涉及设备的…
阅读更多...
【NLP概念源和流】 05-引进LSTM网络（第 5/20 部分）

【NLP概念源和流】 05-引进LSTM网络（第 5/20 部分）

一、说明 在上一篇博客中，我们讨论了原版RNN架构，也讨论了它的局限性。梯度消失是一个非常重要的缺点，它限制了RNN对较短序列的建模。香草 RNN 在相关输入事件和目标信号之间存在超过 5-10 个离散时间步长的时间滞时无法学习。这基本上限制了香草RNN在许多实际问题上的应用，…
阅读更多...
NestJs Debug配置文件

NestJs Debug配置文件

&#xff08;事缓则圆,人缓则安,语迟则贵,虎行似病,鹰立似睡。清俞万春《荡寇志》&#xff09; {"version": "0.2.0","configurations": [{"type": "node","request": "launch","name": &quo…
阅读更多...
基于LNMP架构搭建Discuz论坛

基于LNMP架构搭建Discuz论坛

LNMP: L---->linux系统&#xff0c;操作系统。 N----->nginx网站服务&#xff08;前端),提供前端的静态页面服务。同时具有代理、转发的作用。&#xff08;转发就是转发后端请求&#xff0c;转发PHP&#xff09;&#xff0c;nginx没有处理动态资源的功能&#xff0c;他有…
阅读更多...
IO模型-信号驱动IO

IO模型-信号驱动IO

linux内核中存在一个信号SIGIO&#xff0c;这个信号就是用于实现信号驱动IO的。当应用程序中想要以信号驱动IO的模型读写硬件数据时&#xff0c;首先注册一个SIGIO信号的信号处理函数,当硬件数据就绪&#xff0c;硬件会发起一个中断&#xff0c;在硬件的中断处理函数中向当前进…
阅读更多...
Plus 框架分页合理化问题

Plus 框架分页合理化问题

需要关闭 MyBatis Plus的分页合理化 RuoYi-Vue-Plus框架默认的Mybatis Plus分页拦截器配置是打开了分页合理化&#xff0c;这样会导致溢出的分页数据本来应该返回空数据&#xff0c;打开之后而会永远返回默认的前10条数据。 /*** mybatis-plus配置类(下方注释有插件介绍)** au…
阅读更多...
CSS元素的显示模式

CSS元素的显示模式

1、现在我想做成小米左侧边栏这样的效果&#xff0c;该怎么做呢&#xff1f; 2、小米商城触碰之后会显示出新的商品案例 3、一碰到之后会出现这个列表 4、这里涉及到了元素显示模式&#xff1a; 5、用人进行划分可以分为男人和女人&#xff0c;根据男人和女人的特性进行相应的…
阅读更多...
【ChatGPT 指令大全】怎么利用ChatGPT写报告

【ChatGPT 指令大全】怎么利用ChatGPT写报告

目录 选定切入角度 报告开头 大纲生成 草稿撰写 研究报告 提出反对观点 报告总结 研究来源 总结 随着人工智能技术的快速发展&#xff0c;自然语言处理技术在各个领域的应用越来越广泛。其中&#xff0c;ChatGPT作为目前最先进的自然语言处理模型之一&#xff0c;其强…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023