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

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;
    }
}

更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

// 测试类
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());
    }
}

作者：csdn博客 zdp072

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索单链表
， 线性表
， 数据结构 单链表
， 单链表的顺序
， node
， 单链表 数据结构 c++
， 结点
， position
， 循环链表
， mode getnext
， tail
， 单向循环链表
， java单链表
单链
，以便于您获取更多的相关知识。