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 节点类：
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 链表的实现类：
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("要删除的节点不存在！");
}
}
}
测试类：
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 统计单链表中有效节点数量
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个节点。
参考代码：
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头节点，指向新的节点；
- 直到遍历完为止。
参考代码：
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;
}
以上方式虽然可以实现链表的反转，但是是以返回一个新的反转链表的形式，并没有真正意义上实现原地反转，下面介绍另一种方式：
双指针:
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 百度–逆序打印单链表
从尾到头打印单链表
方式一： 先将单链表反转，然后再打印。但是这样会破坏掉原有单链表的结构，而题目要求仅仅是打印，因此不建议！
方式二： 利用栈模拟
将单链表的各个节点压入栈中，利用栈先进后出的特点，实现逆序打印。
参考代码：
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;
}
以上就是Java数据结构之单链表的实现与面试题汇总的详细内容，更多关于Java单链表的资料请关注其它相关文章！
相关文章