赞
踩
单链表:单链表中的每个节点不仅包含储存的数据,还包含指向下一个节点的链接。
定义节点:
- //定义节点
- class Node {
- public Node next;//指向下一个新的节点
- int val;
-
- public Node(int val) {//通过构造函数赋值
- this.val = val;
- }
- }
1.1、新创建一个节点
1.2、将cur的next指向pre的next
1.3、将pre的next指向cur
- //按照顺序插入元素
- public void addOrder(Node node) {
- Node temp = head;
- //寻找插入的位置
- while (true) {
- //1、链表为空、直接在链表尾部插入
- if (temp.next == null) {
- temp.next = node;
- return;
- }
- //2、需要找到插入点的前一个节点,
- if (temp.next.val >= node.val) {
- node.next = temp.next;
- temp.next = node;
- return;
- }
- temp = temp.next;
-
- }
-
- }

直接在链表尾部添加节点:只需要遍历到链表的最后,将next指向新的节点就可。
代码实现
- //在链表尾增加节点
- public void add(Node node) {
- //1、设置辅助节点
- Node temp = head;
- //2、找到链表的最后
- while (true) {
- if (temp.next != null) {
- temp = temp.next;
- } else {
- break;
- }
- }
- //3、找到最后,插入
- temp.next = node;
-
- }

2.1、找到待删除元素的上一个节点以及下一个节点
2.2、通过遍历找到待删除元素的前一个节点,通过将前一个节点的指向指向当前节点的下一个节点
代码实现
- //删除某一个节点
- public void deleteLinkList(int num) {
- Node temp = head;
- boolean flag = false;//标志位
-
- while (!flag) {
- if (temp.next == null) {
- System.out.println("链表中不存在待删除元素0");
- return;
- }
- if (temp.next.val == num) {
- System.out.println("找到了待删除数据:" + temp.next.val);
- flag = true;
- break;
- }
- temp = temp.next;
-
- }
- if (flag) {
- temp.next = temp.next.next;
- }
-
- }

通过遍历找到需要修改的节点,修改数据
- //修改节点
- public void updateLinkList(int data, int num) {
- Node temp = head;//辅助数组
-
- while (true) {
- if (temp.next == null) {
- System.out.println("链表为空");
- return;
- }
- if (temp.next.val == data) {
- //修改新元素
- temp.next.val = num;
- return;
- }
- temp = temp.next;
-
- }
-
-
- }
-

和修改节点相似
- //取得某一个节点
- public void getLinkList(int num) {
- Node temp = head;
-
- while (true) {
- if (temp.next == null) {
- System.out.println("链表中不存在该元素");
- return;
- }
- if (temp.next.val == num) {
- System.out.println("找到了该元素:" + temp.next.val);
- break;
- }
- temp = temp.next;
-
- }
-
- }

通过辅助数组,遍历到每一个节点,打印链表存储的数值
- //遍历节点
- public void show() {
- Node temp = head.next;
- if (head.next == null) {
- return;
- }
- System.out.print("单链表为:[ ");
- while (true) {
- if (temp == null) {
- break;
- }
- System.out.print(temp.val + "、");
- temp = temp.next;
- }
- System.out.println(" ]");
-
- }
-
- }

