单向链表
- 以节点的形式来存储，蕴含data和next
- 在内存中，链表的各个节点不肯定是间断存储的
- 链表分有头节点的链表和没有头节点的链表，头节点用head示意
- 代码次要是单向链表的增删改查
import java.util.Stack;public class Demo2 { public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList(); //创立用户节点，并插入链表 UserNode user1 = new UserNode(1, "一一"); UserNode user3 = new UserNode(3, "三三"); UserNode user2 = new UserNode(2, "二二"); linkedList.addNode(user1); linkedList.addNode(user3); linkedList.addNode(user2); linkedList.getList(); System.out.println(); //按id大小插入 System.out.println("有序插入"); UserNode user5 = new UserNode(5, "五五"); UserNode user4 = new UserNode(4, "四四"); linkedList.addByOrder(user5); linkedList.addByOrder(user4); linkedList.getList(); System.out.println(); //按id批改用户信息 System.out.println("批改用户信息"); UserNode userEdit = new UserNode(1, "新一一"); linkedList.changeNode(userEdit); linkedList.getList(); System.out.println(); //依据id删除用户信息 System.out.println("删除用户信息"); linkedList.deleteNode(new UserNode(3, "")); linkedList.getList(); System.out.println(); //取得倒数第几个节点 System.out.println("取得倒数节点"); System.out.println(linkedList.getUserByRec(2)); System.out.println(); //翻转链表 System.out.println("翻转链表"); MyLinkedList newLinkedList = linkedList.reverseList(); newLinkedList.getList(); System.out.println(); //顺叙遍历链表 System.out.println("倒序遍历链表"); newLinkedList.reverseTraverse(); }}/** * 创立链表 */class MyLinkedList { private UserNode head = new UserNode(0, ""); /** * 在链表尾部增加节点 * * @param node 要增加的节点 */ public void addNode(UserNode node) { //创立一个辅助节点,用于遍历 UserNode temp = head; //找到最初一个节点 while (true) { //temp是尾节点就进行循环 if (temp.next == null) { break; } //不是尾结点就向后挪动 temp = temp.next; } temp.next = node; } /** * 遍历链表 */ public void getList() { System.out.println("开始遍历链表"); if (head.next == null) { System.out.println("链表为空"); } //创立辅助节点 UserNode temp = head.next; while (true) { //遍历实现就进行循环 if (temp == null) { break; } System.out.println(temp); temp = temp.next; } } /** * 按id程序插入节点 * * @param node */ public void addByOrder(UserNode node) { //如果一个节点都没用，直接插入 if (head.next == null) { head.next = node; return; } UserNode temp = head; while (temp.next != null && temp.next.id < node.id) { temp = temp.next; } //当指标node的id最大时，则不会执行if中的语句 if (temp.next != null) { node.next = temp.next; } temp.next = node; } /** * 依据id来批改节点信息 * * @param node 批改信息的节点 */ public void changeNode(UserNode node) { UserNode temp = head; //遍历链表，找到要批改的节点 while (temp.next != null && temp.id != node.id) { temp = temp.next; } //如果temp曾经是最初一个节点，判断id是否相等 if (temp.id != node.id) { System.out.println("未找到该用户的信息，请先创立该用户的信息"); return; } //批改用户信息 temp.name = node.name; } /** * 依据id删除节点,找到待删除节点的上一个节点 * * @param node 要删除的节点 */ public void deleteNode(UserNode node) { if (head.next == null) { System.out.println("链表为空"); return; } UserNode temp = head; //遍历链表，找到要删除的节点 while (temp.next != null && temp.next.id != node.id) { temp = temp.next; } //判断最初一个节点的是否要删除的节点 if (temp.next.id != node.id) { System.out.println("请先插入该用户信息"); return; } //删除该节点 temp.next = temp.next.next; } /** * 失去倒数的节点 * * @param index 倒数第几个数 * @return */ public UserNode getUserByRec(int index) { if (head.next == null) { System.out.println("链表为空!"); } UserNode temp = head.next; //记录链表长度 //所以length初始化为1 int length = 1; while (temp.next != null) { temp = temp.next; length++; } if (length < index) { throw new RuntimeException("链表越界"); } //假如有五个，倒数第一个相当于负数第五个 temp = head.next; for (int i = 0; i < length - index; i++) { temp = temp.next; } return temp; } /** * 翻转链表 * * @return 反转后的链表 */ public MyLinkedList reverseList() { //链表为空或者只有一个节点，无需翻转 if (head.next == null || head.next.next == null) { System.out.println("无需翻转"); } MyLinkedList newLinkedList = new MyLinkedList(); //用于保留正在遍历的节点 UserNode temp = head.next; //用于保留正在遍历节点的下一个节点 UserNode nextNode = temp.next; while (true) { //插入新链表 temp.next = newLinkedList.head.next; newLinkedList.head.next = temp; //挪动到下一个节点 temp = nextNode; nextNode = nextNode.next; if (temp.next == null) { //插入最初一个节点 temp.next = newLinkedList.head.next; newLinkedList.head.next = temp; head.next = null; return newLinkedList; } } } public void reverseTraverse() { if (head == null) { System.out.println("链表为空"); } UserNode temp = head.next; //创立栈，用于寄存遍历到的节点 Stack<UserNode> stack = new Stack<>(); while (temp != null) { stack.push(temp); temp = temp.next; } while (!stack.isEmpty()) { System.out.println(stack.pop()); } }}/** * 定义节点 */class UserNode { int id; String name; //用于保留下一个节点的地址 UserNode next; public UserNode(int id, String name) { this.id = id; this.name = name; } @Override public String toString() { return "UserNode{" + "id=" + id + ", name='" + name + '\'' + '}'; }}