益保网做推广网站吗?网络营销战略的内容

益保网做推广网站吗?,网络营销战略的内容,建网站论坛,哈尔滨网架公司1.双向链表2.模拟实现双向链表(一).构造节点类首先我们要明白#xff0c;双向链表的每一个节点都包含一个数据域和两个指针域#xff0c;一个指针域为前指针域#xff0c;表示指向当前节点的前一个节点#xff0c;一个指针域为后指针域#xff0c;表示指向当前节点的后一个…1.双向链表2.模拟实现双向链表(一).构造节点类首先我们要明白双向链表的每一个节点都包含一个数据域和两个指针域一个指针域为前指针域表示指向当前节点的前一个节点一个指针域为后指针域表示指向当前节点的后一个节点所以每一个节点都是一个完整的对象所以我们可以通过定义一个内部类static class ListNode{ public int val; public ListNode prev; public ListNode next; public ListNode(int val) { this.val val; } }(二).明确要写的功能要写的功能基本和单链表一样所以我依旧是将他们放到了一个接口中然后重写这些方法(三).创建头节点和尾节点public ListNode head; public ListNode tail;我们需要创建一个头节点来指向我们的第一个节点同时创建一个尾节点来指向我的双向链表的尾节点(四).头插法Override public void addFirst(int data) { ListNode nodenew ListNode(data); if (headnull){ headtailnode; }else{ node.nexthead; head.prevnode; headnode; } }首先我们要先创造一个节点然后判断head是否为空如果head为null说明整个链表就是空的也就是说该节点是整个链表的第一个节点此时该节点既是头节点也是尾节点如果head不为空那就让要插入的节点的next指向头节点同时将头节点的前驱设置为node最后将node节点设置为新的头节点(五).尾插法Override public void addLast(int data) { ListNode nodenew ListNode(data); if(headnull){ headtailnode; }else{ node.prevtail; tail.nextnode; tailnode; } }首先我们先判断链表是否为空即head是否为空当链表为不空的时候我们直接让tail指向的节点的后驱next指向node同时将node的前驱prev指向tail最后将新插入的节点node置为新的尾(六).任意位置插入,第一个数据节点为0号下标Override public void addIndex(int index, int data) { //首先判断index的合法性 try { ListNode nodenew ListNode(data); if_index(index); if (index0){ addFirst(data); return; } if (indexsize()){ addLast(data); return; } ListNode curhead; while (index--0){ //找到要插入位置的后一个节点 curcur.next; } //将要插入的节点的后驱改为cur node.nextcur; //将要插入的节点的前驱改为cur的前驱 node.prevcur.prev; //将原本cur的前一个节点的后驱改为node cur.prev.nextnode; //将cur的前驱改为node cur.prevnode; }catch (indexException e){ e.printStackTrace(); } }private void if_index(int index)throws indexException{ if (index0||indexsize()){ throw new indexException(index下标异常); } }首先我们先判断index的合法性同样我们可以用异常来解决这个问题如果不合法则直接抛出异常如果合法则我们需要找到要插入数据位置的后一个节点然后我们让cur.prev.next指向node我们要明白cur.prev表示cur的前一个节点让前一个节点的next指向node同时让node的前驱指向cur的前一个节点即node.prevcur.prev让node的后驱指向cur即node.nextcur.next让cur的前驱指向node即cur.prevnode上图就是经过我们插入之后的链表(七).查找是否包含关键字key是否在双链表当中Override public boolean contains(int key) { ListNode curhead; while(cur!null){ if(cur.valkey){ return true; } curcur.next; } return false; }这个方法相对于来说比较简单我们只需要遍历这个双向链表即可一旦值一样则返回ture但当链表循环完之后没有找到与key相等的值则返回false(八).删除第一次出现关键字为key的节点Override public void remove(int key) { ListNode curhead; while(cur!null){ if (cur.valkey){ //判断头节点的val值是否和key相同 if (curhead){ //head走向下一个节点 headhead.next; //如果head不为null那么说明这个链表不止1个头节点 //如果head为null那么此时说明这个链表就1个头节点那么如果执行head.prevnull就会报空指针异常 if (head!null){ head.prevnull; } }else{ //将要删除的节点的前一个节点的前驱改为要删除节点的后驱 cur.prev.nextcur.next; //判断cur节点是否是尾节点 if (cur.next!null){ cur.next.prevcur.prev; }else{ //如果是尾节点则需要tail节点往前挪一个位置 tailtail.prev; } } return; } curcur.next; } if (curnull){ System.out.println(没有你要删除的数据); return; } }首先如果我们找到了要删除的节点判断是否为头节点我们要先进行判断判断是不是头节点如果是头节点那么我们让头节点指向头节点的下一个节点同时我们要将新的头节点的前驱置为空但是当链表只有一个头节点的时候我们会发现问题此时head已经空了当我们再执行head.prevnull时就会报出空指针异常此时程序就会报错所以我们在判断cur是否是头节点的时候我们要再加一层判断既然已经执行了headhead.next了那么head已经指向了下一个节点所以我们只需要判断此时的head是否为空即可如果不为空执行head.prevnull判断其他节点如果不是头节点那么剩下的节点我们就可以平常处理了我们可以看上面的图我们可以看到假设我要删除cur这个节点我应该如何做1.让cur前一个节点的后驱指向cur的下一个节点首先我先要找到cur的前一个节点即cur.prev再找到他的后驱即cur.prev.next此时我们已经找到了cur的前一个节点的后驱然后我们再找到cur的下一个节点、即cur.next然后我们将cur前一个节点的后驱指向cur的下一个节点即cur.prev.nextcur.next2.让cur的下一个节点的前驱指向cur的前一个节点首先先要找到cur的下一个节点即cur.next然后找到他的前驱即cur.next.prev再找到cur的前一个节点即cur.prev让后一个节点的前驱指向cur的前一个节点即cur.next.prevcur.prev这样我们将该节点删除了但是还有一种情况如果要删除的节点是尾节点我们这样写代码还可以吗不可以为什么因为当cur是尾节点的时候我们确实可以执行cur.prev.nextcur.next但是cur.next.prevcur.prev还是否可行答案肯定是不行的因为想一想cur已经是尾节点了我执行cur.next.prev就会报空指针异常因为cur.next已经是空了空的前驱肯定是会报错的所以我们在进行删除其他节点的时候我们要进行判断判断是否是尾节点如果不是尾节点我们可以正常删除如果是尾节点则我们可以直接对tail进行处理直接让tailtail.prev即可让链表的尾指向链表的前一个节点(九).删除所有值为key的节点Override public void removeAllKey(int key) { ListNode curhead; while (cur!null){ if (cur.valkey){ if (curhead){ head head.next; if (headnull){ }else{ head.prevnull; } }else { cur.prev.nextcur.next; if (cur.nextnull){ tailtail.prev; }else{ cur.next.prevcur.prev; } } } curcur.next; } }这个方法和上一个第八个方法类似第八个方法我们只是删除了一个等于key的节点然后我们就return返回了这个是将所有等于key的节点都删除所以我们只需要将第八个代码中的return删掉即可(十).计算链表的长度Override public int size() { ListNode curhead; int count0; while(cur!null){ count; curcur.next; } return count; }这个相对于来说比较简单我们只需要比例链表然后统计个数即可(十一).打印链表中的值Override public void display() { ListNode curhead; while(cur!null){ System.out.print(cur.val ); curcur.next; } System.out.println(); }同样也是遍历链表然后打印每个节点的val值即可(十二).清除链表Override public void clear() { ListNode curhead; while(cur!null){ ListNode curNextcur.next; cur.nextnull; cur.prevnull; curcurNext; } headnull; tailnull; }清空链表我们需要把每个节点的next域和prev域都置为null在清空的同时我们要记录cur的下一个节点这样链表才能遍历起来最后我们要将head和tail也置为空3.链表的打印public static void main(String[] args) { LinkedListInteger listnew LinkedList(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); System.out.println(直接打印); System.out.println(list); System.out.println(for循环打印); for (int i 0; i list.size(); i) { System.out.print(list.get(i) ); } System.out.println(); System.out.println(for-each打印); for (Integer x:list) { System.out.print(x ); } System.out.println(); System.out.println(迭代器Iterator打印); //先判断是否有下一个如果有则打印下一个并往下走一步 IteratorInteger iteratorlist.iterator(); while(iterator.hasNext()){ System.out.print(iterator.next() ); } System.out.println(); System.out.println(迭代器ListIterator打印); ListIteratorInteger listIteratorlist.listIterator(); while (listIterator.hasNext()){ System.out.print(listIterator.next() ); } System.out.println(); System.out.println(迭代器ListIterator倒序打印); ListIteratorInteger listIterator1list.listIterator(list.size()); while (listIterator1.hasPrevious()){ System.out.print(listIterator1.previous() ); } }4.ArrayList和LinkedList的区别ArrayList底层是一个数组所以在存储空间上他们是连续的LinkedList是由一个一个的节点组成他们通过地址进行连接所以他们是在逻辑上是连续的在物理上不连续当ArrayList想要随机访问数据时我们可以直接通过下标进行访问所以时间复杂度是O(1)当LinkedList想要随机访问数据时需要从头开始遍历所以时间复杂度是O(N)当要插入数据时ArrayList需要移动数据效率很低LinkedList只需要修改引用的指向即可时间复杂度是O(1)同时LinkedList不需要进行扩容而ArrayList需要进行扩容