带头双向循环链表

双向循环链表中，链表的每个节点既指向前面一个节点，也指向后面一个节点，节点具有两个域：prev和next。

主要类：

package cirLinkedList;

class DLinkedNode{
	public int val =0;
	public DLinkedNode prev = null;
	public DLinkedNode next = null;
	
	public DLinkedNode(int val) {
		this.val = val;
	}	
	
}

public class DLinkedList {
	private DLinkedNode head = null;
	
	public DLinkedList() {
		//创建傀儡节点
		head = new DLinkedNode(-1);
		//带环
		head.next = head;
		head.prev = head;
	}
	
	public void addFrist(int data) {
		//创建一个新的节点
		DLinkedNode newNode = new DLinkedNode(data);
		DLinkedNode next = head.next;
		head.next = newNode;
		newNode.next = next;
		
		newNode.prev = head;
		next.prev = newNode;
	}
	
	public void addLast(int data) {
		DLinkedNode newNode = new DLinkedNode(data);
		DLinkedNode prev = head.prev;
		newNode.next = head;
		head.prev = newNode;
		
		prev.next = newNode;
		newNode.prev = prev;
	}
	
	public void addIndex(int index,int data) {
		if(index<0 || index>size()) {//不合法
			return;
		}
		if(index == 0) {//头插
			addFrist(data);
			return;
		}
		if(index == size()) {//尾插
			addLast(data);
			return;
		}
		DLinkedNode next = getPos(index);
		DLinkedNode prev = next.prev;
		DLinkedNode newNode = new DLinkedNode(data);
		prev.next = newNode;
		newNode.prev = prev;
		
		next.prev = newNode;
		newNode.next = next; 
	}
	
	public boolean contains(int toFind) {
		for(DLinkedNode cur = head.next;
				cur != head;cur = cur.next) {
			if(cur.val == toFind) {
				return true;
			}
		}
		return false;	
	}
	
	public DLinkedNode getPos(int index) {
		//找到下标为index对应的节点
		DLinkedNode cur = head.next;
		for(int i=0;i<index;i++) {
			cur = cur.next;
		}
		return cur;
	}
	
	public void remove(int key) {
		//现根据key找到要删除的元素的位置
		DLinkedNode toRemove = find(key);
		if(toRemove == null) {//未找到要删除元素
			return;
		}
		//具体删除操作
		DLinkedNode prev = toRemove.prev;
		DLinkedNode next = toRemove.next;
		prev.next = next;
		next.prev = prev;
	}
	
	public void removeAll(int key) {
		while(true) {
			DLinkedNode toRemove = find(key);
			if(toRemove == null) {//未找到要删除元素
				return;
			}
			//具体删除操作
			DLinkedNode prev = toRemove.prev;
			DLinkedNode next = toRemove.next;
			prev.next = next;
			next.prev = prev;
		}
	}
	
	public DLinkedNode find(int key) {
		for(DLinkedNode cur = head.next;
				cur != head;cur = cur.next) {
			if(cur.val == key) {
				return cur;
			}
		}
		return null;
	}
	
	public int size() {
		int size = 0;
		for(DLinkedNode cur = head.next;
				cur != head;cur = cur.next) {
			size++;
		}
		return size;
	}
	
	public void display() {
		System.out.print("正向打印：[");
		for(DLinkedNode cur = head.next; 
				cur!=head;cur = cur.next) {
			System.out.print(cur.val);
			if(cur.next != head) {
				System.out.print(",");
			}
		}
		System.out.println("]");
		System.out.print("反向打印：[");
		for(DLinkedNode cur = head.prev; 
				cur!=head;cur = cur.prev) {
			System.out.print(cur.val);
			if(cur.prev != head) {
				System.out.print(",");
			}
		}
		System.out.println("]");	
	}
	
	public void clear() {
		head.next = head;
		head.prev = head;
	}
	
}

测试代码：

package cirLinkedList;

public class Test {
	public static void main(String[] args) {
		testAddFrist();
		testAddLast();
		testAddIndex();
		testContains();
		testRemove();
		testRemoveAll();
	}
	
	public static void testAddFrist() {
		System.out.println("测试双向链表的头插：");
		DLinkedList dLinkedList = new DLinkedList();
		dLinkedList.addFrist(1);
		dLinkedList.addFrist(2);
		dLinkedList.addFrist(3);
		dLinkedList.addFrist(4);
		dLinkedList.display();
	}
	
	public static void testAddLast() {
		System.out.println("测试双向链表的尾插：");
		DLinkedList dLinkedList = new DLinkedList();
		dLinkedList.addFrist(1);
		dLinkedList.addFrist(2);
		dLinkedList.addFrist(3);
		dLinkedList.addFrist(4);
		dLinkedList.display();
	}
	
	public static void testAddIndex() {
		System.out.println("测试双向链表指定位置的插入：");
		DLinkedList dLinkedList = new DLinkedList();
		dLinkedList.addFrist(1);
		dLinkedList.addFrist(2);
		dLinkedList.addFrist(3);
		dLinkedList.addFrist(4);
		dLinkedList.addIndex(2, 666);
		dLinkedList.display();
	}
	
	public static void testContains() {
		System.out.println("测试双向链表是否包含指定元素：");
		DLinkedList dLinkedList = new DLinkedList();
		dLinkedList.addFrist(1);
		dLinkedList.addFrist(2);
		dLinkedList.addFrist(3);
		dLinkedList.addFrist(4);
		boolean ret = dLinkedList.contains(2);
		System.out.println("ret = "+ret);
	}
	
	public static void testRemove() {
		System.out.println("测试双向链表删除指定元素：");
		DLinkedList dLinkedList = new DLinkedList();
		dLinkedList.addFrist(1);
		dLinkedList.addFrist(2);
		dLinkedList.addFrist(3);
		dLinkedList.addFrist(4);
		dLinkedList.remove(3);
		dLinkedList.display();
	}
	
	public static void testRemoveAll() {
		System.out.println("测试双向链表删除所有的指定元素：");
		DLinkedList dLinkedList = new DLinkedList();
		dLinkedList.addFrist(1);
		dLinkedList.addFrist(2);
		dLinkedList.addFrist(2);
		dLinkedList.addFrist(2);
		dLinkedList.addFrist(4);
		dLinkedList.addFrist(3);
		dLinkedList.addFrist(2);
		dLinkedList.addFrist(2);
		dLinkedList.addFrist(4);
		dLinkedList.removeAll(2);
		dLinkedList.display();
	}
	
}

运行结果：