定安网站建设,微网站需要备案吗,网页设计培训教程,沈阳市建设公司网站目录
前言#xff1a;
1、认识双向链表中的结点 2、认识并创建无头双向链表
3、实现双向链表当中的一些方法
3.1、遍历输出方法#xff08;display#xff09;
3.2、得到链表的长度#xff08;size#xff09;
3.3、查找关键字key是否包含在双链表中(contains)
3.…目录
前言
1、认识双向链表中的结点 2、认识并创建无头双向链表
3、实现双向链表当中的一些方法
3.1、遍历输出方法display
3.2、得到链表的长度size
3.3、查找关键字key是否包含在双链表中(contains)
3.4、头插法addFirst
【代码思路】 【代码实现】
3.5、尾插法 addIndex
【代码思路】 【代码实现】
3.6、任意位置插入 第一个数据结点为0号下标addIndex
【代码思路】 【代码示例】
3.7、 删除第一次出现关键字key的结点(remove)
【代码思路】
第一种情况删除头节点。 【代码示例】 3.8、删除所有值为key的结点removeAllKey
【代码思路】
【代码示例】
3.9、清空双向链表clear 【代码思路】 【代码示例】 前言 单向链表能够解决逻辑关系为一对一数据的存储问题但是在解决某些特殊问题的时候单链表并不是效率最有的存储结构。比如需要找某个节点的前驱节点使用单链表并不合适单链表更适合从前往后找而从后往前找并不是单链表的强项。这里就要使用双向链表来解决这类问题。 1、认识双向链表中的结点 双向链表中的结点有两个指针域和一个数据域一个指针指向前驱结点一个指向后继节点。双向链表当中第一个结点的prev为null最后一个结点的next为null 2、认识并创建无头双向链表 在Java当中双链表相比于单链表增加了一个引用lastlast永远指向双链表的最后一个结点。 创建链表类
public class MyLinkedList {static class ListNode{//结点类public int val;public ListNode prev;//前驱public ListNode next;//后继public ListNode(int val){this.val val;}}public ListNode head;public ListNode last;//指向双向链表的结尾
}
3、实现双向链表当中的一些方法 以下这些方法写在MyLinkdeList类当中 3.1、遍历输出方法display public void display(){ListNode cur head;while(cur ! null){//说明cur还没有遍历完这个链表System.out.print(cur.val );cur cur.next;}System.out.println();//当整体输出完成之后换行下一次打印的时候在下一行}3.2、得到链表的长度size public int size(){ListNode cur head;int len 0;while(cur ! null){len;//因为cur是从head向后遍历先通过len将head计算在内cur cur.next;}return len;}3.3、查找关键字key是否包含在双链表中(contains) public Boolean contains(int key){ListNode cur head;while(cur ! null){if(cur.val key){//如果cur在遍历的过程中找到了return true;}cur cur.next;//没有找到就向后走}return false;//遍历完还没找到返回false}
3.4、头插法addFirst
【代码思路】
头插法存在两种情况 【代码实现】 public void addFirst(int data){ListNode node new ListNode(data);//创建一个新的结点if(head null){//如果链表为空插入结点之后头和尾都指向nodehead node;last node;}else{//如果链表不为空。先连接后继再链接前驱最后将head前移node.next head;head.prev node;head node;}} 3.5、尾插法 addIndex
【代码思路】
尾插法存在两种情况。 【代码实现】 public void addLast(int data){ListNode node new ListNode(data);if(head null){head node;last node;}else{last.next node;node.prev last;last node;}}
❗❗❗ 总结 单链表的时间复杂度为O(N)而双链表的时间复杂度为O(1)。 3.6、任意位置插入 第一个数据结点为0号下标addIndex
【代码思路】 【代码示例】 public void addIndex(int index,int data){if(index 0 || index size()){//检查位置的合法性return;//这里可以抛异常也可以直接return}if(index 0){//在链表的开头插入结点addFirst(data);return;}if(index size()){//再链表的结尾插入结点addLast(data);return;}ListNode node new ListNode(data);//创建一个新的结点ListNode cur findIndex(index);//通过调用这个方法找到要插入的位置node.next cur;cur.prev.next node;node.prev cur.prev;cur.prev node;}//通过这个方法来找要插入的位置private ListNode findIndex(int index){ListNode cur head;while(index ! 0){//从头开始遍历链表。cur cur.next;index--;}return cur;} 3.7、 删除第一次出现关键字key的结点(remove)
【代码思路】
第一种情况删除头节点。 第二种和第三种情况删除中间节点和结尾 【代码示例】 public void remove(int key){ListNode cur head;while(cur ! null){//开始删除了if(cur.val key){//1、删除的是头节点if(cur head){head head.next;//head向后移//处理链表只有一个结点的情况if(head ! null) {head.prev null;//将head的前驱置为空}}else{//删除的是中间和结尾cur.prev.next cur.next;//2、删除中间结点if(cur.next ! null){cur.next.prev cur.next;//3、删除尾巴结点}else{last cur.prev;}}return;//这个return对应的是第2个if找到一个与key值相等的结点删除之后就返回只删一个与key值相等的结点}cur cur.next;//对应最开始的if若是要和删除的key不相同继续向后走}} 3.8、删除所有值为key的结点removeAllKey
【代码思路】 当写出删除一个值为key的结点的代码那么删除所有值为key的结点的代码就非常简单了只需要将上述代码中的return去掉就可以了。让上述的代码从头跑到结尾就行这样cur在遍历链表的时候也只是遍历了一遍就将所有与key值相等的结点就删除完了。他的时间复杂度为O(N). 【代码示例】 public void removeAllKey(int key){ListNode cur head;while(cur ! null){//开始删除了if(cur.val key){//1、删除的是头节点if(cur head){head head.next;//head向后移//处理链表只有一个结点的情况if(head ! null) {head.prev null;//将head的前驱置为空}}else{//删除的是中间和结尾cur.prev.next cur.next;//2、删除中间结点if(cur.next ! null){cur.next.prev cur.next;//3、删除尾巴结点}else{last cur.prev;}}}cur cur.next;}} 3.9、清空双向链表clear 这里很多人会想到将head和last直接置为空不让head引用和last引用引用链表的节点即可但是head所引用的结点的后继结点还引用这个结点last所引用的结点的前驱结点还引用这个结点。所以这样的操作还是不能将链表清空必须要将双向链表的所有结点的指针域清空。 【代码思路】 【代码示例】 public void clear(){ListNode cur head;while(cur ! null){//将每个结点的指针域都置为空由于这里的数据域是基本数据类型不用置空但是当数据域当中为引用数据类型的时候数据域还要置空ListNode curNext cur.next;cur.prev null;cur.next null;cur curNext;}head null;//因为head和last作为引用还在引用链表的第一个结点和最后一个结点。last null;}
