大话数据结构四：线性表的链式存储结构（单向循环链表）

1. 单向循环链表：将单链表尾结点的指针端由空指针改为指向头结点，使整个单链表形成一个环，这种头尾相接的单链表称为单向循环链表。

2. 单向循环链表和单链表实现的区别：

1.）添加一个结点到单向循环链表末尾时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为null。

2.）判断是否到达表尾时，单向循环链表可以判断该结点是否指向头结点，单链表只需要知道是否为null。

3.Java实现单向循环链表：

// 单向循环链表
public class CircularLinkedList<E> {
	private Node<E> tail; // 尾结点
	private int size; // 链表长度

	public CircularLinkedList() {
		tail = null;
		size = 0;
	}
	
	// 在头结点前插入
	public boolean addBeforeHead(E data){
		Node<E> newNode = new Node<E>(data);
		if(isEmpty()){
			tail = newNode;
			tail.setNext(newNode); // 尾结点指向头结点
			newNode.setNext(tail); // 头结点指向尾结点
		}else{
			Node<E> head = tail.getNext();
			tail.setNext(newNode);
			newNode.setNext(head);
		}
		size++;
		return true;
	}
	
	// 在尾结点后插入
	public boolean addAfterTail(E data){
		Node<E> newNode = new Node<E>(data);
		if(isEmpty()){
			tail = newNode;
			tail.setNext(newNode); 
			newNode.setNext(tail); 
		}else{
			Node<E> head = tail.getNext(); // 获取头结点
			tail.setNext(newNode); // 将原尾结点指向新结点
			tail = newNode; // 将新节点设置为尾结点
			newNode.setNext(head); // 将新尾结点指向头结点
		}
		size++;
		return true;
	}
	
	// 在某位置上插入（position为结点位置,不是角标）
	public boolean insert(int position,E data){
		if(position >= 1 && (position <= size + 1)){
			if(isEmpty() || position == 1){ // 在头结点前插入
				addBeforeHead(data); 
			}else if(position == size + 1){ // 在尾结点后插入
				addAfterTail(data);
			}else{ // 在中间位置插入
				Node<E> preNode = get(position - 1); // 获取position的前一结点
				Node<E> originalNode = preNode.getNext(); // 获取未插入结点时position位置对应结点 
				Node<E> newNode = new Node<E>(data);
				preNode.setNext(newNode);
				newNode.setNext(originalNode);
				size++;
				return true;
			}
		}
		return false;
	}
	
	// 删除对应位置的结点
	public E delete(int position){
		E result = null;
		if(position >= 1 && position <= size){
			if(position == 1){ // 删除头结点
				result = tail.getNext().getData();
				Node<E> afterHead = tail.getNext().getNext();
				tail.setNext(afterHead);
			}else if(position == size){ // 删除尾结点
				result = tail.getData();
				Node<E> preTail = get(position - 1);
				preTail.setNext(tail.getNext());
				tail = preTail;
				size--;
			}else{ // 删除其他结点
				Node<E> preNode = get(position - 1);
				Node<E> curNode = preNode.getNext();
				result = curNode.getData();
				preNode.setNext(curNode.getNext());
				size--;
			}
		}
		return result;
	}
	
	// 获取某个位置的结点
	public Node<E> get(int position){
		Node<E> targetNode = null;
		if(!isEmpty() && position >= 1 && position <= size){ 
			targetNode = tail.getNext(); // 获取头结点
			for(int i = 1; i < position ; i++){
				targetNode = targetNode.getNext(); // 循环获取对应位置的结点
			}
		}
		return targetNode;
	}
	
	// 获取链表的长度
	public int getSize(){
		return size;
	}
	
	// 判断链表是否为空
	public boolean isEmpty(){
		return size == 0;
	}
	
	// 打印链表中的数据
	public void display(){
		Node<E> node = tail.getNext();  // 获取头结点
		System.out.print("单向循环链表: ");
		for(int i = 0; i < size; i++){
			System.out.print("　" + node.getData());
			node = node.getNext();
		}
		System.out.println("");
	}
}

// 结点类，包含结点的数据和指向下一个节点的引用
public class Node<E> {
	private E data; // 数据域
	private Node<E> next; // 指针域保存着下一节点的引用

	public Node() {
	}

	public Node(E data) {
		this.data = data;
	}

	public Node(E data, Node<E> next) {
		this.data = data;
		this.next = next;
	}

	public E getData() {
		return data;
	}

	public void setData(E data) {
		this.data = data;
	}

	public Node<E> getNext() {
		return next;
	}

	public void setNext(Node<E> next) {
		this.next = next;
	}
}

// 测试类
public class Main {
	public static void main(String[] args) {
		CircularLinkedList<Integer> circular = new CircularLinkedList<Integer>();
		circular.addBeforeHead(3);
		circular.addBeforeHead(2);
		circular.addBeforeHead(1);
		circular.addAfterTail(4);
		circular.addAfterTail(5);
		circular.addAfterTail(6);
		circular.insert(1,0);
		circular.insert(8,7);
		circular.insert(5,8);
		circular.delete(5);
		circular.display();
		System.out.println("链表的长度为: " + circular.getSize());
	}
}