数据结构Java实现：循环链表和双向链表( 二 ) _数据结构

文章插图

如上所示，删除节点必须先找到其前驱节点，在单链表中是不会记录元素的前驱节点的，所以必须从头开始遍历链表，直到找到目标节点的前驱节点，时间复杂度为 O(n) 。
如果是双向链表的结构，每一个节点都会记录其前驱节点，可直接获取，所以此时的时间复杂度为 O(1) 。

文章插图

搞清楚了双向链表的概念，接下来我们用 Java 来实现双向链表的结构。

package com.southwind.link;public class DoubleNode { //数据 public Object data; //下一个节点 public DoubleNode next; //上一个节点 public DoubleNode previous; public DoubleNode(Object data){ this.data = https://www.isolves.com/it/cxkf/yy/JAVA/2019-07-08/data; }}【数据结构Java实现：循环链表和双向链表】package com.southwind.link;public class DoubleLinkedList { public int size; public DoubleNode head; /** * 添加元素 * @param obj * @return */ public DoubleNode add(Object obj){ DoubleNode newNode = new DoubleNode(obj); if(size == 0){ head = newNode; }else{ DoubleNode target = head; while(target.next!=null){ target = target.next; } target.next = newNode; newNode.previous = target; } size++; return newNode; } /** * 在指定位置插入元素 * @return */ public DoubleNode insert(int index,Object obj){ if(index >= size){ return null; } DoubleNode newNode = new DoubleNode(obj); if(index == 0){ newNode.next = head; head.previous = newNode; head = newNode; }else{ DoubleNode target = head; int pos = 0; while(pos != index){ target = target.next; pos++; } newNode.previous = target.previous; newNode.previous.next = newNode; newNode.next = target; } size++; return newNode; } /** * 删除链表头部元素 * @return */ public DoubleNode removeHead(){ if(size > 0){ DoubleNode node = head; head = head.next; size--; return node; }else{ return null; } } /** * 删除指定位置元素 * @return */ public DoubleNode remove(int index){ if(index >= size){ return null; } DoubleNode result = head; if(index == 0){ DoubleNode node = head; head = head.next; }else{ DoubleNode target = head; int pos = 0; while(pos != index){ target = target.next; pos++; } target.previous.next = target.next; } size--; return result; } /** * 删除指定元素 * @return */ public DoubleNode removeNode(Object obj){ DoubleNode target = head; if(obj.equals(target.data)){ DoubleNode node = head; head = head.next; size--; }else{ while(target.next!=null){ if(obj.equals(target.data)){ target.previous.next = target.next; size--; break; } target = target.next; } } return target; } /** * 返回指定元素 * @return */ public DoubleNode findNode(Object obj){ DoubleNode target = head; while(target.next!=null){ if(obj.equals(target.data)){ return target; }else{ target = target.next; } } if(target.next==null && obj.equals(target.data)){ return target; } return null; } /** * 输出链表元素 */ public void show(){ if(size > 0){ DoubleNode node = head; int length = size; System.out.print("["); while(length > 0){ if(length == 1){ System.out.print(node.data); }else{ System.out.print(node.data+","); } node = node.next; length--; } System.out.println("]"); }else{ System.out.println("[]"); } }}

数据结构Java实现：循环链表和双向链表( 二 )

推荐阅读

小青柑图片高清,小青柑冲泡方法

「还是沛公」汽车抵押贷款能做吗？看看他们都是怎么操作的

封面新闻|30秒｜尤文意甲9连冠 C罗追平队史进球纪录

回应|星巴克被曝店员不收硬币，网友：拒收人民币违法！

农的偏旁部首是什么　能力的能字它的部首是什么了?

汇集扬州|爆火！扬州90后“鹅二代”帮父母直播带货

『彩霞讲故事』派军舰威逼这个国家，迫使此国道歉，并赔偿3亿，大清最后雄威

普洱中的霸王,老班章

教师|毕业想当老师，那专业要选好，这8个专业当教师比例较高，值得报

【】孕妇吃番茄对胎儿好吗

北京有哪些live house有rapper的演出

#车与生活#惊人2.0L/100km圈粉无数，探岳GTE树立大众插混市场新标杆

腊肉■它属于低脂菜，隔三差五吃，清爽可口，大肚腩消失，腰围小2公分

芒果怎么看好不好吃芒果怎么挑选好吃的

央视新闻|全球抗生素耐药性行动基金启动，10亿美元注资抗生素研发

不一样的618 京东星链带动线下门店客流大增30%

汽车电瓶没电了怎么办？4招教您自救不求拖车！

映世窗|画一张图3万6，凭什么还有人排队给他们送钱？

[鲁网青岛新闻中心]青岛市应急局与青岛海纳云科技控股有限公司签署战略合作协议

二级建造师一年考几次？