Java-单向链表-从实现到各类操作(全家桶,包含各类常见方法)

版权声明:署名,允许他人基于本文进行创作,且必须基于与原先许可协议相同的许可协议分发本文 (Creative Commons

代码:

package com.lixunhuan.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
public static void main(String[] args) {
    /**
     * 测试步骤:
     * 1)先创建几个节点
     * 2)创建一个链表
     * 3)节点连入链表中
     */

    HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    HeroNode hero4 = new HeroNode(4, "公孙胜", "入云龙");

    SingleLinkedList singleLinkedList = new SingleLinkedList();
    //测试增加节点的方法
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);
//        singleLinkedList.add(hero2);
    //测试 按序增加节点的方法
    singleLinkedList.addByOrder(hero1);
    singleLinkedList.addByOrder(hero3);
    singleLinkedList.addByOrder(hero4);
    singleLinkedList.addByOrder(hero2);
    singleLinkedList.addByOrder(hero2);//重复 会给出提示。
    singleLinkedList.list();
    System.out.println("*********************************************************");
    //测试修改节点的代码
    HeroNode newHeroNode = new HeroNode(2, "卢指导", "鲈鱼");
    singleLinkedList.update(newHeroNode);
    singleLinkedList.list();
    //测试删除指定节点的方法 测试了1,2,3,4,5均经过了考核
    System.out.println("*********************************************************");
    singleLinkedList.delete(4);
    singleLinkedList.list();
    System.out.println("++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
    System.out.println(singleLinkedList.getLength(singleLinkedList.getHead()));
    System.out.println(singleLinkedList.findLastIndexNode(singleLinkedList.getHead(), 1).name);
    //测试单向链表逆序
    singleLinkedList.reverseList(singleLinkedList.getHead());
    singleLinkedList.list();
    //测试逆序打印(原链表不逆序)
    singleLinkedList.reversePrint(singleLinkedList.getHead());
}
}

/**
 * 定义一个SingleLinkedList
 */
class TestMergeList {
public static void main(String[] args) {
    HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    HeroNode hero4 = new HeroNode(4, "公孙胜", "入云龙");
    HeroNode hero6 = new HeroNode(6, "林冲", "豹子头");

    SingleLinkedList singleLinkedList1 = new SingleLinkedList();
    SingleLinkedList singleLinkedList2 = new SingleLinkedList();
    singleLinkedList1.addByOrder(hero2);
    singleLinkedList1.addByOrder(hero4);
    singleLinkedList2.addByOrder(hero1);
    singleLinkedList2.addByOrder(hero3);
    singleLinkedList2.addByOrder(hero6);
    singleLinkedList1.list();
    System.out.println("--------------------分隔符1----------------------");
    singleLinkedList2.list();
    SingleLinkedList singleLinkedList3 = new SingleLinkedList();
    singleLinkedList3.mergeList(singleLinkedList1.getHead(), singleLinkedList2.getHead());
    System.out.println("--------------------分隔符2----------------------");
    singleLinkedList3.list();

}
}

