Java编程内功之怎么使用单链表
这篇文章将为大家详细讲解有关Java编程内功之怎么使用单链表，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。
淮阳网站制作公司哪家好，找成都创新互联公司！从网页设计、网站建设、微信开发、APP开发、成都响应式网站建设等网站项目制作，到程序开发，运营维护。成都创新互联公司于2013年创立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选成都创新互联公司。
基本介绍
链表是有序的列表,但是它在内存中存储如下
鸿蒙官方战略合作共建——HarmonyOS技术社区
链表是以节点的方式来存储.
每个节点包含data域,next域:指向下一个节点.
如图:发现每个链表的各个节点不一定是连续存储
链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定.
单链表介绍
单链表(带头节点)逻辑结构示意图如下
单链表的应用实例
使用带head头的单向链表实现-水浒英雄排行榜管理
package com.structures.linkedlist; public class SingleLinkedListDemo { public static void main(String[] args) { HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨"); HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星"); HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头"); SingleLinkedList singleLinkedList = new SingleLinkedList(); singleLinkedList.add(heroNode3); singleLinkedList.add(heroNode2); singleLinkedList.add(heroNode4); singleLinkedList.add(heroNode1); singleLinkedList.list(); } } //定义SingleLinkedList管理我们的英雄 class SingleLinkedList { //先初始化一个头节点,头节点不能动,将来遍历用 private HeroNode head = new HeroNode(0, "", ""); //添加节点到单向链表 //思路:当不考虑编号的顺序时 //1. 找到当前链表的最后节点 //2. 将最后这个节点的next域指向新的节点 public void add(HeroNode node) { //因为head节点不能动,因此我们需要一个辅助遍历temp HeroNode temp = head; //遍历链表,找到最后 while (temp.next != null) { //找到链表的最后 //如果没有找到temp就后移 temp = temp.next; } temp.next = node; } //显示链表[遍历] public void list() { //判断链表是否为空 if (head.next == null) { System.out.println("链表为空"); } //因为头节点不能动,因此我们需要一个辅助变量来遍历 HeroNode temp = head.next; while (temp != null) { //判断是否到最后 //输出节点的信息 System.out.println(temp); //将temp后移 temp = temp.next; } } } //定义一个HeroNode,每个HeroNode对象就是一个节点 class HeroNode { public int no; public String name; public String nickName; public HeroNode next;//指向下一个节点 //构造器 public HeroNode(int no, String name, String nickName) { this.no = no; this.name = name; this.nickName = nickName; } public HeroNode getNext() { return next; } public void setNext(HeroNode next) { this.next = next; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } } /* HeroNode{no=3, name='吴用', nickName='智多星'} HeroNode{no=2, name='卢俊义', nickName='玉麒麟'} HeroNode{no=4, name='林冲', nickName='豹子头'} HeroNode{no=1, name='宋江', nickName='及时雨'} */可以看到以上链表的实现方式,在添加英雄时,并未按照英雄的编号进行排序. 下面重新写一个添加方法,实现插入英雄时按编号排序
package com.structures.linkedlist; public class SingleLinkedListDemo { public static void main(String[] args) { HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨"); HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星"); HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头"); SingleLinkedList singleLinkedList = new SingleLinkedList(); singleLinkedList.addByNo(heroNode3); singleLinkedList.addByNo(heroNode2); singleLinkedList.addByNo(heroNode4); singleLinkedList.addByNo(heroNode1); singleLinkedList.list(); } } //定义SingleLinkedList管理我们的英雄 class SingleLinkedList { //先初始化一个头节点,头节点不能动,将来遍历用 private HeroNode head = new HeroNode(0, "", ""); //添加节点到单向链表 //思路:当不考虑编号的顺序时 //1. 找到当前链表的最后节点 //2. 将最后这个节点的next域指向新的节点 public void add(HeroNode node) { //因为head节点不能动,因此我们需要一个辅助遍历temp HeroNode temp = head; //遍历链表,找到最后 while (temp.next != null) { //找到链表的最后 //如果没有找到temp就后移 temp = temp.next; } temp.next = node; } //第二种添加英雄的方式,在添加英雄时,根据排名将英雄插入到指定位置 //如果有这个排名,则添加失败,并给出提示 public void addByNo(HeroNode heroNode) { //因为head节点不能动,因此我们需要一个辅助遍历temp //因为单链表,因此找的temp是位于添加位置的前一个节点,否则加入不了 HeroNode temp = head; boolean flag = false;//标识添加的编号是否存在,默认false while (true) { if (temp.next == null) { break; } if (temp.next.no > heroNode.no) {//位置找到,就在temp的后面插入 break; } else if (temp.next.no == heroNode.no) { //编号已存在 flag = true; break; } temp = temp.next; } if (flag) { System.out.printf("准备插入的英雄的编号 %d 已存在,不能加入\n", heroNode.no); } else { //插入链表temp的后面 heroNode.next = temp.next; temp.next = heroNode; } } //显示链表[遍历] public void list() { //判断链表是否为空 if (head.next == null) { System.out.println("链表为空"); } //因为头节点不能动,因此我们需要一个辅助变量来遍历 HeroNode temp = head.next; while (temp != null) { //判断是否到最后 //输出节点的信息 System.out.println(temp); //将temp后移 temp = temp.next; } } } //定义一个HeroNode,每个HeroNode对象就是一个节点 class HeroNode { public int no; public String name; public String nickName; public HeroNode next;//指向下一个节点 //构造器 public HeroNode(int no, String name, String nickName) { this.no = no; this.name = name; this.nickName = nickName; } public HeroNode getNext() { return next; } public void setNext(HeroNode next) { this.next = next; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } } /* HeroNode{no=1, name='宋江', nickName='及时雨'} HeroNode{no=2, name='卢俊义', nickName='玉麒麟'} HeroNode{no=3, name='吴用', nickName='智多星'} HeroNode{no=4, name='林冲', nickName='豹子头'} */再次进行完善功能,添加修改节点功能
//修改节点的信息,根据no编号来修改,即编号no不能修改. public void update(HeroNode heroNode) { //判断是否为空 if (head.next == null) { System.out.println("链表为空"); } //找到需要修改的节点,根据no编号 HeroNode temp = head.next; boolean flag = false;//表示节点是否找到 while (true) { if (temp == null) { break; } if (temp.no == heroNode.no) { flag = true; break; } temp = temp.next; } if (flag) { temp.name = heroNode.name; temp.nickName = heroNode.nickName; } else { System.out.printf("没有找到 编号%d 的节点,不能修改\n", heroNode.no); } }再次进行完善功能,添加删除节点功能
//删除节点 public void remove(HeroNode heroNode) { //判断是否为空 if (head.next == null) { System.out.println("链表为空"); } HeroNode temp = head.next; boolean flag = false;//标识是否找到待删除的点 while (true) { if (temp == null) { break; } if (temp.next.no == heroNode.no) { flag = true; break; } temp = temp.next; } if (flag) { temp.next = temp.next.next; } else { System.out.printf("无法删除 编号%d 的节点,\n", heroNode.no); } }再次进行完善功能,添加统计单链表的有效节点数功能
/** * 获取单链表的有效节点数,不统计头节点 * @param head 链表的头结点 * @return 有效节点数 */ public static int getLength(HeroNode head) { if (head.next == null) { return 0; } int count = 0; HeroNode temp = head.next; while (temp.next != null) { count++; temp = temp.next; } return count; }再次进行完善功能,添加查找单链表中的倒数第K个节点功能
/** * 查找单链表的倒数第K个节点[新浪面试题] * 思路: * 1.先把链表从头到尾遍历,得到链表的总长度 * 2.得到size后,从链表的第一个开始遍历到(size-index)个,就可以得到 * * @param head * @param index 表示倒数第index个节点 * @return */ public static HeroNode findLastIndexNode(HeroNode head, int index) { if (head.next == null) { return null; } int size = getLength(head); if (index <= 0 || index > size) { return null; } HeroNode temp = head.next; for (int i = 0; i < (size - index); i++) { temp = temp.next; } return temp; }再次进行完善功能,添加单链表反转功能
/** * 反转链表[腾讯面试题] * 思路: * 1.先定义一个reverseHead = new HeroHead(); * 2.从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表的最前端; * 3.原来的链表的head.next = reverseHead.next; */ public static void reverseList(HeroNode head) { if (head.next == null || head.next.next == null) { return; } HeroNode curr = head.next; HeroNode next = null;//指向当前节点[curr]的下一个节点 HeroNode reverseHead = new HeroNode(0, "", ""); while (curr != null) { next = curr.next;//先暂时保存curr节点的下一个节点 curr.next = reverseHead.next;//将curr的下一个节点指向新的链表的最前端 reverseHead.next = curr;//将curr连接到新的链表上 curr = next;//让curr后移 } head.next = reverseHead.next; }再次进行完善功能,添加从尾到头打印单链表功能
/** * 使用栈的方式逆序打印[百度面试题] */ public static void reversePrint(HeroNode head) { if (head.next == null) { return; } Stack heroNodes = new Stack(); HeroNode temp = head.next; while (temp != null) { heroNodes.add(temp); temp = temp.next; } while (heroNodes.size() > 0) { System.out.println(heroNodes.pop()); } } 关于Java编程内功之怎么使用单链表就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
分享文章：Java编程内功之怎么使用单链表
文章出自：http://ybzwz.com/article/ghogii.html