举例:头节点设定为链表的开始,所有的节点连接在后边
- package com.zheng.demo1;
-
- public class MySingleLinkList {
- public static void main(String[] args) {
- //创建节点
- Node node1 = new Node(1);
- Node node2 = new Node(2);
- Node node3 = new Node(3);
- Node node4 = new Node(4);
- Node node5 = new Node(8);
-
- //创建链表
- SingleLinkList singleLinkList = new SingleLinkList();
- singleLinkList.add(node1);
- singleLinkList.add(node2);
- singleLinkList.add(node3);
- singleLinkList.add(node4);
- singleLinkList.add(node5);
- System.out.println("添加数据后的节点:");
- singleLinkList.show();
-
- singleLinkList.getLinkList(3);//查找
- singleLinkList.deleteLinkList(4);
- System.out.println("删除数据4后的链表:");
- singleLinkList.show();
- //修改
- System.out.println("将数据为2的节点的值修改为22");
- singleLinkList.upDateLinkList(2, 22);
- System.out.println("修改后的节点信息:");
- singleLinkList.show();
-
- // //创建链表2
- // System.out.println("==================");
- // SingleLinkList singleLinkList1 = new SingleLinkList();
- // singleLinkList1.addOrder(node4);
- // singleLinkList1.addOrder(node3);
- // singleLinkList1.addOrder(node1);
- // singleLinkList1.addOrder(node2);
- // singleLinkList1.addOrder(node5);
- // singleLinkList1.show();
-
- }
-
- }
-
- class SingleLinkList {
- //构造一个头节点
- private Node head = new Node(0);
-
- //增加节点
- public void add(Node node) {
- //1、设置辅助节点
- Node temp = head;
- //2、找到链表的最后
- while (true) {
- if (temp.next != null) {
- temp = temp.next;
- } else {
- break;
- }
- }
- //3、找到最后,插入
- temp.next = node;
-
- }
-
- //删除某一个节点
- public void deleteLinkList(int num) {
- Node temp = head;
- boolean flag = false;//标志位
-
- while (!flag) {
- if (temp.next == null) {
- System.out.println("链表中不存在待删除元素0");
- return;
- }
- if (temp.next.val == num) {
- System.out.println("找到了待删除数据:" + temp.next.val);
- flag = true;
- break;
- }
- temp = temp.next;
-
- }
- if (flag) {
- temp.next = temp.next.next;
- }
-
- }
-
- //取得某一个节点
- public void getLinkList(int num) {
- Node temp = head;
-
- while (true) {
- if (temp.next == null) {
- System.out.println("链表中不存在该元素");
- return;
- }
- if (temp.next.val == num) {
- System.out.println("找到了该元素:" + temp.next.val);
- break;
- }
- temp = temp.next;
-
- }
-
- }
-
- //修改节点
- public void upDateLinkList(int data, int num) {
- Node temp = head;//辅助数组
-
- while (true) {
- if (temp.next == null) {
- System.out.println("链表为空");
- return;
- }
- if (temp.next.val == data) {
- //修改新元素
- temp.next.val = num;
- return;
- }
- temp = temp.next;
-
- }
-
-
- }
-
- //按照顺序插入元素
- public void addOrder(Node node) {
- Node temp = head;
- //寻找插入的位置
- while (true) {
- //1、链表为空、直接在链表尾部插入
- if (temp.next == null) {
- temp.next = node;
- return;
- }
- //2、需要找到插入点的前一个节点,
- if (temp.next.val >= node.val) {
- node.next = temp.next;
- temp.next = node;
- return;
- }
- temp = temp.next;
-
- }
-
- }
-
- //遍历节点
- public void show() {
- Node temp = head.next;
- if (head.next == null) {
- return;
- }
- System.out.print("单链表为:[ ");
- while (true) {
- if (temp == null) {
- break;
- }
- System.out.print(temp.val + "、");
- temp = temp.next;
- }
- System.out.println(" ]");
-
- }
-
- }
-
-
- //定义节点
- class Node {
- public Node next;//指向下一个新的节点
- int val;
-
- public Node(int val) {//通过构造函数赋值
- this.val = val;
- }
-
-
- }
-

实例二、单链表存储学生的信息
- package com.zheng.demo2;
-
- public class MyTest {
- public static void main(String[] args) {
-
- //定义节点
- Student student1 = new Student(1, "小明", "男");
- Student student2 = new Student(2, "小红", "女");
- Student student3 = new Student(3, "小黑", "男");
- Student student4 = new Student(4, "小青", "女");
-
- //2、初始化链表
- LinkList linkList = new LinkList();
- linkList.addStudent(student1);
- linkList.addStudent(student2);
- linkList.addStudent(student3);
- linkList.addStudent(student4);
-
- //遍历
- linkList.queryLinkList();
-
- }
-
- }
-
- class LinkList {
- //定义链表的开始位置
- private Student head = new Student(0, "", "");
-
- //增加节点,从尾部
- public void addStudent(Student student) {
- Student temp = head;//辅助数组
- boolean flag = false;
-
- while (true) {
- if (temp.next == null) {
- flag = true;
- break;
- } else {
- temp = temp.next;
- }
-
- }
- if (flag) {
- temp.next = student;
- }
- }
-
- //遍历
- public void queryLinkList() {
- Student temp = head;
- if (head.next == null) {
- System.out.println("链表为空");
- return;
- }
-
- while (true) {
- if (temp.next == null) {
- return;
- }
- System.out.println(temp.next);
- temp = temp.next;
- }
- }
-
-
- }
-
- //定义一个学生信息的节点类
- class Student {
- int id;//学号
- String name;//姓名
- String sex;//性别
- Student next;//下一个学生的节点
-
- public Student(int id, String name, String sex) {
- this.id = id;
- this.name = name;
- this.sex = sex;
- }
-
- @Override
- public String toString() {
- return "Student{" +
- "id=" + id +
- ", name='" + name + '\'' +
- ", sex='" + sex + '\'' +
- '}';
- }
- }