class SingleLinkedList {
//先初始化一个头节点,头节点不能动,也不存放数据
private HeroNode head = new HeroNode(0, null, null);

public HeroNode getHead() {
    return head;
}

//编写添加新节点的方法。
// 不考虑英雄排名的思路:1)找到当前链表最后一个元素 2)使其next节点指向当前节点

public void add(HeroNode heroNode) {
    //因为头节点不能动,所以我们需要一个辅助遍历来遍历链表找到最后节点
    HeroNode temp = head;
    //while循环用来找到当前链表的尾部
    while (temp.next != null) {
        temp = temp.next;
    }
    //是最后节点指向新增节点
    temp.next = heroNode;
}

//考虑到排序的增加元素方法
public void addByOrder(HeroNode heroNode) {
    //因为头节点不能动,我们这里依然通过一个辅助变量来找到添加的位置
    //又由于是单向链表,所以temp是要位于添加位置的前一个节点,这样才插入合法
    HeroNode temp = head;
    boolean flag = false; // 标识添加的英雄是否则在,默认为false

    while (temp.next != null) {
        //虽然是单向链表,但是依据当前节点是可以写出下面任何一个位置的节点的相关属性,
        //比如temp.next.next.next.no
        if (temp.next.no > heroNode.no) {
            break;
        } else if (temp.next.no == heroNode.no) {
            flag = true;
            break;
        } else {
            temp = temp.next;
        }
    }
    if (flag) {
        System.out.printf("英雄:%d不要重复添加英雄\n", heroNode.no);
    } else {
        heroNode.next = temp.next;
        temp.next = heroNode;
    }
}

/**
 * 修改节点的信息,根据no编号来修改,即no编号不能改
 * 说明:
 * 1. 根据newHeroNode 的 no来修改
 * 2.默认链表未排序
 */

public void update(HeroNode newHeroNode) {
    //判断是否为空
    if (head.next == null) {
        System.out.println("链表为空!");
    } else {//找到需要修改的节点
        //先定义一个辅助变量
        HeroNode temp = head.next;
        boolean flag = false;//表示是否找到该节点,默认为false
        while (temp != null) {
            if (temp.no == newHeroNode.no) {
                //找到了
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag来判断是否找到要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            System.out.printf("没有找到编号为:%d\n", newHeroNode.no);
        }
    }
}

/**
 * 删除节点的方法编写
 * 默认链表未排序
 * 根据排序no来进行英雄删除
 * 删除要查找的节点不再是对应no编号的节点,而是要找到其上一个节点,和修改不一样
 */
public void delete(int no) {
    //1)判断链表是否为空
    if (head.next == null) {
        System.out.println("是空链表,无英雄");
        return;
    }
    //2)创建临时指针进行链表的遍历、查找
    HeroNode temp = head;
    boolean flag = false;//用于记录是否已找到指定英雄

    while (temp.next != null) {
        if (temp.next.no == no) {
            flag = true;//表示找到了
            break;
        } else if (temp.no == no) {
            flag = true;
            break;
        } else {
            temp = temp.next;
        }
    }
    if (flag) {
        temp.next = temp.next.next;
    } else {
        System.out.printf("未找到编号为:%d节点!\n", no);
    }
}

/**
 * 编写 遍历显示链表的方法
 */
public void list() {
    if (head.next == null) {
        System.out.println("链表为空!");
    } else {
        //因为头节点不能动,所以我们需要一个辅助遍历来遍历链表
        HeroNode temp = head.next;//这次遍历的时候可不需要头节点了,因为头节点不存有效数据
        while (temp != null) {
            System.out.println(temp);//即调用了重写的System.out.println(temp.toString());
            temp = temp.next;
        }
    }
}

/**
 * 编写得到链表长度的方法
 * 传入一个头节点(但不将其计入有效节点个数统计)
 */

public int getLength(HeroNode head) {
    if (head.next == null || head == null) {
        return 0;
    }
    int length = 0;
    HeroNode cur = head.next;
    while (cur != null) {
        length++;
        cur = cur.next;
    }
    return length;
}

/**
 * 查找单链表中的倒数第K个节点【新浪面试题】
 * 接收:head节点,index(倒数第index个节点)
 * 返回:找到则返回对应节点,没找到则返回null
 * 思路:受于单向链表限制,1)先遍历链表得到链表长度,2)然后得到正向看过去的节点数
 * 具体计算请见代码
 */
public HeroNode findLastIndexNode(HeroNode head, int index) {
    if (index <= 0)
        throw new RuntimeException("数组索引不合法\n");
    if (head == null || head.next == null) {
        return null;
    }
    int length = this.getLength(head);
    if (length < index)
        throw new RuntimeException("数组索引超出范围\n");
    int cishu = length - index;
    HeroNode cur = head.next;
    for (int i = 0; i < cishu; i++) {
        cur = cur.next;
    }
    return cur;
}

/**
 * 将单链表进行反转的方法
 */
public void reverseList(HeroNode head) {
    //先判断链表是否为空,是否只有一个节点,那么就无需反转,直接返回
    if (head.next == null || head.next.next == null)
        return;

    HeroNode cur = head.next;//定义一个辅助的指针,帮助遍历
    HeroNode next = null; //用于记录当前节点下一个节点
    HeroNode reverseHead = new HeroNode(0, "", "");

    //遍历原来的链表,并从头开始遍历原来链表,每遍历一个节点,就将其取出,并放在新链表最前端(reverseHead.next处)
    while (cur != null) {
        next = cur.next;
        cur.next = reverseHead.next;
        reverseHead.next = cur;
        cur = next;
    }
    head.next = reverseHead.next;//这一步很关键,头部和反转头部的交接工作!别落下!
}

/**
 * 反序输出一个单向链表的方法,且原链表结构保持不变
 *
 * @param head
 */
public void reversePrint(HeroNode head) {
    if (head.next == null)
        return;
    //创建一个栈,将各个节点压入栈中
    Stack<HeroNode> stack = new Stack<>();
    HeroNode cur = head.next;
    //将链表的所有节点压入
    // 栈中
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;//这样就可以压入下一个节点
    }
    //将栈中的节点进行打印

    while (stack.size() > 0) {
        System.out.println(stack.pop());
    }
}

/**
 * 连接两个有序单向链表的方法
 * 排序依据:将的 no序号进行升序排序 (当然,原本要合并的序列也是这样排好序的)
 */
public void mergeList(HeroNode head1, HeroNode head2) {
    if (head1.next == null) {
        System.out.println("无需合并");
        head = head2;
    }
    if (head2.next == null) {
        System.out.println("无需合并");
        head = head1;
    }
    HeroNode cur1 = head1.next;
    HeroNode cur2 = head2.next;
    HeroNode mergeHead = new HeroNode(0, "", "");//头是不能变的,即不能再次被赋值
    HeroNode mergeCur = mergeHead;
    while (cur1 != null && cur2 != null) {
        if (cur1.no < cur2.no) {
            mergeCur.next = cur1;
            cur1 = cur1.next;//队列向后移动一个节点
            mergeCur=mergeCur.next;//新链表
        } else if (cur1.no == cur2.no) {
            mergeCur.next = cur1;
            cur1 = cur1.next;
            cur2 = cur2.next;
            mergeCur=mergeCur.next;
        } else {
            mergeCur.next = cur2;
            cur2 = cur2.next;
            mergeCur=mergeCur.next;
        }
    }
    if (cur1 == null && cur2 != null) {
        mergeCur.next = cur2;
    }
    if (cur2 == null && cur1 != null) {
        mergeCur.next = cur1;
    }
    head = mergeHead;
}
}
/**
* 定义一个将节点
*/
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next;//指向下一个节点

