单向链表的介绍和实现思路

链表在内存中的存储

• 链表是以节点的方式来存储, 是链式存储
• 每个节点包含 data 域 和 next 域。next域用来指向下一个节点
• 链表的各个节点不一定是连续存储的
• 链表分 带头节点的链表和 没有头节点的链表，根据实际的需求来确定

带头结点的 逻辑示意图

创建（添加）

• 先创建一个Head头节点，表示单链表的头

• 后面我们每添加一个节点，就放在链表的最后

• 通过一个辅助变量，来遍历整个链表

有序插入

• 先遍历链表，找到应该插入的位置
• 要插入的节点的next指向插入位置的后一个节点
• 插入位置的前一个节点的next指向要插入节点
• 插入前要判断是否在队尾插入

根据某个属性节点修改值

• 先遍历节点，找到修改的位置
• 如果未找到修改节点，则不修改

删除某个节点

• 先遍历节点，找到要删除节点的前一个节点
• 进行删除操作

求倒数第n个节点的信息

• 遍历链表，求出链表的 有效长度length（不算头结点）
• 遍历链表到第length-n的节点

翻转链表

• 创建一个新的头结点，作为新链表的头
• 从头遍历旧链表，将遍历到的节点插入新链表的头结点之后
• 注意需要用到 两个暂存节点
• 一个用来保存正在遍历的节点
• 一个用来保存正在遍历节点的下一个节点

逆序打印

• 遍历链表，将遍历到的节点入栈
• 遍历完后，进行出栈操作，同时打印出栈元素

java;collapse:true;;gutter:true; public class Demo1 { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); linkedList.traverseNode(); System.out.println(); //创建学生节点，并插入链表 StudentNode student1 = new StudentNode(1, "Nyima"); StudentNode student3 = new StudentNode(3, "Lulu"); linkedList.addNode(student1); linkedList.addNode(student3); linkedList.traverseNode(); System.out.println();</p> <pre><code> //按id大小插入 System.out.println("有序插入"); StudentNode student2 = new StudentNode(0, "Wenwen"); linkedList.addByOrder(student2); linkedList.traverseNode(); System.out.println(); //按id修改学生信息 System.out.println("修改学生信息"); student2 = new StudentNode(1, "Hulu"); linkedList.changeNode(student2); linkedList.traverseNode(); System.out.println(); //根据id删除学生信息 System.out.println("删除学生信息"); student2 = new StudentNode(1, "Hulu"); linkedList.deleteNode(student2); linkedList.traverseNode(); System.out.println(); //获得倒数第几个节点 System.out.println("获得倒数节点"); System.out.println(linkedList.getStuByRec(2)); System.out.println(); //翻转链表 System.out.println("翻转链表"); LinkedList newLinkedList = linkedList.reverseList(); newLinkedList.traverseNode(); System.out.println(); //倒叙遍历链表 System.out.println("倒序遍历链表"); newLinkedList.reverseTraverse(); } </code></pre> <p>}</p> <p>/*<em> * 创建链表 </em>/ class LinkedList { //头节点，防止被修改，设置为私有的 private StudentNode head = new StudentNode(0, "");</p> <pre><code>/** * 添加节点 * @param node 要添加的节点 */ public void addNode(StudentNode node) { //因为头节点不能被修改，所以创建一个辅助节点 StudentNode temp = head; //找到最后一个节点 while (true) { //temp是尾节点就停止循环 if(temp.next == null) { break; } //不是尾结点就向后移动 temp = temp.next; } //现在temp是尾节点了，再次插入 temp.next = node; } /** * 遍历链表 */ public void traverseNode() { System.out.println("开始遍历链表"); if(head.next == null) { System.out.println("链表为空"); } //创建辅助节点 StudentNode temp = head.next; while(true) { //遍历完成就停止循环 if(temp == null) { break; } System.out.println(temp); temp = temp.next; } } /** * 按id顺序插入节点 * @param node */ public void addByOrder(StudentNode node) { //如果没有首节点，就直接插入 if(head.next == null) { head.next = node; return; } //辅助节点，用于找到插入位置和插入操作 StudentNode temp = head; //节点的下一个节点存在，且它的id小于要插入节点的id，就继续下移 while (temp.next!=null && temp.next.id < node.id) { temp = temp.next; } //如果temp的下一个节点存在，则执行该操作 //且插入操作，顺序不能换 if(temp.next != null) { node.next = temp.next; } temp.next = node; } /** * 根据id来修改节点信息 * @param node 修改信息的节点 */ public void changeNode(StudentNode node) { if(head == null) { System.out.println("链表为空，请先加入该学生信息"); return; } StudentNode 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(StudentNode node) { if(head.next == null) { System.out.println("链表为空"); return; } StudentNode temp = head.next; //遍历链表，找到要删除的节点 if(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 StudentNode getStuByRec(int index) { if(head.next == null) { System.out.println("链表为空!"); } StudentNode temp = head.next; //用户记录链表长度，因为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 stack = new Stack<>(); while(temp != null) { stack.push(temp); temp = temp.next; } while (!stack.isEmpty()) { System.out.println(stack.pop()); } } </code></pre> <p>}</p> <p>/*<em> * 定义节点 </em>/ class StudentNode { int id; String name; //用于保存下一个节点的地址 StudentNode next;</p> <pre><code>public StudentNode(int id, String name) { this.id = id; this.name = name; } @Override public String toString() { return "StudentNode{" + "id=" + id + ", name='" + name + '\'' + '}'; } </code></pre> <p>}

Original: https://www.cnblogs.com/wyh518/p/16725760.html
Author: 腹白
Title: 单向链表的介绍和实现思路