福建：网站建设,山东德州做网站,区域推广网站,做彩票网站推广文章目录 前言什么是链表链表的结构带头和不带头的区别 链表的实现#xff08;方法#xff09;遍历链表头插法尾插法任意位置插入一个节点链表中是否包含某个数字删除链表某个节点删除链表中所有关键字key清空链表所有节点 ArrayList 和 LinkedList的区别总结 前言
什么是链… 文章目录 前言什么是链表链表的结构带头和不带头的区别 链表的实现方法遍历链表头插法尾插法任意位置插入一个节点链表中是否包含某个数字删除链表某个节点删除链表中所有关键字key清空链表所有节点 ArrayList 和 LinkedList的区别总结 前言
什么是链表
含义链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
图形解释 逻辑上是连续的但物理上看起来不连续 这个图形也叫单向不带头非循环
链表的结构
非常多样有8种结构
重点掌握下面两种
无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
无头双向链表在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
带头和不带头的区别 链表的实现方法 定义接口
public interface ILIst {// 1、无头单向非循环链表实现//头插法void addFirst(int data);//尾插法void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void clear();void display();
}遍历链表 1.怎么从一个节点走到下一个节点 head head.next
2.怎么判断所有节点遍历完了 当head null 循环结束 // while(head ! null){
// System.out.print(head.val );
// head head.next;
// }//这个方法遍历完headnull,会导致链表空了找不到第一个节点在哪了
//所以应该把head赋值给一个数让它去遍历相当于head的分身分身消失了主体head还在ListNode cur this.head;//进入循环条件为链表不为空//也就是说当head为空时循环结束while(cur ! null){System.out.print(cur.val );cur cur.next;}头插法 //头插法//时间复杂度O1Overridepublic void addFirst(int data) {//先实例化一个节点ListNode node new ListNode(data);//如果链表没有节点那么插入的这个节点就是第一个节点//所以head nodeif (this.head null){this.head node;}else {node.next this.head;this.head node;}}尾插法 //尾插法:在最后创建一个节点//时间复杂度ONOverridepublic void addLast(int data) {//创建一个新节点ListNode node new ListNode(data);ListNode cur this.head;//当链表为空时此案件的新节点就是第一个节点if (this.head null){this.head node;}else {//让cur遍历完走到cur.next为空时才找到了最后一个节点//意思就是走出了while循环就说明cur走到了最后一个节点上while (cur.next ! null){cur cur.next;}cur.next node;node.next null;}}任意位置插入一个节点 //让cur去到index-1位置private ListNode searchPrev(int index){ListNode cur this.head;int count 0;while(count ! index-1){cur cur.next;count;}//循环走完, cur已经走到index-1得位置了return cur;}//任意位置插一个节点Overridepublic void addIndex(int index, int data) {ListNode node new ListNode(data);//检查index得合法性if (index 0 || index size()){//抛自定义异常return ;}//如果index0 头插法if (index 0){addFirst(data);return;}//如果indexsize,尾插法if (index size()){addLast(data);return;}ListNode cur searchPrev(index);//调用cur走到index-1的方法node.next cur.next;cur.next node;}链表中是否包含某个数字 //链表是否包含某个数字Overridepublic boolean contains(int key) {ListNode cur this.head;while(cur ! null){if (cur.val key){return true;}cur cur.next;}return false;}Overridepublic void remove(int key) {}删除链表某个节点 //让cur走到要删除的节点的前一个节点private ListNode findPrev(int key){ListNode cur this.head;//判断条件是cur不能超过倒数二个节点while(cur.next ! null ){if (cur.next.val key){return cur;}cur cur.next;}return null;}Overridepublic void remove(int key) {//如果链表为空,无法删除if (this.head null){return ;}//如果要删除第一个节点if (this.head.val key){this.head this.head.next;return;}//判断前驱ListNode cur findPrev(key);//判断返回值是否为空if (cur null){System.out.println(没有你要删除的数字);return ;}//删除ListNode del cur.next;cur.next del.next;}
删除链表中所有关键字key //删除链表中所有关键字keyOverridepublic void removeAllKey(int key) {if (this.head null){return;}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 head.next;}}清空链表所有节点 public void clear() {ListNode cur this.head;while(cur ! null){ListNode curNext cur.next;cur.next null;cur curNext;}this.head null;}ArrayList 和 LinkedList的区别 总结
以上就是关于链表的详细知识。
