大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > Java实现双向链表

Java实现双向链表

关键词:Java双向链表Java实现双向链表  阅读(516) 赞(19)

[摘要]本文主要是对Java实现双向链表的讲解,希望对大家学习Java实现双向链表有所帮助。

  自定异常类:


  Java代码


  public class MyException extends Exception {


  public MyException(){};


  public MyException(String msg){


  super(msg);


  }


  }


  链表结点对像:


  Java代码


  public class Node {


  public Node previou=null;//前结点指针


  public Node next=null;   //后结点指针


  public Object value;//结点值


  Node(Object value){


  this.value=value;


  }


  }


  链表对像:


  Java代码


  public class DoubleLinked {


  private Node head;//链表头


  DoubleLinked(){


  }


  /**


  * 判断是否还有下一个结点,没有则为链表的尾结点


  * @param node


  * @return


  */


  public boolean hasNext(Node node){


  if(node.next==null)


  return false;


  return true;


  }

 


  /**


  * 判断是否有上一个结点,没有则为链表的头结点


  * @param node


  * @return


  */


  public boolean hasPrev(Node node){


  if(node.previou==null)


  return false;


  return true;


  }


  /**


  * 获取链表头元素


  * @return


  * @throws MyException


  */


  public Node getHead() throws MyException{


  if(head==null){


  throw new MyException("链表为空");


  }


  return head;


  }


  /**


  * 获取上一个接点


  * @param node


  * @return


  */


  public Node getPrev(Node node){


  return node.previou;


  }


  /**


  * 获取下一个结点


  * @param node


  * @return


  */


  public Node getNext(Node node){


  return node.next;


  }


  /**


  * 根据索引获取结点


  * @param index:结点索引


  * @return


  * @throws MyException


  */


  public Node getNode(int index) throws MyException{


  Node curNode=null;


  Node next=null;


  Node node=null;


  if(head==null){


  throw new MyException("链表为空");


  }else{


  curNode=head;


  for(int i=0;i<index;i++){


  if(curNode==null){


  throw new MyException("你要获取的元素索引大于链表长度");


  }else{


  node=curNode;


  if(hasNext(curNode)){


  next=curNode.next;


  curNode=next;


  }else{


  curNode=null;


  }


  }


  }


  }


  return node;


  }

 


  /**


  * 获取最后一个结点


  * @return


  * @throws MyException


  */


  public Node getLast() throws MyException{


  Node curNode=null;


  Node next=null;


  Node last=null;


  boolean flag=true;


  if(head==null){


  throw new MyException("链表为空");


  }else{


  curNode=head;


  while(flag){


  if(hasNext(curNode)){


  next=curNode.next;


  curNode=next;


  }else{


  last=curNode;


  flag=false;


  }


  }


  }


  return last;


  }


  /**


  * 在链表头添加新结点


  * @param node


  */


  public void addHead(Node node){


  if(head==null){


  head=node;


  }else{


  node.next=head;


  head.previou=node;


  head=node;


  }


  }


  /**


  * 在链表末尾处添加新结点


  * @param node


  * @throws MyException


  */


  public void addLast(Node node) throws MyException{


  if(head==null){


  head=node;


  }else{


  Node last=this.getLast();


  last.next=node;


  node.previou=last;


  }


  }


  /**


  * 在链表中间插入新结点


  * @param node


  * @throws MyException


  */


  public void insertNode(int index,Node node) throws MyException{


  Node indexNode=this.getNode(index);


  Node prev=indexNode.previou;


  prev.next=node;


  node.previou=prev;


  node.next=indexNode;


  indexNode.previou=node;


  }

 


  /**


  * 删除链表头结点


  * @return


  * @throws MyException


  */


  public Node deleteHead() throws MyException{


  Node head=this.getHead();


  if(hasNext(head)){


  Node next=head.next;


  this.head=next;


  next.previou=null;


  }


  return head;


  }


  /**


  * 删除链表的最后一个结点


  * @return


  * @throws MyException


  */


  public Node deleteLast() throws MyException{


  Node last=this.getLast();


  Node prev=last.previou;


  if(prev==null){


  this.head=null;


  }else{


  prev.next=null;


  }


  return last;


  }


  /**


  * 根据索引删除链表结点


  * @param index


  * @return


  * @throws MyException


  */


  public Node deleteNode(int index) throws MyException{


  Node node=this.getNode(index);


  Node prev=node.previou;


  Node next=node.next;


  if(prev==null && next!=null){


  this.head=next;


  next.previou=null;


  }


  if(prev!=null && next==null){


  prev.next=null;


  }


  if(prev==null && next==null){


  this.head=null;


  }


  if(prev!=null && next!=null){


  prev.next=next;


  next.previou=prev;


  }


  return node;


  }


  } :!:



相关评论