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

大话数据结构四：线性表的链式存储结构（单向循环链表）2014-12-281. 单向循环链表：将单链表尾结点的指针端由空指针改为指向头结点，使整个单链表形成一个环，这种头尾相接的单链表称为单向循环链表。

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

作者：csdn博客 zdp072