Java实现双向循环链表

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 chttp://lass Node{

private int data;//数据http://

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

}

//插入位置是否越界

public Boolean isPositionIndex(int lKqzNVPNxindex){

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(thttp://rue);

System.out.println("链表长度");

System.out.println(linkedList.size());

linkedList.clearList();

}

}

总结

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

}

//插入位置是否越界

public Boolean isPositionIndex(int lKqzNVPNxindex){

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(thttp://rue);

System.out.println("链表长度");

System.out.println(linkedList.size());

linkedList.clearList();

}

}

总结

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。