链表

链表

链表是以节点的方式来存储的每个节点包含data域，next域链表各个节点不一定是连续存储

链表分带头节点的和不带头节点的 头节点：不存放具体的数据，作用是表示单链表头

判断链表是否为空：判断头节点.next是否为空即可

在Java中，删除链表的某个节点，该节点即不被使用，会被垃圾回收机制回收。

单向链表

代码

import java.util.Stack; /** * @author:zmc * @function: * @date: 2020/10/3 10:46 */ public class SingleLinkedList { public static void main(String[] args) { SingleLinkedList2 linkedList = new SingleLinkedList2(); Node node1 = new Node(1,"宋江","及时雨"); Node node2 = new Node(2,"卢俊义","玉麒麟"); Node node3 = new Node(3,"mc","mc"); Node node4 = new Node(4,"mcmc","mcmc"); Node node5 = new Node(5,"mcmc2","mcmc2"); linkedList.addByOrder(node1); linkedList.addByOrder(node2); linkedList.addByOrder(node3); linkedList.addByOrder(node4); linkedList.addByOrder(node5); //linkedList.reverse(); //linkedList.list(); linkedList.reversePrint(); } } class SingleLinkedList2{ private Node head = new Node(0,"",""); public void add(Node node){ Node temp = head; while(true){ if(temp.next == null){ break; } temp = temp.next; } temp.next = node; } public void reverse(){ Node pre = null; Node next = null; Node head2 = head.next; while (head2 != null) { next = head2.next; head2.next = pre; pre = head2; head2 = next; } //head2.next = pre; head.next = pre; } public void reversePrint(){ Stack<String> stack = new Stack<>(); Node node = head; node = node.next; while(node != null){ stack.push(node.name); node = node.next; } while(!stack.isEmpty()){ System.out.println(stack.pop()); } } public void addByOrder(Node node){ Node temp = head; boolean flag = false; while(true){ if(temp.next == null){ break; } if(temp.next.no > node.no){ break; }else if(temp.next.no == node.no){ flag = true; break; } temp = temp.next; } if(flag){ throw new RuntimeException("该节点已存在！"); }else { node.next = temp.next; temp.next = node; } } public void list(){ if(head.next == null){ throw new RuntimeException("链表为空"); } Node temp = head.next; while(true){ if(temp == null){ return; } System.out.println(temp); temp = temp.next; } } } //节点 class Node{ public int no; public String name; public String nickname; public Node next; public Node(int no,String name,String nickname){ this.no = no; this.name = name; this.nickname = nickname; } @Override public String toString() { return "Node{" + "no=" + no + ", name='" + name + '\'' + ", nickname='" + nickname + '\'' + '}'; } }

双向链表

只有next指针的单向链表存在一些问题

无法往回查找，一旦错过无法返回无法自我删除，只能依靠辅助节点

对于这些问题，我们可以时候双向链表来解决

代码

/** * @author:zmc * @function: * @date: 2020/10/4 12:59 */ public class DoubleLinkedList { public static void main(String[] args) { Node node1 = new Node(1,"1","11"); Node node2 = new Node(2,"2","22"); Node node3 = new Node(3,"3","33"); Node node4 = new Node(4,"4","44"); DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); doubleLinkedList.add(node1); doubleLinkedList.add(node2); doubleLinkedList.add(node3); doubleLinkedList.add(node4); doubleLinkedList.list(); System.out.println("啊哈！"); doubleLinkedList.del(node4.no); doubleLinkedList.list(); } private Node head = new Node(0, "", ""); public Node getHead() { return head; } public void list(){ if (head.next == null) { throw new RuntimeException("链表为空"); } Node temp = head.next; while (temp != null) { System.out.println(temp); temp = temp.next; } } public void add(Node node){ Node temp = head; while(temp.next != null){ temp = temp.next; } temp.next = node; node.pre = temp; } public void update(Node node){ if(head.next == null){ throw new RuntimeException("链表为空"); } Node temp = head.next; boolean flag = false; while (temp != null) { if (node.no == temp.no) { temp.name = node.name; temp.nickname = node.nickname; flag = true; } temp = temp.next; } if(!flag){ throw new RuntimeException("该节点不存在"); } } public void del(int no){ if(head.next == null){ throw new RuntimeException("链表为空"); } Node temp = head; boolean flag = false; while(true){ if(temp == null){ break; } if(temp.no == no){ flag = true; break; } temp = temp.next; } if(flag){ temp.pre.next = temp.next; if(temp.next != null) { temp.next.pre = temp.pre; } }else { throw new RuntimeException("该结点不存在"); } } } class Node{ public int no; public String name; public String nickname; public Node next; public Node pre; public Node(int no,String name,String nickname){ this.no = no; this.name = name; this.nickname = nickname; } @Override public String toString() { return "Node{" + "no=" + no + ", name='" + name + '\'' + ", nickname='" + nickname + '\'' + '}'; } }

单向环形链表

约瑟夫问题

从第k个人开始，每数n次就杀死一人，输出死亡顺序和最后幸存者 下附实现代码

代码

/** * @author:zmc * @function: * @date: 2020/10/4 14:02 */ public class Josepfu { public static void main(String[] args) { CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); circleSingleLinkedList.addBoy(125); circleSingleLinkedList.countBoy(10,20,125); } } class CircleSingleLinkedList{ private Boy first = null; public void addBoy(int nums){ if(nums <= 0){ throw new RuntimeException("不可小于1"); } Boy cur = null; for(int i = 1; i <= nums; i++){ Boy newBoy = new Boy(i); if(i == 1){ first = newBoy; first.setNext(first); cur = first; }else { cur.setNext(newBoy); newBoy.setNext(first); cur = newBoy; } } } public void list(){ if(first == null || first.getNext() == null){ throw new RuntimeException("链表为空"); } Boy cur = first; while(cur != null){ System.out.println(cur.getNo()); if(cur.getNext() == first){ break; } cur = cur.getNext(); } } public void countBoy(int startNo,int countNum,int nums){ if(first == null || startNo < 1 || startNo > nums){ throw new RuntimeException("数据不规范"); } Boy cur = first; for(int i = 0; i < startNo - 1; i++){ cur = cur.getNext(); } while(cur.getNext() != cur){ for(int i = 0; i < countNum - 2; i++){ cur = cur.getNext(); } System.out.println(cur.getNext().getNo()); cur.setNext(cur.getNext().getNext()); cur = cur.getNext(); } System.out.println("最后幸存者为"+cur.getNo()); } } class Boy{ private int no; private Boy next; public Boy(int no) { this.no = no; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public Boy getNext() { return next; } public void setNext(Boy next) { this.next = next; } }