//构造器,注意单向链表新增节点的时候,其是不知道下一个节点的指向的,要么不管,要么赋值null

public HeroNode(int no, String name, String nickname) {
    this.no = no;
    this.name = name;
    this.nickname = nickname;
    this.next = null;
}

//为了显示方便 重写toString方法

@Override
public String toString() {
    return "HeroNode{" +
            "no=" + no +
            ", name='" + name + '\'' +
            ", nickname='" + nickname + '\'' +
            '}';
}
}

解释:

  1. 本例以水浒108将为例,heroNode为一个水浒英雄的相关类定义,包括:将排名、将名、将昵称、下一个节点地址
  2. SingleLinkedList类则定理了以上述节点为单位的单向链表
  3. SingleLinkedListDemo中测试了单向链表的增加节点(add())、有序增加节点(addByOrder())、修改节点属性(update())、删除对应节点(delete())、遍历显示节点属性(list()),得到除了头节点以外的有效节点个数(getLength())、查询单向两边倒数第n个元素的方法(findLastIndexNode(n))、反转链表方法(reverseList())、反转输出链表节点但是不改变原链表构造的方法(reversePrint())、俩有序单向链表合并(mergeList()的方法)
  4. 俩有序单向链表合并(mergeList()的方法)在TestMergeList类中的主函数实现

注意事项:

  • 遍历改变节点指向时,需要达成的关键步骤是遍历临时节点指向当前要操作的节点(改变其next指向),并使临时节点.next=新节点;不要:"ListNode curNewNode =head.next;curNewNode=curNode;"这样只会白费力气,因为不影响next的值;

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习与python

Python 谱聚类算法从零开始

谱聚类算法是一种常用的无监督机器学习算法,其性能优于其他聚类方法。 此外,谱聚类实现起来非常简单,并且可以通过标准线性代数方法有效地求解。 在谱聚类算法中,根据...

25020
来自专栏测试游记

ARTS打卡(第一周)

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

11650
来自专栏完美Excel

Python学习笔记:命名空间和作用域

在Python中,任何“东西”都是一个对象。当我们赋值整数给变量时,例如x = 1,我们告诉Python在引用x时,意味着Python指向整数类型对象1,以便对...

8340
来自专栏测试游记

Git基础知识(六)

因为是主线上的bug,所以先切回到主线上去,不过本地的主线可能有点旧了,所以把本地的master分支删掉,然后和远端同步一下之后再从远端把master分支检出

5230
来自专栏IT可乐

Java虚拟机详解(三)------垃圾回收

  如果对C++这门语言熟悉的人,再来看Java,就会发现这两者对垃圾(内存)回收的策略有很大的不同。

9420
来自专栏测试游记

Git基础知识(二)

可以使用 git status -s 命令或 git status --short 命令,得到一种更为紧凑的格式输出。

12730
来自专栏测试游记

Git通过变基将提交变得更美观

通过git log --graph我们可以看到,之前是三个提交的,现在前面两个提交已经合为了一个

19240
来自专栏完美Excel

Excel VBA解读(146): 使用隐式交集处理整列

Excel有一个有趣且非常有效的技巧叫做隐式交集(Implicit Intersection),允许有效地使用大的命名区域和整列引用。

13230
来自专栏安富莱嵌入式技术分享

【STM32H7教程】第29章 STM32H7的USART串口基础知识和HAL库API

完整教程下载地址:http://forum.armfly.com/forum.php?mod=viewthread&tid=86980

30740
来自专栏完美Excel

VBA实用小程序48: 确保工作簿已装载必需的外部加载宏

如果你的Excel应用程序依赖于外部加载项(例如分析工具库或规划求解加载项),那么必须确保在运行应用程序之前加载了该加载项。

7230

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励