织梦cms 学校网站模板山东潍坊疫情最新消息
什么是单链表？
单链表是一种基础的数据结构，其中每个节点都包含两部分：
- 数据域：存储节点数据。
- 指针域：存储指向下一个节点的引用。
为什么使用头节点？
头节点的存在简化了操作逻辑：
-
统一操作逻辑：即使链表为空，头节点也存在，从而避免特殊情况的判断。
-
简化插入和删除：无需特殊处理第一个节点的操作。
-
没有头节点的add：你必须对是头节点插入进行处理，把当前的node给头节点，这样才不是null，后续才能进行正常查找最后一个的node节点然后进行指向。详情查看下面代码演示过程。
package com.algorithm.dev.linked;import lombok.AllArgsConstructor;
import lombok.Data;/*** @author xiazhihao* @ClassName: NoHeadSingleLinkedList* @ClassNameExplain:* @Description: xiazhihao* @date 2024/12/13 */
public class NoHeadSingleLinkedList {/*** 起始位置 没有设置头节点 现在它为null*/private Node head;/*** 添加数据* @param data 待添加的数据*/public void add(Object data){Node newNode = new Node(data, null);//没有头节点需要判断 因为必须告知起始的地址//【】if (null == head){//【node|next】->head = newNode;}//有新的话必须 往后面找//【1|next】—> 【1|next】 -> null//假设你不判断null == head 那么没有头节点插入就会空指针else {//当前处理的node节点 后面为了找到最后一个会不断遍历更新Node currentNode = newNode;while ( null != currentNode.next){//没找到一直更新当前遍历的情况currentNode = currentNode.next;}//找到了就证明找到了结尾 直接更改指向就链上了currentNode.next = newNode;}}@Data@AllArgsConstructorclass Node{/*** 数据域*/private Object data;/*** 下一个指针*/private Node next;}}
- 有头节点的add：不管是不是头节点都可以直接按一套逻辑查找，直接找最后的node，因为头节点给了入口进行查找，不会出现null的情况。
/*** @author xiazhihao* @ClassName: SingleLinkedList* @ClassNameExplain:* @Description: 有头节点的标志单链表* @date 2024/12/13 */
@ToString
public class SingleLinkedList {/*** 头节点*/private Node head = new Node("我是头节点，不要动我，我是多余的，我为方便新增或者删除少做逻辑判断",null);/*** 新增链表数据 尾插o(n)* @param data 数据*/public void add(Object data){Node newNode = new Node(data,null);//用于后续编辑找到最后一个节点 代表当前遍历的位置Node currentNode = head;while (null != currentNode.next){currentNode = currentNode.next;}//【currentNode|next】 -> 【newNode|next】 -> null//找到了最后的节点currentNode.next = newNode;}
}
链表实现及方法解析
链表结构
初始状态下链表只有一个头节点：
【head|next】-> null
1. 新增节点：尾插法
代码实现：
/*** 新增链表数据 尾插o(n)* @param data 数据*/
public void add(Object data){Node newNode = new Node(data,null);// 用于后续编辑找到最后一个节点，代表当前遍历的位置Node currentNode = head;while (null != currentNode.next){currentNode = currentNode.next;}//【currentNode|next】 -> 【newNode|next】 -> null// 找到了最后的节点currentNode.next = newNode;
}
操作示意图：
- 插入 “1” 后：
【head|next】-> 【1|next】-> null - 插入 “2” 后：
【head|next】-> 【1|next】-> 【2|next】-> null
2. 新增节点：头插法
代码实现：
/*** 头插法 o(1)* @param data*/
public void afterAdd(Object data){Node newNode = new Node(data,null);// 【1|next】-> nullnewNode.next = head;head = newNode;// 【newNode|next】->【1|next】-> null
}
操作示意图：
-
插入 “2” 后：
【head|next】-> 【2|next】-> null -
插入 “3” 后：
【head|next】-> 【3|next】-> 【2|next】-> null
3. 查找节点
代码实现：
/*** 查找出指定节点*/
public Node find(Object data){// 头节点不需要查找Node currentNode = head.next;if (null != currentNode){// 一直往下找while (null != currentNode.next){if (currentNode.data.equals(data)){return currentNode;}// 继续往下滚currentNode = currentNode.next;}return null;}// 啥都没有return null;
}
操作示意图：
查找 “2” 的节点：
【head|next】-> 【1|next】-> 【2|next】-> null↑查找
4. 删除节点：按数据删除
代码实现：
/*** 删除节点* @param data 待删除的节点* @return true 删除成功 false 删除失败*/
public boolean remove(Object data){if (isEmpty()){return false;}Node currentNode = head;while (null != currentNode.next){// 找当前系节点的下一个数据是符合删除的if (currentNode.next.data.equals(data)){// 找到了currentNode.next = currentNode.next.next;// 后续会自动释放2return true;}// 继续往下滚currentNode = currentNode.next;}return false;
}
5. 删除节点：按索引删除
代码实现：
/*** 删除指定坐标node* @param index 坐标* @return true 删除成功 false 删除失败*/
public boolean remove(int index){// 前驱节点Node preNode = head;// 遍历到指定位置的前驱节点for (int i = 0; i < index; i++) {if (preNode.next == null) {return false; // 索引超出范围}preNode = preNode.next;}// 删除了前驱next的节点if (preNode.next != null) {preNode.next = preNode.next.next; // 前驱节点指向后继节点return true;}return false;
}
6. 获取节点：按索引获取
代码实现：
/*** 获取node节点* @param index 坐标从0开始* @return*/
public Node get(int index){Node currentNode = head;for (int i = 0; i <= index; i++) {if (null == currentNode.next){return null; // 超界}currentNode = currentNode.next;}return currentNode;
}
测试代码与运行结果
测试代码：
public static void main(String[] args) {SingleLinkedList singleLinkedList = new SingleLinkedList();singleLinkedList.add("1");singleLinkedList.add("2");singleLinkedList.add("3");// 删除索引3的节点boolean remove = singleLinkedList.remove(3);System.out.println(remove); // 输出 false// 输出链表System.out.println(singleLinkedList);
}
运行结果：
false
SingleLinkedList(head=Node(data=我是头节点，不要动我，我是多余的，我为方便新增或者删除少做逻辑判断, next=Node(data=1, next=Node(data=2, next=Node(data=3, next=null)))))
完整代码
以下是完整代码：
package com.algorithm.dev.linked;import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.ToString;import java.util.LinkedList;/*** @author xiazhihao* @ClassName: SingleLinkedList* @ClassNameExplain:* @Description: 有头节点的标志单链表* @date 2024/12/13*/
@ToString
public class SingleLinkedList {/*** 头节点*/private Node head = new Node("我是头节点，不要动我，我是多余的，我为方便新增或者删除少做逻辑判断",null);/*** 新增链表数据 尾插o(n)* @param data 数据*/public void add(Object data){Node newNode = new Node(data,null);//用于后续编辑找到最后一个节点 代表当前遍历的位置Node currentNode = head;while (null != currentNode.next){currentNode = currentNode.next;}//【currentNode|next】 -> 【newNode|next】 -> null//找到了最后的节点currentNode.next = newNode;}/*** 头插法 o(1)* @param data*/public void afterAdd(Object data){Node newNode = new Node(data,null);//【1|next】-> nullnewNode.next = head;head = newNode;//【newNode|next】->【1|next】-> null}/*** 查找出指定节点*/public Node find(Object data){//头节点不需要查找Node currentNode = head.next;if (null != currentNode){//一直往下找while ( null != currentNode.next){if (currentNode.data.equals(data)){return currentNode;}//继续往下滚currentNode = currentNode.next;}return null;}//啥都没有return null;}/****/public boolean isEmpty(){return head.next == null;}/*** 删除节点* @param data 待删除的节点* @return true 删除成功 false 删除失败*/public boolean remove(Object data){if (isEmpty()){return false;}Node currentNode = head;//【1|next】->【2|next】->【3|next】->//【1|next】->【3|next】->//while ( null != currentNode.next){//找当当前系节点的下一个数据是符合删除的代表需要上面所属的操作 1链入3if (currentNode.next.data.equals(data)){//找到了currentNode.next = currentNode.next.next;//后续会自动释放2return true;}//继续往下滚currentNode = currentNode.next;}return false;}/*** 删除指定坐标node* @param index 坐标* @return true 删除成功 false 删除失败*/public boolean remove(int index){//前驱节点Node preNode = head;// 遍历到指定位置的前驱节点for (int i = 0; i < index; i++) {if (preNode.next == null) {return false; // 索引超出范围}preNode = preNode.next;}//删除了前驱next的节点 自动释放 如果不是最后一个if (preNode.next != null) {preNode.next = preNode.next.next; // 前驱节点指向后继节点return true;}return false;}/*** 获取node节点* @param index 坐标从0开始* @return*/public Node get(int index){Node currentNode = head;for (int i = 0; i <= index; i++) {//下一个坐标没有 还在遍历肯定是超界了if ( null == currentNode.next){return null;}currentNode = currentNode.next;}return currentNode;}@AllArgsConstructor@Dataclass Node{/*** 数据*/private Object data;/*** next指针*/private Node next;}public static void main(String[] args) {SingleLinkedList singleLinkedList = new SingleLinkedList();singleLinkedList.add("1");singleLinkedList.add("2");singleLinkedList.add("3");boolean remove = singleLinkedList.remove(3);System.out.println(remove);System.out.println(singleLinkedList);}}