Java数据结构之单链表的实现与面试题汇总
目录
- 1 单链表
- 1.1 单链表介绍
- 1.2 单链表的实现思路分析
- 1.3 实现代码
- 2 单链表的面试题
- 2.1 统计单链表中有效节点数量
- 2.2 新浪–倒数第k个节点
- 2.3 腾讯–单链表的反转
- 2.4 百度–逆序打印单链表
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; }
以上就是Java数据结构之单链表的实现与面试题汇总的详细内容,更多关于Java单链表的资料请关注我们其它相关文章!