java中的单向链表和双向链表,双向循环链表java

  java中的单向链表和双向链表,双向循环链表java

  00-1010前言1。理解双向链表2。添加、删除和检查双向链表1。在索引位置2插入头部和尾部。修改3。询问4。删除索引位置的节点头尾删除第一个带val的节点删除所有带val的汇总值。

  00-1010我们之前学过的单链表,默认情况下只能从链表头遍历到链表尾,这种情况太少见了,在实践中也很有限;对于链表中的任何一个节点,双向链表都可以通过这个节点向前或向后遍历。双向链表在实际工程中应用广泛,使用链表结构是首选。

  00-1010单向链表不仅保存当前节点值,还保存下一个节点的地址。

  双向链表不仅保存当前节点的值,还保存上一个节点的地址和下一个节点的地址。

  定义一个双向链表的结点类:

  在节点中,不仅要保存当前节点的值,还要保存该节点的前任节点的地址和继任节点的地址。

  class double node { public double node next;DoubleNode prevint val双节点尾部;public double node(){ } public double node(int val){ this . val=val;} public double node(double node prev,int val,double node tail){ this . prev=prev;this.val=valthis.tail=tail} }定义一个双向链表类:

  可以是从前到后,也可以是从后到前,所以在这个类中,保存的是第一个节点和最后一个节点的值。

  public class doublelinked list { private int size;私有DoubleNode头;私有DoubleNode尾部;}

  

目录

 

  

前言

 

  00-1010在当前链表的头中插入一个节点,使当前链表的头节点头前驱指向要插入的节点,然后节点的后继指向头,然后设head=node,设node成为链表的头节点。

  代码如下:

  /* * * prefix */public void add first(intval){ double node node=new double node(val);if(head==null){ head=tail=node;} else { node.next=headhead.prev=node头=节点;}大小;}

  00-1010与头插入相同,只是它被插入到链表的末尾。

  代码如下:

  public void add last(int val){ double node node=new double node(val);if(head==null){ head=tail=node;} else { tail.next=nodenode.prev=tail尾=节点;}大小;}

  

一、认识双向链表

在索引为index的位置插入值为val的节点:

 

  插入还是要找前驱节点,但是用双向链表找前驱节点比单向链表灵活多了,单向链表只能从头开始。

  走到尾,假如此时有100个节点,要在索引为98的位置插入节点,那么双向链表就可以从尾结点开始找,会方便很多

  如何判断从前向后找,还是从后向前找?

  1.index < size / 2 – >从前向后找,插入位置在前半部分2.index > size / 2 – >从后向前找,插入位置在后半部分

 

  代码如下:

  

/** * 在index位置插入 * @param index * @param val */ public void add(int index,int val){ DoubleNode cur = new DoubleNode(val); if (index < 0 index > size){ System.err.println("add index illegal"); return; }else{ if (index == 0){addFirst(val);} else if (index == size){addLast(val);} else{ DoubleNode prev = node(index-1); DoubleNode next = prev.next; cur.next = next; next.prev = cur; prev.next = cur; cur.prev = prev; } } size++; }/** * 根据索引值找到对应的结点 * @param index * @return */ private DoubleNode node(int index){ DoubleNode x = null; if (index < size/2){ x = head; for (int i = 0; i < index; i++) { x = x.next; } }else{ x = tail; for (int i = size - 1; i > index ; i--) { x = x.prev; } } return x; }

 

  

2.修改

代码如下:

 

  

/** * 修改双向链表index位置的结点值为newVal */ public int set(int index,int newVal){ DoubleNode dummyHead = new DoubleNode(); dummyHead.next = head; DoubleNode prev = dummyHead; DoubleNode cur = prev.next; if (index < 0 index > size - 1){ System.err.println("set index illegal"); }else{ for (int i = 0; i < index; i++) { prev = prev.next; cur = cur.next; } } int oldVal = cur.val; cur.val = newVal; return oldVal; }

 

  

3.查询

代码如下:

 

  

 /** * 查询index位置的结点值 */ public int get(int index){ DoubleNode dummyHead = new DoubleNode(); dummyHead.next = head; DoubleNode prev = dummyHead; DoubleNode cur = prev.next; if (index < 0 index > size - 1){ System.err.println("get index illegal"); }else{ for (int i = 0; i < index; i++) { prev = prev.next; cur = cur.next; } } return cur.val; }

 

  

4.删除

 

  

删除index位置的节点

代码如下:

 

  

//删除链表index位置的结点 public void removeIndex(int index){ if (index < 0 index > size - 1){ System.err.println("remove index illegal"); return; } DoubleNode cur = node(index); unlink(cur); } /** * 删除当前双向链表的node结点 * 分治法 * @param node */ private void unlink (DoubleNode node){ DoubleNode prev = node.prev; DoubleNode successor = node.next; //1.先处理node的前半部分 if (prev == null){ head = successor; }else{ //前驱不为空的情况 prev.next = successor; node.prev = null; } if (successor == null){ tail = prev; }else{ successor.prev = prev; node.next = null; } size--; }

 

  

头删

调用删除任意位置的节点即可

 

  代码如下:

  

//头删 public void removeFirst(){ removeIndex(0); }

 

  

尾删

调用删除任意位置的节点即可

 

  代码如下:

  

//尾删 public void removeLast(){ removeIndex(size - 1); }

 

  

删除第一个值为val的节点

代码如下:

 

  

//删除第一个值为val的结点 public void removeValOnce(int val){ if (head == null){ return; } for (DoubleNode x = head;x != null;x = x.next){ if (x.val == val){ unlink(x); break; } } } /** * 删除当前双向链表的node结点 * 分治法 * @param node */ private void unlink (DoubleNode node){ DoubleNode prev = node.prev; DoubleNode successor = node.next; //1.先处理node的前半部分 if (prev == null){ head = successor; }else{ //前驱不为空的情况 prev.next = successor; node.prev = null; } if (successor == null){ tail = prev; }else{ successor.prev = prev; node.next = null; } size--; }

 

  

删除所有值为val的值

代码如下:

 

  

//删除链表中所有值为val的结点 public void removeAllVal(int val){ for (DoubleNode x = head;x != null;){ if (x.val == val){ //暂存一下x的下一个结点 DoubleNode next = x.next; unlink(x); x = next; }else{ //val不是待删除的元素 x = x.next; } } } /** * 删除当前双向链表的node结点 * 分治法 * @param node */ private void unlink (DoubleNode node){ DoubleNode prev = node.prev; DoubleNode successor = node.next; //1.先处理node的前半部分 if (prev == null){ head = successor; }else{ //前驱不为空的情况 prev.next = successor; node.prev = null; } if (successor == null){ tail = prev; }else{ successor.prev = prev; node.next = null; } size--; }

 

  

总结

本篇博客带大家了解了一下什么是双向链表,和单链表有什么区别,已经双向链表的一些基本的增删改查的操作,

 

  到此这篇关于Java双向链表的操作的文章就介绍到这了,更多相关Java双向链表内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT!

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: