Java实现双向循环链表

双向循环链表定义

相比于单链表，有两个指针，next指针指向下一个结点,prior指针指向上一个结点,最后一个结点的next指针指向头结点，头结点的prior指针指向最后一个结点

代码实现：

我们对加以修改

package algorithm.datastructure.doublelinkedlist;
import java.util.nosuchelementexception;

/*
* 双向循环链表
* 两个指针，next指针指向下一个结点,prior指针指向上一个结点,最后一个结点的next指针指向头结点，
* 头结点的prior指针指向最后一个结点
* */
public class linkedlist {
  private node head;//头节点
  private int size;//链表长度

  static private class node{
    private int data;//数据
    private node next;//下一个结点
    private node prior;//上一个结点

    public node(){
    }
    public node(int data){
      this.data=data;
    }
    private node(int data,node next){
      this.data=data;
      this.next=next;
    }

    public node(node prior,int data,node next){
      this.prior=prior;
      this.data=data;
      this.next=next;
    }

  }

  //初始化空链表
  public linkedlist(){
    //head=null;
  }

  //添加元素
  public boolean add(int element){
    linklast(element);
    return true;
  }

  //在某个位置之前添加元素
  public boolean add(int index,integer element){
    checkpositionindex(index);
    if (index==size){
      linklast(element);
    } else {
      linkbefore(element,node(index));
    }

    return true;
  }

  //根据下标获取元素
  public int get(int index){
    checkelementindex(index);
    return node(index).data;
  }
  //获取第一个元素
  public integer getfirst(){
    node f=head;
    if (f==null){
      throw new nosuchelementexception();
    } else {
      return f.data;
    }
  }
  //获取最后一个元素
  public integer getlast(){
    if (size==0){
      throw new nosuchelementexception();
    }

    return head.prior.data;
  }

  //删除第一个元素
  public integer removefirst(){
    node f=head;
    if (f==null){
      throw new nosuchelementexception();
    } else {
      return unlink(head);
    }
  }

  //删除最后一个元素
  public integer removelast(){
    if (size==0){
      throw new nosuchelementexception();
    }
    int index=size-1;
    return unlink(node(index));
  }


  //根据索引删除元素
  public integer remove(int index){
    checkelementindex(index);
    return unlink(node(index));
  }

  //销毁链表
  public void destroylist(){
    clearlist();
  }
  //将链表置为空表
  public void clearlist() {

    for (node p=head;p!=null;){
      node next=p.next;//记录下一个结点
      p=null;//删除当前结点
      p=next;//指向下一个结点
    }
    size=0;
    head=null;
  }
  //遍历链表
  public void traverselist(boolean isreversevisited){
    if (!isempty()){
      if (!isreversevisited){
        for (node p=head;p!=head.prior;p=p.next){
          system.out.println(p.data);
        }
        system.out.println(head.prior.data);
      } else {
        for (node p=head.prior;p!=head;p=p.prior){
          system.out.println(p.data);
        }
        system.out.println(head.data);
      }
    }
  }



  //返回链表元素个数
  public int size(){
    return size;
  }


  public boolean isempty(){
    return size==0;
  }
  /*双向链表插入一个结点，要改变的指针如下:
   *
   *(1)前一个结点的next指针
   *(2)后一个结点的prior指针
   *(3)新创建的结点的prior指针和next指针
   * */
  //尾部添加结点
  private void linklast(int element){
    if (size==0){//没有结点时
      head=new node(element);
      head.next=head;
      head.prior=head;
      size++;
    } else {
      //得到最后一个结点
      node oldtail=head.prior;
      //new新的尾结点 newtail
      //newtail的前一个结点设置为旧的尾结点,
      //newtail的后一个结点指向head
      node newtail=new node(oldtail,element,head);
      //head的下一个结点指向newtail
      head.prior=newtail;
      //旧的尾结点的下一个结点指向新的尾结点
      oldtail.next=newtail;
      size++;
    }

  }


