温州网站建设培训学校,wordpress如何下载,网络营销典型案例有哪些,东阿网站建设价格双向链表 一.双向链表二.创建MyListCode类实现双向链表创建一.AddFirst创建#xff08;头插法#xff09;二.AddLast创建#xff08;尾叉法#xff09;三.size四.remove(指定任意节点的首位删除)五.removeAll(包含任意属性值的所有删除)六.AddIndex(给任意位置添加一个节点… 双向链表 一.双向链表二.创建MyListCode类实现双向链表创建一.AddFirst创建头插法二.AddLast创建尾叉法三.size四.remove(指定任意节点的首位删除)五.removeAll(包含任意属性值的所有删除)六.AddIndex(给任意位置添加一个节点)七.contains(无)八.partition区分链表的大小范围九.display(打印) 接口类MyListNode整体代码Test测试类代码 一.双向链表
单向链表从头部开始我们的每一个节点指向后驱的节点。 此处为单向链表 单向链表
双向链表是相互指向前驱以及后驱的链表 前驱链表我们需要在我们的MyListCode内部类中在定义一个previous来接收每一个前驱的地址 想要删除任意节点可以直接通过访问下一个节点使其prev获取想要删除的上一个节点然后将想要删除的上一个节点.next获取到被删除对象下一个节点的指向 这里我们可以模拟实现MyListCode类中的一些方法入头插法、尾叉法、任意位置插入节点、指定元素删除含有该元素的第一个节点、指定元素删除含有该元素的所有节点等…
二.创建MyListCode类实现双向链表创建
public class MyListNode implements IList {static class Node{public int val;//获取的后一个节点public Node next;//获取的前一个节点public Node prev;public Node(int val) {this.val val;}}//始终在第一个节点public Node head;//指向最后一个节点public Node last;}一.AddFirst创建头插法
这里当头部为null没有头部和尾巴我们将新节点作为头和尾如果不为null将每次产生的新节点对象放到头部头部的pre与新节点相连头部更新最新节点 Overridepublic void addFirst(int data) {Node nodenew Node(data);if(this.headnull){//head指向头部last指向尾巴this.headnode;this.lastnode;}else{//不为空将新节点插入头部并将头部的pre置为新节点最后更新头部位置node.nextthis.head;this.head.prevnode;this.headnode;}}
二.AddLast创建尾叉法
这里考虑的是当head为空时我们的头和尾巴都将获取新的节点如果不为空我们只需要移动last将last的下一个节点获取到新的节点新的节点pre指向last最后last走向新节点得到尾巴 Overridepublic void addLast(int data) {Node nodenew Node(data);if(this.headnull){this.headnode;this.lastnode;}else {this.last.next node;node.prev last;lastnode;}}三.size
从头部开始遍历或者尾部开始遍历 Overridepublic int size() {if(this.headnull){return 0;}Node curthis.head;int count0;while(cur!null){count;curcur.next;}return count;}Overridepublic void display() {Node curthis.head;while(cur!null){System.out.print(cur.val );curcur.next;}System.out.println();}
四.remove(指定任意节点的首位删除)
首先判断如果头部值为空说明没有节点头部的下一个节点如果为key值则直接返回key因为这里只是删除一个所以不考虑多个带key的节点然后遍历如果最后一个节点为key它的下一个节点为null则将双向节点置为null如果不为null就删除这个节点 Overridepublic void remove(int key) {if (this.head null) {return;}if(this.head.valkey){//头节点为key将其更换为后驱节点将后驱节点的prev置空this.headthis.head.next;this.head.prevnull;return;}Node curthis.head.next;while(cur!null){if(cur.valkey){//最后一个节点为key将前驱的下一项置空并将cur的pre置空if(cur.nextnull){cur.prev.nextnull;cur.prevnull;return;}else{//不是最后一个节点将前驱节的下一节点为当前节点下一项//当前节点的下一项的前驱为当前项的前驱cur.prev.nextcur.next;cur.next.prevcur.prev;return;}}curcur.next;}}五.removeAll(包含任意属性值的所有删除)
首先判断是否头部为空 判断最后一个last值是否时key是key将双节点置空 然后判断key值将key值在节点中删除 最后判断头节点是否为key并将头节点置空
Overridepublic void removeAll(int key) {if(this.headnull){return;}if(this.last.valkey) {//如果最后一项的值为key,将last前一项保留下来最后赋值给last使其尾部更新Node prethis.last.prev;this.last.prev.next null;this.last.prev null;this.lastpre;}Node curthis.head.next;while(cur!null){//cur的值如果为key清理该节点指向if(cur.valkey){cur.prev.nextcur.next;cur.next.prevcur.prev;}curcur.next;}//最后判断head的值是否是keyif(this.head.valkey){this.headthis.head.next;}//如果head有数据将head头的前节点置空if(this.head!null){this.head.prevnull;}}六.AddIndex(给任意位置添加一个节点)
首先判断头部是否为空 判断该坐标是否合法如果该坐标在0或者在尾巴则头插法和尾叉法 将给的坐标作为循环条件节点开始走跳出循环后改节点位置就是要添加的位置 首先要把改节点的坐标向后移动一位插入其中间 单链表的话将cur先指向后一个节点在指向前一个节点 Overridepublic void addIndex(int index,int data)throws RuntimeException {if(this.headnull){return;}try {if(index0||indexsize()){throw new RuntimeException(错误范围size());}}catch (RuntimeException e){e.printStackTrace();}if(index0){addFirst(data);return;}if(indexsize()){addLast(data);return;}Node nodenew Node(data);Node curthis.head;while(index0){//出来后就是要插入的范围curcur.next;index--;}//在任意位置新增一个节点node.nextcur;node.prevcur.prev;cur.prevnode;node.prev.nextnode;return ;}七.contains(无) Overridepublic boolean contains(int key) {if(this.headnull){return false;}Node curthis.head;while(cur!null){if(cur.valkey){return true;}curcur.next;}return false;}八.partition区分链表的大小范围 Overridepublic Node partition(Node node,int x) {if (node null) {return null;}Node cur node;Node minnull;Node minEndnull;Node maxnull;Node maxEndnull;while (cur ! null) {if(cur.valx){if(minnull){mincur;minEndcur;}else{minEnd.nextcur;minEndminEnd.next;}}else{if(maxnull){maxcur;maxEndcur;}else{maxEnd.nextcur;maxEndmaxEnd.next;}}cur cur.next;}if(minnull){return max;}if(maxEnd!null){maxEnd.nextnull;}minEnd.nextmax;return min;}
}
九.display(打印)
Overridepublic void display() {Node curthis.head;while(cur!null){System.out.print(cur.val );curcur.next;}System.out.println();}接口类
public interface IList {public void display();public int size();public void addFirst(int data);//新增一个节点放到头部public void addLast(int data);//新增一个节点放到尾部public void remove(int key);//删除第一个val值为key的节点public void removeAll(int key);//删除所有val值的节点public void addIndex(int index,int data);//在任意一个位置放入一个节点public boolean contains(int key);//是否包含key数值这个节点public MyListNode.Node partition(MyListNode.Node node,int x);//指定一个值将数值小的放在前将数值大的放在后
}
MyListNode整体代码
import java.util.List;public class MyListNode implements IList {static class Node{public int val;public Node next;public Node prev;public Node(int val) {this.val val;}}//始终在第一个节点public Node head;//指向最后一个节点public Node last;Overridepublic void addFirst(int data) {Node nodenew Node(data);if(this.headnull){this.headnode;this.lastnode;}else{node.nextthis.head;this.head.prevnode;this.headnode;}}Overridepublic void addLast(int data) {Node nodenew Node(data);if(this.headnull){this.headnode;this.lastnode;}else {this.last.next node;node.prev last;lastnode;}}Overridepublic int size() {if(this.headnull){return 0;}Node curthis.head;int count0;while(cur!null){count;curcur.next;}return count;}public int size2(){if(this.headnull){return 0;}Node endthis.last;int count0;while(end!null){count;endend.prev;}return count;}Overridepublic void display() {Node curthis.head;while(cur!null){System.out.print(cur.val );curcur.next;}System.out.println();}public void display2(){Node curthis.last;while(cur!null){System.out.print(cur.val );curcur.prev;}System.out.println();}Overridepublic void remove(int key) {if (this.head null) {return;}if(this.head.valkey){//头节点为key将其更换为后驱节点将后驱节点的prev置空this.headthis.head.next;this.head.prevnull;return;}Node curthis.head.next;while(cur!null){if(cur.valkey){//最后一个节点为key将前驱的下一项置空并将cur的pre置空if(cur.nextnull){cur.prev.nextnull;cur.prevnull;return;}else{//不是最后一个节点将前驱节的下一节点为当前节点下一项//当前节点的下一项的前驱为当前项的前驱cur.prev.nextcur.next;cur.next.prevcur.prev;return;}}curcur.next;}}Overridepublic void removeAll(int key) {if(this.headnull){return;}if(this.last.valkey) {//如果最后一项的值为key,将last前一项保留下来最后赋值给last使其尾部更新Node prethis.last.prev;this.last.prev.next null;this.last.prev null;this.lastpre;}Node curthis.head.next;while(cur!null){//cur的值如果为key清理该节点指向if(cur.valkey){cur.prev.nextcur.next;cur.next.prevcur.prev;}curcur.next;}//最后判断head的值是否是keyif(this.head.valkey){this.headthis.head.next;}//如果head有数据将head头的前节点置空if(this.head!null){this.head.prevnull;}}Overridepublic void addIndex(int index,int data)throws RuntimeException {if(this.headnull){return;}if(index0){addFirst(data);return;}if(indexsize()){addLast(data);return;}try {if(index0||indexsize()){throw new RuntimeException(错误范围size());}}catch (RuntimeException e){e.printStackTrace();}Node nodenew Node(data);Node curthis.head;while(index0){//出来后就是要插入的范围curcur.next;index--;}//在任意位置新增一个节点node.nextcur;node.prevcur.prev;cur.prevnode;node.prev.nextnode;return ;}Overridepublic boolean contains(int key) {if(this.headnull){return false;}Node curthis.head;while(cur!null){if(cur.valkey){return true;}curcur.next;}return false;}Overridepublic Node partition(Node node,int x) {if (node null) {return null;}Node cur node;Node minnull;Node minEndnull;Node maxnull;Node maxEndnull;while (cur ! null) {if(cur.valx){if(minnull){mincur;minEndcur;}else{minEnd.nextcur;minEndminEnd.next;}}else{if(maxnull){maxcur;maxEndcur;}else{maxEnd.nextcur;maxEndmaxEnd.next;}}cur cur.next;}if(minnull){return max;}if(maxEnd!null){maxEnd.nextnull;}minEnd.nextmax;return min;}
}
Test测试类代码
public class Test {public static void main(String[] args) {MyListNode myListNodenew MyListNode();myListNode.addLast(3);myListNode.addLast(5);myListNode.addLast(7);myListNode.removeAll(6);
// System.out.println(myListNode.last.val);
// myListNode.display();myListNode.addIndex(1,9);System.out.println(myListNode.contains(3));myListNode.display();int len1 myListNode.size();int len2 myListNode.size();System.out.println(len1size);System.out.println(len2size1);MyListNode myListNode1new MyListNode();myListNode1.addLast(3);myListNode1.addLast(3);myListNode1.addLast(8);myListNode1.addLast(9);myListNode1.addLast(19);myListNode1.addLast(3);myListNode1.display();myListNode1.display2();myListNode1.partition(myListNode1.head,5);myListNode1.display();myListNode1.display2();}
}
写的也有很多不好的地方希望大佬们多多指点谢谢祝大家开心快乐