测试结果
单链表插入节点共有三种方式,除了我们常见的头插法和尾插法,还多加入了指定顺序插入节点。
就是在链表的头部一直插入节点。
- //判断单链表是否为null
- //单链表头插法
- public void addHead(Node node) {
- //如果链表为null,则把传入的第一个元素赋给head.next
- if (head.next == null){
- head.next = node;
- return;
- }
- //如果链表不为null,就定义一个temp来辅助插入节点
- Node temp = head.next;
- //把传入的节点插入单链表,注意两个步骤
- //1、head.next 指向 传入的节点
- //2、传入的节点.next 指向 temp
- head.next = node;
- node.next = temp;
- }

就是从链表的尾部插入节点。
- //尾插法
- //不管什么插入法,都需要把要插入的节点传入方法中
- public void addLast(Node node){
- //定义辅助变量来插入数据
- Node temp = head;
- //退出循环
- while (temp.next != null) {
- //遍历到单链表的尾部
- temp = temp.next;
- }
- //退出循环表示找到链表的最后一个节点,就在该节点插入传入的节点
- temp.next = node;
- }
头插法和尾插法的测试:
- /**
- * 单链表使用头插法和尾插法插入节点
- */
- public class InsertLinked {
- public static void main(String[] args) {
-
- Node node1 = new Node("head");
- Node node2 = new Node("middle");
- Node node3 = new Node("last");
- Node node4 = new Node("lastOne");
-
- SingleNode singleNode = new SingleNode();
- /*
- singleNode.addLast(node1);
- singleNode.addLast(node2);
- singleNode.addLast(node3);
- singleNode.addLast(node4);
- singleNode.show();
- */
- singleNode.addHead(node1);
- singleNode.addHead(node2);
- singleNode.addHead(node3);
- singleNode.addHead(node4);
- singleNode.show();
- }
- }
-
- class SingleNode{
-
- //初始化头节点,不放任何数据
- private Node head = new Node("");
-
- //尾插法
- //不管什么插入法,都需要把要插入的节点传入方法中
- public void addLast(Node node){
- //定义辅助变量来插入数据
- Node temp = head;
- //退出循环
- while (temp.next != null) {
- //遍历到单链表的尾部
- temp = temp.next;
- }
- //退出循环表示找到链表的最后一个节点,就在该节点插入传入的节点
- temp.next = node;
- }
-
- //判断单链表是否为null
- //单链表头插法
- public void addHead(Node node) {
- //如果链表为null,则把传入的第一个元素赋给head.next
- if (head.next == null){
- head.next = node;
- return;
- }
- //如果链表不为null,就定义一个temp来辅助插入节点
- Node temp = head.next;
- //把传入的节点插入单链表,注意两个步骤
- //1、head.next 指向 传入的节点
- //2、传入的节点.next 指向 temp
- head.next = node;
- node.next = temp;
- }
-
- //遍历链表,输出链表
- public void show(){
- //判断链表为null
- if (head.next == null) {
- System.out.println("链表为null");
- return;
- }
- //注意这里的链表是不存放节点的,所以和add的方法的遍历有所不同
- Node temp = head.next;
- while (temp != null) {
- System.out.println(temp);
- temp = temp.next;
- }
- }
- }
-
- class Node{
- //存放数据
- public String data;
-
- //指向当前节点的下一个节点,默认为null
- public Node next;
-
- public Node(String name) {
- this.data = name;
- }
-
- @Override
- public String toString() {
- return "Node{" +
- "name='" + data + '\'' +
- '}';
- }
- }

还有一种指定插入,但是需要在Node节点类再定义一个编号 属性,通过比较编号的大小来确定指定节点的插入顺序。即使插入的顺序不按照规律,但是最后遍历出来的节点还是会按照编号顺序来输出节点。
-
- //按照指定顺序插入节点
- public void addByOrder(Node1 node){
- //定义一个辅助变量temp
- Node1 temp = head;
- //定义一个标记,用来寻找 节点 要 插入的位置
- boolean flag = false;
- //遍历链表
- while (true) {
- //如果链表为null就退出循环
- if (temp.next == null) {
- //符合条件 退出循环
- break;
- }
- //比如我插入的节点的编号为4 (node.no==4),原来temp的后一个节点编号为5 (temp.next.no==5)
- //所以temp后一个节点的就不再指向编号为5的节点,而是指向编号为4的节点(也就是我当前插入的节点)
- // 5 > 4
- if (temp.next.no > node.no){
- //符合条件 退出循环
- break;
- }else if ( temp.next.no == node.no){
- flag = true; //说明编号已存在 ,不需要插入
- //继续循环遍历,直到找到合适的位置
- }
- temp = temp.next; //后移,相当于遍历当前链表
- }
- //判断flag的值
- //可以写成flag == true
- if (flag) { //不能插入
- System.out.println("该节点已存在");
- }else {
- //插入当前节点
- node.next = temp.next;
- temp.next = node;
- }
- }