  //在某结点之前插入结点
  private void linkbefore(int element,node node){
    if (node==null){
      linklast(element);
    } else {
      node p=head;
      if (node.data==p.data){
        node q=p.prior;
        node newnode=new node(q,element,p);
        q.next=newnode;
        p.prior=newnode;
        size++;
      } else {
        for (p=p.next;p!=head;){
          if (node.data==p.data){
            node q=p.prior;
            node newnode=new node(q,element,p);
            q.next=newnode;
            p.prior=newnode;
            size++;
          }
          p=p.next;
        }

      }


    }

  }
  /*
  * 双向链表删除一个结点:
  * (1)找到该结点
  * (2)找到该结点的前一结点(prior)p和下一结点(next)q
  * (3)p的next指针指向q,q的prior指针指向p
  * (4)如果是删除的是头结点，指明当前头结点
  * */

  //删除结点
  private integer unlink(node node){
    integer deletenodedata=node.data;
    node p=null,q=null;
    if (deletenodedata==head.data){//该结点为头结点
      node cur=head;
      p=head.prior;
      q=head.next;
      p.next=q;
      q.prior=p;
      head=q;
      cur=null;
      size--;
    } else {
      node m;
      for (m=head.next;m!=head;){
        if (m.data==deletenodedata){
          p=m.prior;
          q=m.next;
          p.next=q;
          q.prior=p;
          m=null;
          size--;
          break;
        }
        m=m.next;
      }

    }
    return deletenodedata;
  }

  //数组下标是否越界
  private boolean iselementindex(int index){
    return index>=0&&index<size;
  }
  //插入位置是否越界
  public boolean ispositionindex(int index){
    return index>=0&&index<=size;
  }

  //检验下标是否越界，抛出异常
  private void checkelementindex(int index){
    if(!iselementindex(index)){
      try {
        throw new indexoutofboundsexception("下标越界");
      } catch (exception e) {
        e.printstacktrace();
      }
    }
  }

  //检验插入下标是否越界，抛出异常
  private void checkpositionindex(int index){
    if(!ispositionindex(index)){
      try {
        throw new indexoutofboundsexception("下标越界");
      } catch (exception e) {
        e.printstacktrace();
      }
    }
  }



  //返回指定位置的元素
  private node node(int index){
    int nowindex = 0;
    if(size>0){
      for (node p=head;p!=head.prior;){
        if (nowindex==index){
          return p;
        }
        p=p.next;
        nowindex++;
      }
      if (nowindex==index){
        return head.prior;
      }
    }
    return null;

  }

  public static void main(string[] args) {

    java.util.linkedlist linkedlist0=new java.util.linkedlist();
    linkedlist0.add(6);
    linkedlist0.remove(0);
    linkedlist0.size();
    linkedlist0.peek();
    //linkedlist0.getfirst();
    linkedlist0.clear();

    //测试
    linkedlist linkedlist=new linkedlist();
    linkedlist.add(2);
    linkedlist.add(3);
    linkedlist.add(5);
    linkedlist.add(7);
    linkedlist.add(1);
    linkedlist.add(33);

    linkedlist.add(4,0);
    linkedlist.add(3,1);
    linkedlist.add(7,6);
    linkedlist.add(0,10);
    linkedlist.add(10,11);
    linkedlist.remove(0);
    linkedlist.remove(0);
    linkedlist.remove(0);
    linkedlist.remove(1);
    linkedlist.remove(4);
    linkedlist.remove(5);
    linkedlist.remove(0);
//    linkedlist.remove(0);
//    linkedlist.remove(0);
//    linkedlist.remove(0);
   // linkedlist.remove(0);
    system.out.println(linkedlist.get(0));
    system.out.println(linkedlist.get(1));
    system.out.println(linkedlist.get(2));
    system.out.println(linkedlist.get(3));
    system.out.println(linkedlist.getfirst());
    system.out.println(linkedlist.getlast());
    linkedlist.removefirst();
    linkedlist.removelast();

    system.out.println("遍历链表");
    linkedlist.traverselist(false);
//    system.out.println("逆向遍历链表");
//    linkedlist.traverselist(true);
    system.out.println("链表长度");

    system.out.println(linkedlist.size());
    linkedlist.clearlist();

  }
}

总结

以上就是java简单实现双向链表，更多功能可参考java集合中的linkedlist实现。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。