云南网站定制,阿毛免费模板网,wordpress xiu主题最新版,一块钱涨1000粉网站#x1f937;♀️#x1f937;♀️#x1f937;♀️ 今天给大家分享的是单链表的基本操作。 清风的个人主页 #x1f389;欢迎#x1f44d;点赞✍评论❤️收藏 #x1f61b;#x1f61b;#x1f61b;希望我的文章能对你有所帮助#xff0c;有不足的地方还请各位… ♀️♀️♀️ 今天给大家分享的是单链表的基本操作。 清风的个人主页 欢迎点赞✍评论❤️收藏 希望我的文章能对你有所帮助有不足的地方还请各位看官多多指教大家一起学习交流 动动你们发财的小手点点关注点点赞在此谢过啦哈哈哈 目录 一、接口定义
二、类定义
三、方法实现
3.1创建单链表(初始化创建)
3.2头插法插入节点
3.3尾插法插入节点
3.4指定位置插入节点
3.5判断节点是否包含在链表中
3.6删除值为key的节点 3.7删除所有值为key的节点
3.8得到链表长度
3.9清空链表
3.10显示链表(打印) 源码链接:清风的Gitee主页 一、接口定义
还是和之前的顺序表一样定义一个接口。后续通过链表类去实现这个定义的接口。
interface SingleLinkedList {//头插法void addFirst(int data);//尾插法void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void clear();void display();
}
二、类定义
定义一个链表类它是由各个节点构成的因此还需要在链表类内定义一个关于节点的内部类。代码如下
public class MyLinkedList implements SingleLinkedList {class LinkNode {public int val;public LinkNode next;public LinkNode(int val) {this.val val;}}public LinkNode head;
}
三、方法实现
3.1创建单链表(初始化创建)
每次通过LinkNode类定义的节点去new一个新的节点并通过构造函数设置初始值节点定义完成后通过各个节点的next域把各个节点之间联系起来便成功创建了一个单链表。 public void creatLinkedList() {LinkNode node1 new LinkNode(12);LinkNode node2 new LinkNode(23);LinkNode node3 new LinkNode(34);LinkNode node4 new LinkNode(45);LinkNode node5 new LinkNode(56);node1.next node2;node2.next node3;node3.next node4;node4.next node5;this.head node1;}
3.2头插法插入节点 //头插法public void addFirst(int data) {LinkNode newnode new LinkNode(data);if (this.head null) {this.head newnode;} else {newnode.next this.head;this.head newnode;}}
3.3尾插法插入节点
尾插法插入节点时首先要找到单链表的最后一个节点再去插入。
注意找到单链表的最后一个节点在while循环里面的控制条件是cur.next!null而不是cur!null这一点要切记在我们刷题的时候很多情况下都要去遍历找节点因此一定要注意。(cur是一个引用从head开始遍历)下图是while(cur.next!null),循环条件结束的时候,cur所指向的位置: 下图是while(cur!null)循环条件结束的时候cur所指向的位置: public void addLast(int data) {LinkNode newnode new LinkNode(data);if (this.head null) {this.head newnode;return;}LinkNode cur this.head;while (cur.next ! null) {cur cur.next;}cur.next newnode;}
3.4指定位置插入节点
在指定位置插入首先要判断插入位置是否合法。其次若是在头节点插入调用头插法即可若是在尾节点插入调用尾插法即可。然后就需要找到指定的位置此时应该找的是指定位置的前驱节点通过指定位置的前驱节点的next域指向要插入的节点即可。当然在执行这一步骤之前我们还需要先把前驱节点的next域所指向的节点交给要插入的节点的next域。 public void addIndex(int index, int data) {if (index 0 || index size()) {System.out.println(插入位置不合法: index);return;}if (index 0) {addFirst(data);return;}if (index size()) {addLast(data);return;}LinkNode cur this.head;LinkNode newnode new LinkNode(data);for (int i 0; i index - 1; i) {cur cur.next;}newnode.next cur.next;cur.next newnode;}
3.5判断节点是否包含在链表中
只需遍历链表比较节点的值是否和要判断节点的值相等即可。 public boolean contains(int key) {LinkNode cur this.head;while (cur ! null) {if (cur.val key) {return true;}cur cur.next;}return false;}
3.6删除值为key的节点
要先找到值为key的节点的前驱节点 private LinkNode findPrev(int key) {LinkNode cur this.head;while ((cur.next ! null)) {if (cur.next.val key) {return cur;}cur cur.next;}return cur;}
以下图为例假设删除34: public void remove(int key) {if (this.head null) {System.out.println(链表为空无法删除!!!);return;}if (this.head.val key) {this.head this.head.next;return;}
/* while(cur.next!null){//找到要删除节点的前驱if(cur.next.valkey){LinkNode delcur.next;cur.nextdel.next;return;}else {curcur.next;}}*/LinkNode prev findPrev(key);if (prev null) {System.out.println(无要删除的数字: key);return;}LinkNode del prev.next;prev.nextdel.next;} 3.7删除所有值为key的节点
方法是通过双指针来解决:
假设删除值为23的所有节点。 cur往前走发现值为23的节点进行删除操作:
删除之后prev指向了23的下一个节点。 删除完成后prev不动cur继续往后遍历: 当cur这个引用所指向的节点的值不是23是prev也要继续往前挪: 如此进行下去即可删除所有值为23的节点。
下面是实现代码 public void removeAllKey(int key) {if (this.head null) {System.out.println(链表为空!);return;}LinkNode prev head;LinkNode cur head.next;while (cur ! null) {if (cur.val key) {prev.next cur.next;cur cur.next;} else {prev cur;cur cur.next;}}if (head.val key) {head head.next;}}
3.8得到链表长度
很简单只需通过一个引用遍历即可。如果引用所指的对象不是空那么计数器1。 public int size() {LinkNode cur this.head;int count 0;while (cur ! null) {count;cur cur.next;}return count;}
3.9清空链表 public void clear() {LinkNode cur this.head;while (cur ! null) {LinkNode curNext cur.next;cur.next null;cur curNext;}head.next null;}
3.10显示链表(打印) public void display(LinkNode newhead) {LinkNode cur newhead;while (cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();} 好啦今天的分享就到这里 ✨创作不易还希望各位大佬支持一下 点赞你的认可是我创作的动力 ⭐收藏你的青睐是我努力的方向 ✏️评论你的意见是我进步的财富