这是指定顺序插入的测试代码
-
- public class InsertLinked {
- public static void main(String[] args) {
-
-
- //创建节点类对象
- Node1 node1 = new Node1("head", 1);
- Node1 node2 = new Node1("middle", 2);
- Node1 node3 = new Node1("last", 3);
- Node1 node4 = new Node1("lastOne", 4);
-
- //创建单链表对象
- SingleNode singleNode = new SingleNode();
- /* 尾插法
- singleNode.addLast(node1);
- singleNode.addLast(node2);
- singleNode.addLast(node3);
- singleNode.addLast(node4);
- singleNode.show();
- */
- /* 头插法
- singleNode.addHead(node1);
- singleNode.addHead(node2);
- singleNode.addHead(node3);
- singleNode.addHead(node4);*/
-
- //指定顺序插入节点
- Node1 order1 = new Node1("head1", 1);
- Node1 order2 = new Node1("middle2", 2);
- Node1 order3 = new Node1("last3", 3);
- Node1 order4 = new Node1("lastOne4", 4);
-
- singleNode.addByOrder(order4);
- singleNode.addByOrder(order2);
- singleNode.addByOrder(order3);
- singleNode.addByOrder(order1);
-
- singleNode.show();
- }
- }
-
- class SingleNode{
-
- //初始化头节点,不放任何数据
- private Node1 head = new Node1("",0);
-
- //尾插法
- //不管什么插入法,都需要把要插入的节点传入方法中
- public void addLast(Node1 node){
- //定义辅助变量来插入数据
- Node1 temp = head;
- //退出循环
- while (temp.next != null) {
- //遍历到单链表的尾部
- temp = temp.next;
- }
- //退出循环表示找到链表的最后一个节点,就在该节点插入传入的节点
- temp.next = node;
- }
-
- //判断单链表是否为null
- //单链表头插法
- public void addHead(Node1 node) {
- //如果链表为null,则把传入的第一个元素赋给head.next
- if (head.next == null){
- head.next = node;
- return;
- }
- //如果链表不为null,就定义一个temp来辅助插入节点
- Node1 temp = head.next;
- //把传入的节点插入单链表,注意两个步骤
- //1、head.next 指向 传入的节点
- //2、传入的节点.next 指向 temp
- head.next = node;
- node.next = temp;
- }
-
- //按照指定顺序插入节点
- public void addByOrder(Node1 node){
- //定义一个辅助变量temp
- Node1 temp = head;
- //定义一个标记,用来寻找 节点 要 插入的位置
- boolean flag = false;
- //遍历链表
- while (true) {
- //如果链表为null就退出循环
- if (temp.next == null) {
- //符合条件 退出循环
- break;
- }
- //比如我插入的节点的编号为4 (node.no==4),原来temp的后一个节点编号为5 (temp.next.no==5)
- //所以temp后一个节点的就不再指向编号为5的节点,而是指向编号为4的节点(也就是我当前插入的节点)
- // 5 > 4
- if (temp.next.no > node.no){
- //符合条件 退出循环
- break;
- }else if ( temp.next.no == node.no){
- flag = true; //说明编号已存在 ,不需要插入
- //继续循环遍历,直到找到合适的位置
- }
- temp = temp.next; //后移,相当于遍历当前链表
- }
- //判断flag的值
- //可以写成flag == true
- if (flag) { //不能插入
- System.out.println("该节点已存在");
- }else {
- //插入当前节点
- node.next = temp.next;
- temp.next = node;
- }
- }
-
- //遍历链表,输出链表
- public void show(){
- //判断链表为null
- if (head.next == null) {
- System.out.println("链表为null");
- return;
- }
- //注意这里的链表是不存放节点的,所以和add的方法的遍历有所不同
- Node1 temp = head.next;
- while (temp != null) {
- System.out.println(temp);
- temp = temp.next;
- }
- }
- }
-
- class Node1{
- //存放数据
- public String data;
- public int no;
-
-
- //指向当前节点的下一个节点,默认为null
- public Node1 next;
-
- public Node1(String data,int no) {
- this.data = data;
- this.no = no;
- }
-
- @Override
- public String toString() {
- return "Node{" +
- "name='" + data + '\'' +
- '}';
- }
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。