[数据结构] 链表之一(胖黑)毁所有 （无头单向非循环链表实现）
目录
往期回顾，专栏一览
🔴 链表
🔵 链表的概念及结构
🔵 无头单向非循环链表实现
🔵 黑胖毁所有
往期回顾，专栏一览
🍉 JavaSE 🍋 AWT 🍑 数据结构 🍅 C1进阶之路 🍒 每日一练 🌽 代码报错 🍈 活动
🍹欢迎各路大佬来到 Nick 主页指点
☀️本期文章将学习 [数据结构] 链表之一(胖黑)毁所有 （无头单向非循环链表实现），我是博主Nick。✨
✨我的博客主页：Nick_Bears 🌹꧔ꦿ
🌹꧔ꦿ博文内容如对您有所帮助，还请给个点赞 + 关注 + 收藏✨
🔴 链表
🔵 链表的概念及结构
🔶 链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
🔶 实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向、双向
- 带头、不带头
- 循环、非循环
虽然有这么多的链表的结构，但是我们重点掌握两种:
🔷 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希、桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
🔷 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
🔵 无头单向非循环链表实现
💠 提供以下方法
// 1、无头单向非循环链表实现public class SingleLinkedList { //头插法 public void addFirst(int data); //尾插法 public void addLast(int data); //任意位置插入,第一个数据节点为0号下标 public boolean addIndex(int index,int data); //查找是否包含关键字key是否在单链表当中 public boolean contains(int key); //删除第一次出现关键字为key的节点 public void remove(int key); //删除所有值为key的节点 public void removeAllKey(int key); //得到单链表的长度 public int size(); public void display(); public void clear(); }
💠 方法实现
package 链表.头插尾插;// ListNode 代表一个节点class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val = val; }}public class MyLinkedList { public ListNode head;//链表的头 //用于帮助新手理解 public void creatList() { ListNode listNode1 = new ListNode(1); ListNode listNode2 = new ListNode(13); ListNode listNode3 = new ListNode(11); ListNode listNode4 = new ListNode(17); ListNode listNode5 = new ListNode(54); listNode1.next = listNode2; listNode2.next = listNode3; listNode3.next = listNode4; listNode4.next = listNode5; //listNode5.next = null; this.head = listNode1; } //这样做不可行,我的头没了// public void display(){// //this.head.next!=null少打印一个// while(this.head!=null){// System.out.println(this.head.val+" ");// this.head = this.head.next;// }// } //遍历 public void display() { ListNode cur = this.head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } // 1、无头单向非循环链表实现 //头插法 public void addFirst(int data) {//一定记住，绑定的时候，一定要先绑定后面 ListNode node = new ListNode(data); node.next = head; this.head = node;// if(this.head == null){// this.head = node;// }else{// node.next = head;// this.head = node;// } } //尾插法 public void addLast(int data) {//尾插第一次必须要判断 ListNode node = new ListNode(data); if (head==null) { this.head = node; }else{ ListNode cur = this.head; while (cur.next!= null) { cur = cur.next; } cur.next = node; } } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index, int data) { if(indexsize()){ System.out.println("index位置不合法"); return; } if(index==0){ addFirst(data); return; } if(index==size()){ addLast(data); return; } ListNode cur = findIndex(index); ListNode node = new ListNode(data); node.next = cur.next; cur.next = node; } //找到插入前驱index-1 public ListNode findIndex(int index){ ListNode cur = this.head; while(index-1!=0){ cur = cur.next; index--; } return cur; } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key) { ListNode cur = this.head; while (cur != null) { if (cur.val == key) { return true; } cur = cur.next;//先判断再走，不然会错过第一个 } return false; } //找到删除的关键字的前驱 public ListNode searchPerv(int key){ ListNode cur = this.head; while(cur.next!=null){ if(cur.next.val==key){ return cur; } cur = cur.next; } return null; } //删除第一次出现关键字为key的节点 public void remove(int key) { if(this.head == null){ System.out.println("单链表为空，不能删除"); return; } if(this.head.val==key){ this.head=this.head.next; return; } ListNode cur = searchPerv(key); if(cur == null){ System.out.println("没有你要删除的节点"); return; } ListNode del = cur.next; cur.next = del.next; } //遍历链表一遍,删除所有值为key的节点(一个思路，代码后面要加最后位的判断)// public void removeAllKey(int key){// if(this.head == null){// System.out.println("单链表为空，不能删除");// return;// }// if(this.head.val==key){// this.head=this.head.next;// return;// }// ListNode last_cur = this.head;// ListNode cur =this.head.next;// int count = 0;// int size = this.size();// while(cur.next!=null && count < size){// ListNode cur_next = cur.next;// if(cur.val==key){// last_cur.next = cur_next;// }else{// last_cur = cur;// }// cur = cur.next;// count++;// }// } //推荐 public ListNode removeAllKey(int key) { if(this.head==null){ return null; } ListNode prev = this.head; ListNode cur = this.head.next; while(cur !=null){ if(cur.val==key){ prev.next = cur.next; cur = cur.next; }else{ prev = cur; cur = cur.next; } } if(this.head.val == key){ this.head = this.head.next; } return this.head; } //得到单链表的长度 public int size() { int count = 0; ListNode cur = this.head; while (cur != null) { count++; cur = cur.next; } return count; } //温柔的清空链表 public void clear() { while(head!=null){ ListNode curNext = head.next; head.next = null; head = curNext; } }}
💠 方法测试
package 链表.头插尾插;public class Demo { public static void main(String[] args) { MyLinkedList myLinkedList=new MyLinkedList(); myLinkedList.addFirst(1); myLinkedList.addFirst(1); myLinkedList.addFirst(1); myLinkedList.addFirst(2); myLinkedList.addFirst(2); myLinkedList.addFirst(2); myLinkedList.addIndex(0,10); myLinkedList.removeAllKey(2); System.out.println(myLinkedList.size()); myLinkedList.clear(); myLinkedList.addFirst(10); myLinkedList.display(); }}
💠 难点分析
这是Nick自己写了一遍总结的一些卡点 先理解，后实践 (可能和上面不完全一样)
//心得体悟1.为什么遍历时?是cur!=null,而lastAdd是cur.next!=null; public void display(){ NodeList cur = head; while(cur!=null){ System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); }答：因为遍历时目标是确定自身是否为空(为空跳出循环，不为空sout),添加元素时是判断下一个节点是否为空(为空cur.next = node，不为空 cur = cur.next)2.尾插法最后赋值时为什么是cur.next = node;而不能反着写？ public void lastAdd(int date){ NodeList cur = head; NodeList node = new NodeList(date); while(cur.next!=null){ cur = cur.next; } cur.next = node; }答:node.next指向是空,若node.next=cur意味着，cur的前一个元素是node,但是实际情况是前一个元素已经"另有所指"了，因此不能往前插，只有cur的后面是空滴,所以cur.next = node;3.查询一个元素删除前驱时，为什么while中条件是cur.next!=null,而不是cur!=null;呢？ public NodeList getPrev(int val){ NodeList cur = head; while(cur.next!=null){ if(cur.next.val==val){ return cur; } } return null; }答：前驱为cur,删除元素为cur.next，既然你要删cur.next,那么你就是要保证有这个元素,因此判断cur.next不为空4.小坑：通过前驱找删除的，第0个没有前驱,因此要加一个判断。 //删除元素 public void remove(int val){ if(head.val==val){ head=head.next; return; } if(container(val)){ NodeList cur = getPrev(val); NodeList del = cur.next; cur.next = del.next; }else{ System.out.println("该链表没有这个元素"); } }//删除前驱 public NodeList getPrev(int val){ NodeList cur = head; while(cur.next!=null){ if(cur.next.val==val){ return cur; } } return null; }5.为啥清空链表是head.next而不是head？ //清空链表 public void clear(){ while(head!=null){ NodeList curNext = head.next; head.next = null; head = curNext; } }答：不要担心第一个删不掉，这个代码先删除了第一个的后继,通过head = curNext最终会head=null;
💠 做题时画了一些图
头插法
尾插法
添加节点
删一个元素
删除所有
点我跳转
💠 总结
1、你要搞清楚前驱后继
2、一定记住，绑定的时候，一定要先绑定后面(经验)
3、不要把head头跑没了，因为黑胖毁所有
🔵 黑胖毁所有
🔶 链表：一(胖黑)毁所有
🔶 胖黑：以节点为单位存储，不支持随机访问
🔶 所有：
- 1.任意位置插入删除时间复杂度为O(1)
- 2.没有增容问题，插入一个开辟一个空间。
