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实现。

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