公司网站能自己做二维码,赣州网络问政,wordpress .po 在哪里,工程造价管理写在前: 本篇博客主要介绍关于双向链表的一些简答操作实现#xff0c;其中有有部分代码的实现和前两篇博客中的单向链表是相类似的。例如#xff1a;查找链表中是否包含关键字key、求链表的长度等。 其余的涉及到prev指向的需要特别注意#xff0c;区分和单向链表之间的差异…写在前: 本篇博客主要介绍关于双向链表的一些简答操作实现其中有有部分代码的实现和前两篇博客中的单向链表是相类似的。例如查找链表中是否包含关键字key、求链表的长度等。 其余的涉及到prev指向的需要特别注意区分和单向链表之间的差异。 目录
写在前:
0.首先定义一个结点
1.双向链表-头插法
2.双向链表-尾插法
3.双向链表-任意位置插
4.打印双向链表
5.求双向链表的长度
6.找到双向链表中下标为index的元素
7.查找双向链表中是否包含关键字key
8.删除双向链表中第一个值为key的结点
9.删除双向链表中所有值为key的结点
10.清空双向链表 0.首先定义一个结点 实现双向链表首先需要自己定义一个结点结点中包含三个域val、prev、next; 定义头结点的引用head 定义尾结点的引用last 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;//代表当前链表尾结点的引用
1.双向链表-头插法 public void addFirst(int data){ListNode node new ListNode(data);if(head null){head node;last node;}else {node.next head;head.prev node;head node;}}
2.双向链表-尾插法 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;}}3.双向链表-任意位置插 public void addIndex(int index,int data){//首先判断插入位置的合法性if(index 0 || index size()){throw new ListIndexOutOfException();}//当下标为0-头插法if(index 0){addFirst(data);return;}//当下标为size尾插法if(index size()){addLast(data);return;}//排除其他情况--正常插入//定义结点cur指向需要插入到的index位置ListNode cur findIndex(index);ListNode node new ListNode(data);cur.prev.next node;node.prev cur.prev;node.next cur;cur.prev node;}
4.打印双向链表 public void display(){ListNode cur head;while(cur ! null){System.out.print(cur.val );cur cur.next;}System.out.println();}
5.求双向链表的长度 public int size(){int len 0;ListNode cur head;while(cur ! null){len;cur cur.next;}return len;}
6.找到双向链表中下标为index的元素 private ListNode findIndex(int index){ListNode cur head;while (index ! 0){cur cur.next;index--;}return cur;}
7.查找双向链表中是否包含关键字key public boolean contains(int key){ListNode cur head;while(cur ! null){if(cur.val key){return true;}cur cur.next;}return false;}
8.删除双向链表中第一个值为key的结点 public void remove(int key){ListNode cur head;while (cur ! null){//判断cur的值和所要删除的值是否相同//相同if(cur.val key){//这里需要分多种情况//1.删除的是头结点if(cur head){head head.next;//如果链表中有多个结点则需要将前head.prev置空if(head ! null){head.prev null;}}else {//2.删除的不是头结点//删除的是尾巴结点if(cur.next null){last last.prev;cur.prev.next null;}else {//删除的是中间结点cur.prev.next cur.next;cur.next.prev cur.prev;}}return;//不相同}cur cur.next;}}
9.删除双向链表中所有值为key的结点 public void removeAllKey(int key){ListNode cur head;while (cur ! null){//判断cur的值和所要删除的值是否相同//相同if(cur.val key){//这里需要分多种情况//1.删除的是头结点if(cur head){head head.next;//如果链表中有多个结点则需要将前head.prev置空if(head ! null){head.prev null;}}else {//2.删除的不是头结点//删除的是尾巴结点if(cur.next null){last last.prev;cur.prev.next null;}else {//删除的是中间结点cur.prev.next cur.next;cur.next.prev cur.prev;}}//不相同}cur cur.next;}}
10.清空双向链表 public void clear(){ListNode cur head;while (cur ! null){ListNode curNext cur.next;cur.next null;cur.prev null;cur curNext;}head null;last null;}
