自己建设一个网站需要多少钱,南充市房产网,网络系统运维,湖南官网网站推广软件引入
我们之前学的单向链表有什么缺点呢#xff1f; 缺点#xff1a;后一个节点无法看到前一个节点的内容
那我们就多设置一个格子prev用来存放前面一个节点的地址#xff0c;第一个节点的prev存最后一个节点的地址#xff08;一般是null#xff09;
这样一个无头双向…引入
我们之前学的单向链表有什么缺点呢 缺点后一个节点无法看到前一个节点的内容
那我们就多设置一个格子prev用来存放前面一个节点的地址第一个节点的prev存最后一个节点的地址一般是null
这样一个无头双向链表就造好啦
老规矩手搓双链表
初始
和单链表一样我们也是实现IList接口的方法
初始化差不多可以去看我前面的博客
数据结构链表1_cx努力编程中的博客-CSDN博客 跟前驱没关系的函数我先放进来 Overridepublic boolean contains(int key) {ListNode cur this.head;while(cur ! null){if(cur.val key){return true;}cur cur.next;}return false;}Overridepublic int size() {int count 0;ListNode cur this.head;while (cur ! null) {count;cur cur.next;}return count;}Overridepublic void display() {ListNode cur head;while(cur ! null){System.out.print(cur.val );cur cur.next;}System.out.println();}
插入
头插法
实例化一个node如果只有一个节点的话就把head和last都放在这个节点的下面 node.next head;
head.prev node;
head node;//把head的位置放到node这里 public void addFirst(int data) {ListNode node new ListNode(data);if(head null){head node;last node;}else{node.next this.head;head.prev node;head node;}}
尾插法
跟单链表不一样的是双链表有last所以时间复杂度是O(1) Overridepublic void addLast(int data) {ListNode node new ListNode(data);if(head null){head node;last node;}else{last.next node;node.prev head;last node;}}
指定位置插入
比如我们实例化一个节点想要将其插入到1和2之间 那么我们就要将cur移动到2的位置走index步
这个cur的前驱节点1的next就是这个新节点的地址
node.next cur
cur.prev.next node(0x123)
node.prev cur.prev
cur.prev node 代码 Overridepublic void addIndex(int index, int data) {//检查index是否异常int len size();if(index 0 || index len){System.out.println(异常索引index);return;}if(index 0){//头插法addFirst(data);return;}if(index len){//尾插法addLast(data);return;}ListNode cur findIndex(index);ListNode node new ListNode(data);node.next cur;cur.prev.next node;node.prev cur.prev;cur.prev node;} 删除
假如删除中间45这个节点先让cur走到这个节点再让45前一个节点的地址等于45后一个节点地址让45后一个节点的前驱等于45前一个节点的地址 但是假如要删除的是13这个节点头节点那么cur.prev.next cur.next这行代码有问题
所以我们这么干直接把头节点的后一个节点的前驱prev置为null就行了 if(cur head){head head.next;head.prev null;
假如要删除的是56这个节点尾节点那么cur.next.prev cur.prev这行代码有问题
那我们这么干直接把尾节点的前一个节点的next置为null就行了 cur.prev.next cur.next;
last last.prev;
我们发现尾节点的删除和中间节点删除有一行代码是一样的
cur.prev.next cur.next;
我们可以把它作为这二者的公用代码 cur.prev.next cur.next;if(cur.next null){last last.prev;}else {cur.next.prev cur.prev;}
其实这段代码还存在问题
当链表只有一个元素的时候 head head.next //这行代码一走完表明head此时已经是空的了下一行代码还说head.prev就根本不存在注意head.prev null是赋值操作首先你得有head.prev才能进行赋值
更改代码 整个remove代码 Overridepublic void remove(int key) {ListNode cur head;while(cur ! null){if(cur.val key){if(cur head){head head.next;if(head null){last null;}else{head.prev null;}}else {cur.prev.next cur.next;if(cur.next null){last last.prev;}else {cur.next.prev cur.prev;}}return;}else{cur cur.next;}}}
删除指定值的所有相同值的节点
跟上面的代码很像区别就是删除之后不要return让cur继续往下走 Overridepublic void removeAllKey(int key) {ListNode cur head;while(cur ! null){if(cur.val key) {if (cur head) {head head.next;if (head null) {last null;} else {head.prev null;}} else {cur.prev.next cur.next;if (cur.next null) {last last.prev;} else {cur.next.prev cur.prev;}}}cur cur.next;}}
清除链表
暴力方法
head null; last null;
细致方法
定义一个cur遍历整个链表每到一个节点就把prev和next都置为空 Overridepublic void clear() {ListNode cur head;while(cur!null){ListNode curNext cur.next;//防止将这个节点的next置为空之后cur没办法继续遍历cur.prev null;cur.next null;cur curNext;}} 总结
ArrayList和LinkedList的区别是
如果是经常根据下标查找的使用顺序表ArrayList或者数组
如果经常进行插入和删除操作的就使用链表LinkedList
