网站维护有多长时间,哪些网站论坛做推广好,网站怎么打开,wordpress分页链接什么是单链表#xff1f;
单链表是一种基础的数据结构#xff0c;其中每个节点都包含两部分#xff1a;
数据域#xff1a;存储节点数据。指针域#xff1a;存储指向下一个节点的引用。 为什么使用头节点#xff1f;
头节点的存在简化了操作逻辑#xff1a; 统一操作…什么是单链表
单链表是一种基础的数据结构其中每个节点都包含两部分
数据域存储节点数据。指针域存储指向下一个节点的引用。 为什么使用头节点
头节点的存在简化了操作逻辑 统一操作逻辑即使链表为空头节点也存在从而避免特殊情况的判断。 简化插入和删除无需特殊处理第一个节点的操作。 没有头节点的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;}}DataAllArgsConstructorclass 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】- null1. 新增节点尾插法
代码实现
/*** 新增链表数据 尾插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】- null2. 新增节点头插法
代码实现
/*** 头插法 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】- null3. 查找节点
代码实现
/*** 查找出指定节点*/
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(headNode(data我是头节点不要动我我是多余的我为方便新增或者删除少做逻辑判断, nextNode(data1, nextNode(data2, nextNode(data3, nextnull)))))完整代码
以下是完整代码
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;}AllArgsConstructorDataclass 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);}}
