Java数据结构：单链表的实现与面试题汇总（带头节点与不带头节点的两种方式的链表实现）
·
文章目录
1 单链表
1.1 单链表介绍
由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它 不要求在逻辑上相邻的两个元素在物理位置上也相邻。
物理结构示意图：
逻辑结构示意图：
关于单链表的一些说明：
- 链表是以节点的方式存储的，每个节点包含data和next域，分别表示存储的数据和指向下一个节点；
- 链表的各个节点不一定是连续存储的；
- 可以根据实际需求来构造是否带有头节点的链表。
1.2 单链表的实现思路分析
1.2.1 单链表的创建与遍历
单链表的创建：
- 先创建一个 head 头节点，表示单链表的头；
- 每添加一个节点就直接加入链表的最后；
遍历的思路：
- 创建一个辅助指针，用于帮助遍历整个链表；
- 当指针指向的节点的next域为null，说明当前节点为最后一个，遍历完成。
1.2.2 单链表节点的插入与修改
示意图如下：
- 首先需要通过遍历找到需要添加节点的位置，图中示意的为a1的位置；
- 新的节点的next指向a1.next；
- 将该位置，即a1.next指向新的节点。
修改操作相当于上述过程的简化，只需要找到对应的节点直接修改节点对应的属性即可，这里不再赘述。
1.2.3 单链表节点的删除
删除序号为 “2” 的节点示意图如下：
思路如下：
- 找到待删除节点的前一个节点，示例中则找到序号为1的节点；
- 让该节点的 temp.next = temp.next.next，即可；
- 由于被删除的节点没有其他的指向，则会由Java的垃圾回收机制进行回收，无需处理。
1.3 实现代码
StudentNode.java 节点类：
/**
* @author 兴趣使然黄小黄
* @version 1.0
* 链表的节点类，包含学生信息和next
*/
public class StudentNode {
public String no; //学号
public String name; //姓名
public int age; //年龄
public StudentNode next; //指向下一个节点
//构造器
public StudentNode(String no, String name, int age ){
this.no = no;
this.name = name;
this.age = age;
}
//为了显示方便
@Override
public String toString() {
return "StudentNode{" +
"no='" + no + '\'' +
", name='" + name + '\'' +
", age=" + age +
'}';
}
}
StudentLinkedList.java 链表的实现类：
/**
* @author 兴趣使然黄小黄
* @version 1.0
* 链表的实现类，用于管理众多StudentNode节点
*/
public class StudentLinkedList {
//初始化头节点
private StudentNode head = new StudentNode("", "", 0);
//获取头节点
public StudentNode getHead() {
return head;
}
//添加节点
//1.找到当前链表的最后节点
//2.将最后节点的next指向新的节点
public void add(StudentNode studentNode) {
StudentNode temp = head;
//遍历链表找到最后的节点
while (temp.next != null) {
//没有找到，就后移
temp = temp.next;
}
//最后的节点的next指向新节点
temp.next = studentNode;
}
//遍历 显示链表
public void showList(){
//判断链表是否为空
if (head.next == null){
System.out.println("当前链表为空");
return;
}
//遍历 使用辅助指针
StudentNode temp = head;
while (temp != null){
//更新指针
temp = temp.next;
if (temp.next == null){
System.out.print(temp);
break;
}
System.out.print(temp + "--->");
}
}
//插入节点
//根据学号顺序查找添加的位置, 如果存在, 则提示错误信息
public void addByOrder(StudentNode studentNode){
//寻找的temp应该为添加位置的前一个节点
StudentNode temp = head;
boolean flag = false; //标识新添加的no是否已经存在
while (true){
if (temp.next == null){
//已经在链表的尾部
break;
}
if (Integer.parseInt(temp.next.no) > Integer.parseInt(studentNode.no)){
//位置找到 插入到temp后
break;
}else if (Integer.parseInt(temp.next.no) == Integer.parseInt(studentNode.no)){
//已经存在
flag = true;
break;
}
//移动指针
temp = temp.next;
}
if (flag){
System.out.println("\n准备插入的学生信息: " + studentNode.no + "，该学号已经存在，不可添加！");
}else {
studentNode.next = temp.next;
temp.next = studentNode;
}
}
//根据no学号修改学生信息
public void update(StudentNode studentNode){
if (head.next == null){
System.out.println("当前链表为空, 无法修改");
return;
}
StudentNode temp = head.next;
boolean flag = false; //表示是否找到节点
while (true){
if (temp == null){
break;
}
if (temp.no == studentNode.no){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
temp.name = studentNode.name;
temp.age = studentNode.age;
}else {
System.out.println("没有找到");
}
}
//删除节点
public void delete(String no){
StudentNode temp = head;
boolean flag = false; //标志是否找到
//查找到待删除节点的前一个节点进行删除操作
while (true){
if (temp.next == null){
//到达尾部
break;
}
if (temp.next.no == no){
//找到了
flag = true;
break;
}
//遍历
temp = temp.next;
}
//删除操作
if (flag){
temp.next = temp.next.next;
System.out.println("删除成功！");
}else {
System.out.println("要删除的节点不存在！");
}
}
}
测试类：
/**
* @author 兴趣使然黄小黄
* @version 1.0
* 测试链表
*/
public class StudentListTest {
public static void main(String[] args) {
StudentNode node1 = new StudentNode("1", "黄小黄", 21);
StudentNode node2 = new StudentNode("2", "懒羊羊", 21);
StudentNode node3 = new StudentNode("3", "沸羊羊", 22);
//创建单链表 录入数据 输出
StudentLinkedList list = new StudentLinkedList();
list.add(node1);
list.add(node2);
list.add(node3);
System.out.println("遍历链表:");
list.showList();
//测试插入数据方法
StudentNode node5 = new StudentNode("5", "美羊羊", 19);
StudentNode node4 = new StudentNode("4", "暖羊羊", 19);
list.addByOrder(node5);
list.addByOrder(node4);
System.out.println("\n依次插入学号为5、4的学生后:");
list.showList();
//测试修改方法
System.out.println("\n测试修改方法:");
list.update(new StudentNode("1", "祢豆子", 10));
list.showList();
//测试删除方法
System.out.println("\n测试删除方法:");
list.delete("1");
list.delete("5");
list.showList();
}
}
实现结果：
遍历链表:
StudentNode{no='1', name='黄小黄', age=21}--->StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}
依次插入学号为5、4的学生后:
StudentNode{no='1', name='黄小黄', age=21}--->StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}--->StudentNode{no='5', name='美羊羊', age=19}
测试修改方法:
StudentNode{no='1', name='祢豆子', age=10}--->StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}--->StudentNode{no='5', name='美羊羊', age=19}
测试删除方法:
删除成功！
删除成功！
StudentNode{no='2', name='懒羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}
Process finished with exit code 0
2 单链表的面试题
2.1 统计单链表中有效节点数量
/**
*
* @param head 头节点
* @return 返回有效节点个数
*/
public static int getLength(StudentNode head){
if (head.next == null){
return 0;
}
int length = 0;
StudentNode temp = head.next;
while (temp != null){
length++;
temp = temp.next;
}
return length;
}
2.2 新浪–倒数第k个节点
查找链表中倒数第k个节点
思路分析：
- 编写一个方法，接收head头节点和index，index表示k；
- 链表从头到尾遍历，求出长度（链表节点个数）size；
- 从第一个节点，遍历size-length次，即可找到倒数第k个节点。
参考代码：
/**
* 获取单链表中倒数第k个节点
* @param head 链表的头节点
* @param index 倒数第 k 个元素
* @return 返回倒数第 k 个元素，或者 null
*/
public static StudentNode findLastIndexNode(StudentNode head, int index){
//如果链表为空
if (head.next == null){
return null;
}
//得到链表的长度(节点个数)
int size = getLength(head);
//遍历 size-index次 得到倒数第index个节点
//数据校验
if (index <= 0 || index > size){
return null;
}
//遍历
StudentNode current = head.next;
for (int i = 0; i < size - index; i++) {
current = current.next;
}
return current;
}
2.3 腾讯–单链表的反转
反转单链表
思路分析：
- 可以使用头插法；
- 以原链表为模板，每遍历一个节点，取出，并接在新链表的最前端；
- 原head头节点，指向新的节点；
- 直到遍历完为止。
参考代码：
/**
* 头插法反转链表
* @param head 接收待反转的链表
* @return 返回一个反转后的新链表
*/
public static StudentLinkedList reverseList(StudentNode head){
if (head.next == null){
return null;
}
StudentNode old = head.next; //用于遍历旧链表
//创建新链表，新链表根据原链表遍历得到
StudentLinkedList newList = new StudentLinkedList();
StudentNode newHead = newList.getHead(); //新链表的头节点
//遍历构造
boolean flag = true; //标记是否为第一次添加
while (old != null){
//头插法加入到新链表中
StudentNode newNode = new StudentNode(old.no, old.name, old.age);
if(flag){
newHead.next = newNode;
newNode.next = null;
flag = false;
}else {
newNode.next = newHead.next;
newHead.next = newNode;
}
old = old.next;
}
return newList;
}
以上方式虽然可以实现链表的反转，但是是以返回一个新的反转链表的形式，并没有真正意义上实现原地反转，下面介绍另一种方式：
双指针:
/**
* 双指针就地反转链表
* @param head 接收链表的头节点，方法中会将链表反转
*/
public static void reverse(StudentNode head){
//如果当前链表为空 或者只有一个节点 直接返回即可
if (head.next == null || head.next.next == null){
return;
}
//辅助指针遍历原来的链表
StudentNode cur = head.next; //当前节点
StudentNode next = null; //指向cur的下一个节点
StudentNode reverseHead = new StudentNode("", "", 0);
//遍历原来的链表，每遍历一个节点，就取出，放在新链表的最前端
while (cur != null){
next = cur.next; //暂时保存当前节点的下一个节点
cur.next = reverseHead.next; //讲cur下一个节点放在链表最前端
reverseHead.next = cur;
cur = next; //cur后移动
}
head.next = reverseHead.next;
return;
}
2.4 百度–逆序打印单链表
从尾到头打印单链表
方式一： 先将单链表反转，然后再打印。但是这样会破坏掉原有单链表的结构，而题目要求仅仅是打印，因此不建议！
方式二： 利用栈模拟
将单链表的各个节点压入栈中，利用栈先进后出的特点，实现逆序打印。
参考代码：
/**
* 利用栈模拟 实现链表的逆序打印
* @param head 链表的头节点
*/
public static void reversePrintList(StudentNode head){
if (head.next == null){
return; //空链表无法打印
}
//创建栈模拟逆序打印
Stack<StudentNode> stack = new Stack<>(); //栈
StudentNode cur = head.next;
//将链表的所有节点压入栈
while (cur != null){
stack.push(cur);
cur = cur.next;
}
//逆序打印
while (!stack.empty()){
//出栈
System.out.println(stack.pop());
}
return;
}
3 *不带头节点的单链表实现
3.1 完整代码
ListIndexOutOfException
自定义异常类
/**
* @author 兴趣使然黄小黄
* @version 1.0
* 链表越界异常
*/
public class ListIndexOutOfException extends RuntimeException {
public ListIndexOutOfException(String message) {
super(message);
}
}
MyLinkedList
使用泛型实现
/**
* @author 兴趣使然黄小黄
* @version 1.0
* 不带头节点的单向链表
*/
@SuppressWarnings({"all"})
public class MyLinkedList<T> {
public Node head; // 指向链表的头
class Node<T>{
public T val; // 存储的数据
public Node next; // 存储下一个节点的地址
public Node(T val) {
this.val = val;
}
}
/**
* 遍历链表
*/
public void display(){
Node<T> cur = head; // 辅助指针
while (cur != null){
if (cur.next == null){
System.out.println(cur.val);
}else {
System.out.print(cur.val + "->");
}
cur = cur.next;
}
}
/**
* 查看链表是否包含key
* @param key 查询的值
* @return
*/
public boolean contains(T key){
Node<T> cur = head;
while (cur != null){
if (cur.val.equals(key)){
return true;
}
cur = cur.next;
}
return false;
}
/**
* 查看链表的长度
* @return 链表的长度
* 时间复杂度O(n),如果属性中存储长度,则只需要每次添加和删除的时候size++,时间复杂度O(1)
*/
public int size(){
int count = 0;
Node<T> cur = head;
while (cur != null){
count++;
cur = cur.next;
}
return count;
}
/**
* 头插法
* @param data 插入的节点数据
*/
public void addHead(T data){
Node<T> newNode = new Node<>(data);
newNode.next = head;
head = newNode;
}
/**
* 尾插法
* @param data 插入的节点数据
*/
public void add(T data){
Node<T> newNode = new Node<>(data);
if(head == null){
head = newNode;
}else {
Node<T> cur = head;
while (cur.next != null){
cur = cur.next;
}
cur.next = newNode;
}
}
/**
* 清空链表
*/
public void clear(){
head = null;
}
/**
* 在指定位置处插入节点，第一个位置为0下标
* @param index 指定位置
* @param data 插入的节点
*/
public void insertByIndex(int index, T data){
if (index < 0 || index > size()){
throw new ListIndexOutOfException("index位置不合法！");
}
Node<T> cur = head;
Node<T> newNode = new Node<>(data);
if (index == 0){
addHead(data);
return;
}
if (index == size()){
add(data);
return;
}
while (cur.next != null && index-1 != 0){
--index;
cur = cur.next;
}
newNode.next = cur.next;
cur.next = newNode;
}
/**
* 根据key删除，删除第一个出现的key
* @param key
*/
public void remove(T key){
//判断链表是否为空
if (head == null){
System.out.println("当前链表为空，无法删除！");
return;
}
// 如果要删的是第一个节点
if (head.val.equals(key)){
head = head.next;
return;
}
Node<T> cur = head;
while (cur != null && !cur.next.val.equals(key)){
cur = cur.next;
}
if (cur == null){
System.out.println("待删除的元素不存在，无法删除！");
return;
}
// 常规情况
cur.next = cur.next.next;
}
/**
* 删除所有的key
* @param key
*/
public void removeAll(T key){
// 判空
if (head == null){
return;
}
// 使用双指针法删除
Node<T> pre = head;
Node<T> cur = head.next;
while (cur != null){
if(cur.val == key){
pre.next = cur.next;
}else {
pre = cur;
}
cur = cur.next;
}
// 处理第一个元素
if (head.val == key){
head = head.next;
}
}
}
3.2 测试
public class Main {
public static void main(String[] args) {
MyLinkedList<Integer> myList = new MyLinkedList<>();
System.out.println("==========测试尾插法=========");
myList.add(1);
myList.add(2);
myList.add(3);
myList.add(4);
myList.display();
myList.clear();
System.out.println("==========测试头插法=========");
myList.addHead(1);
myList.addHead(2);
myList.addHead(3);
myList.addHead(4);
myList.display();
System.out.println("在第4个位置处插入99");
myList.insertByIndex(4, 99);
myList.display();
System.out.println("在第0个位置处插入100");
myList.insertByIndex(0, 100);
myList.display();
System.out.println("==========测试删除=========");
System.out.println("删除第一个100：");
myList.remove(100);
myList.display();
System.out.println("删除第一个99：");
myList.remove(99);
myList.display();
System.out.println("插入一个4");
myList.add(4);
myList.display();
System.out.println("删除所有的4");
myList.removeAll(4);
myList.display();
}
}
写在最后
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
37
0- 0
已为社区贡献5条内容
所有评论(0)