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 节点类：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | /** * @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 链表的实现类：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | /** * @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("要删除的节点不存在！"); } }} |
测试类：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | /** * @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 统计单链表中有效节点数量
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | /** * * @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个节点。
参考代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | /** * 获取单链表中倒数第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 size){ return null; } //遍历 StudentNode current = head.next; for (int i = 0; i |
2.3 腾讯–单链表的反转
反转单链表
思路分析：
- 可以使用头插法；
- 以原链表为模板，每遍历一个节点，取出，并接在新链表的最前端；
- 原head头节点，指向新的节点；
- 直到遍历完为止。
参考代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | /** * 头插法反转链表 * @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;} |
以上方式虽然可以实现链表的反转，但是是以返回一个新的反转链表的形式，并没有真正意义上实现原地反转，下面介绍另一种方式：
双指针:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | /** * 双指针就地反转链表 * @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 百度–逆序打印单链表
从尾到头打印单链表
方式一： 先将单链表反转，然后再打印。但是这样会破坏掉原有单链表的结构，而题目要求仅仅是打印，因此不建议！
方式二： 利用栈模拟
将单链表的各个节点压入栈中，利用栈先进后出的特点，实现逆序打印。
参考代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | /** * 利用栈模拟 实现链表的逆序打印 * @param head 链表的头节点 */public static void reversePrintList(StudentNode head){ if (head.next == null){ return; //空链表无法打印 } //创建栈模拟逆序打印 Stack 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单链表的资料请关注IT俱乐部其它相关文章！
