什么是链表？
1，链表是以节点的方式存储的，链式存储
2，每个节点包含data域，next域指向下一个节点
3，链表的各个节点不一定是链式存储的
4，链表分带头节点的链表和不带头结点的链表
下面用代码实现一个单向链表
首先定义一个类用来存储到链表中
/** * 定义HeroNode，每个HeroNode对象就是一个节点 */ public 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; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } }
链表实现类
/** * 定义SingleLinkedList管理我们的英雄 */ public class SingleLinkedList { //初始化一个头节点，头结点不动，不存放任何数据 public HeroNode head = new HeroNode(0, "", ""); /** * 添加节点到单向链表 * 当不考虑编号顺序时 * 1，找到当前链表的最后节点 * 2，将最后这个节点的next指向新的节点 * * @param heroNode */ public void add(HeroNode heroNode) { //因为头结点不能动，因此我们需要一个辅助遍历的temp HeroNode temp = head; //遍历链表，找到最后的节点 while (true) { //如果指向下一个链表是null 就是最后一个 if (temp.next == null) { break; } //如果不是空 就是还没到最后一个，将temp后移 temp = temp.next; } //当退出while循环时，temp就指向了链表的最后 //将最后这个节点的next指向新的节点即可 temp.next = heroNode; } //第二种插入方式在添加英雄时，根据排名将英雄输入到指定位置 public void addByOrder(HeroNode heroNode) { //使用辅助变量 //我们找的temp是位于添加位置的前一个节点 HeroNode temp = head; boolean flag = false;//如果要添加的编号已存在flag就变成true while (true) { if (temp.next == null) {//说明已经到了链表的最后 break; } if (temp.next.no > heroNode.no) {//如果temp的下一个节点的编号大于要插入节点的编号，位置找到，在temp的后面插入 break; }else if(temp.next.no == heroNode.no){//编号相同 已存在 flag = true; break; } //三种条件都不满足，指针后移 temp = temp.next; } if(flag){//已存在 不能添加 System.out.println("编号"+heroNode.no+"已存在"); }else{ heroNode.next = temp.next; temp.next = heroNode; } } //根据编号修改 public void edit(HeroNode newHeroNode){ HeroNode temp = head.next;//直接指向头结点的下一个 boolean flag = false;//表示是否找到节点 while(true){ if(temp == null){ break;//表示已经遍历完链表 } if(temp.no == newHeroNode.no){ //找到 flag = true; break; } temp = temp.next; } if(flag){ temp.name = newHeroNode.name; temp.nickName = newHeroNode.nickName; }else{ System.out.println("没有找到编号"+newHeroNode.no+"的英雄"); } } //删除节点 public void delete(int no){ //辅助变量 HeroNode temp = head; boolean flag = false;//标志是否找到待删除节点 while(true){ if(temp.next == null){ break; } if(temp.next.no == no){ //找到了待删除节点的前一个节点temp flag = true; break; } //后移 temp = temp.next; } if(flag){ //跳过要删除的节点，jvm垃圾回收机制会清理没有作用的节点 temp.next = temp.next.next; }else{ System.out.println("要删除的节点不存在"); } } //显示链表 public void show() { //如果链表为空就直接返回 if (head.next == null) { System.out.println("链表为空"); return; } //再次使用一个辅助变量来遍历 HeroNode temp = head.next; while (true) { //判断链表是否到最后 if (temp == null) { break; } //输出节点信息 System.out.println(temp); //将temp后移 temp = temp.next; } } }
问题1，统计链表中有效节点的个数
public static int getLength(SingleLinkedList link){ if(link.head.next == null){ //空链表 返回0 return 0; } int length = 0; HeroNode current = link.head; //头结点不是有效节点 不统计头结点 while(current.next != null){ length += 1; current = current.next; } return length; }
问题2，获取链表中倒数第k个元素的值
public static HeroNode findLastIndexNode(SingleLinkedList link,int index){ //如果链表为空 直接返回null 没找到 if(link.head.next == null){ return null; } //遍历获取链表的有效个数，调用刚才的方法 int size = getLength(link); //校验数据是否合法 if(index <= 0 || index > size){ return null; } //遍历size-index的位置，就是倒数第k个节点 HeroNode current = link.head.next; for(int i = 0;i < size-index;i++){ current = current.next; } return current; }
问题3，实现单链表的反转
public static void reverseList(SingleLinkedList link){ //如果链表为空，直接返回空 if(link.head.next == null){ return ; } //定义一个车辅助指针，帮助我们遍历原来的链表 HeroNode current = link.head.next; HeroNode next = null;//当前节点的下一个节点 //定义一个新的头结点 HeroNode reverseHead = new HeroNode(0, "", ""); //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的头结点的最前端 while (current != null){ next = current.next;//暂时保存当前节点的下一个节点 current.next = reverseHead.next;//将当前节点的下一个节点指向新的连别的最前端 reverseHead.next = current;//再将新的链表的最前端指向当前节点 current = next;//当前节点后移 } //原来的头结点指向新的头结点，实现反转 link.head.next = reverseHead.next; }
问题4，反向打印单链表
对于这个问题，我们可以对链表先进行反转然后再遍历输出，但是这样会破坏原来链表的结构，没必要。
所以采取另外一种方法，利用栈的先进后出的特性，把链表中的元素压入栈中在取出打印。
public static void reversePrint(SingleLinkedList link){ if(link.head.next == null){ return ; } Stack<HeroNode> stack = new Stack<>(); HeroNode current = link.head.next; while(current != null){ stack.push(current);//添加到栈 current = current.next;//后移 } while (!stack.empty()){ System.out.println(stack.pop()); } } 双向链表的定义及基本操作 首先定义一个节点类 public class HeroNode2 { public int no;//编号 public String name;//名字 public String nickName;//昵称 public HeroNode2 next;//指向当前节点的下一个节点 public HeroNode2 pre;//指向当前节点的前一个节点 public HeroNode2(int no, String name, String nickName) { this.no = no; this.name = name; this.nickName = nickName; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } }
双向链表
public class DoubleLinkedList { //初始化一个头节点，头结点不动，不存放任何数据 public HeroNode2 head = new HeroNode2(0, "", ""); //显示链表 public void show() { //如果链表为空就直接返回 if (head.next == null) { System.out.println("链表为空"); return; } //再次使用一个辅助变量来遍历 HeroNode2 temp = head.next; while (true) { //判断链表是否到最后 if (temp == null) { break; } //输出节点信息 System.out.println(temp); //将temp后移 temp = temp.next; } } //在双向链表的最后添加一个节点 public void add(HeroNode2 heroNode) { //因为头结点不能动，因此我们需要一个辅助遍历的temp HeroNode2 temp = head; //遍历链表，找到最后的节点 while (true) { //如果指向下一个链表是null 就是最后一个 if (temp.next == null) { break; } //如果不是空 就是还没到最后一个，将temp后移 temp = temp.next; } //当退出while循环时，temp就指向了链表的最后 temp.next = heroNode; heroNode.pre = temp; } //根据编号修改 public void edit(HeroNode2 newHeroNode){ HeroNode2 temp = head.next;//直接指向头结点的下一个 boolean flag = false;//表示是否找到节点 while(true){ if(temp == null){ break;//表示已经遍历完链表 } if(temp.no == newHeroNode.no){ //找到 flag = true; break; } temp = temp.next; } if(flag){ temp.name = newHeroNode.name; temp.nickName = newHeroNode.nickName; }else{ System.out.println("没有找到编号"+newHeroNode.no+"的英雄"); } } //删除节点 //找到待删除的节点，自我删除即可 public void delete(int no){ //辅助变量 HeroNode2 temp = head.next; boolean flag = false;//标志是否找到待删除节点 while(true){ if(temp == null){ break; } if(temp.no == no){ //找到了待删除节点的前一个节点temp flag = true; break; } //后移 temp = temp.next; } if(flag){ temp.pre.next = temp.next; //如果要删除的是最后一个节点，就不能执行下面一句操作（待删除节点后一个节点的pre指向待删除节点的前一个节点） if(temp.next != null){ temp.next.pre = temp.pre; } }else{ System.out.println("要删除的节点不存在"); } } //按顺序添加 public void addByOrder(HeroNode2 node){ //使用辅助变量 //我们找的temp是位于添加位置的前一个节点 HeroNode2 temp = head; boolean flag = false;//如果要添加的编号已存在flag就变成true while (true) { if (temp.next == null) {//说明已经到了链表的最后 break; } if (temp.next.no > node.no) {//如果temp的下一个节点的编号大于要插入节点的编号，位置找到，在temp的后面插入 break; }else if(temp.next.no == node.no){//编号相同 已存在 flag = true; break; } //三种条件都不满足，指针后移 temp = temp.next; } if(flag){//已存在 不能添加 System.out.println("编号"+node.no+"已存在"); }else{ node.next = temp.next; node.pre = temp; temp.next = node; temp.next.pre = node; } } }
