数据结构||Java实现循环链表的增添，删除，插入，修改，查询

冷不防 2021-10-30 05:42 386阅读 0赞

## 循环链表 ##

前面我们已经讲过了单链表和双向链表，今天我们要讲的主角是循环链表，循环链表与前面两个没多大区别，仅仅是将最后一个元素的后驱指向首元素，即尾部结点的后驱再也不是指向null了，而是指向头部；

### 结构图如下 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pvY2tMaXU_size_16_color_FFFFFF_t_70][]

功能实现：

public class CycleLinkedList {
    
        class CycleNode {
            Object data;
            CycleNode next = null;
            CycleNode() {//为空情况
                this.data = null;
            }
            CycleNode(Object data) {//不为空的情况
                this.data = data;
            }
        }
    
        private CycleNode head, pos;
        private int size;
    
        //初始化时,生成一个包含头节点的空链表
        CycleLinkedList() {
            head = new CycleNode();
            head.next = head;
            pos = head;
            this.size = 0;
    
        }
    
        /**
         * 返回链表的大小
         * @return
         */
        public int len() {
            return this.size;
        }
    
        /**
         * 判断链表是否为空
         * @return
         */
        public boolean isEmpty() {
            return this.size == 0;
        }
    
        /**
         * 添加元素，在末尾节点处添加
         */
        public void add(Object data) {
            CycleNode temp = new CycleNode(data);
            if (head.next == head) {
                head.next = temp;
                temp.next = head;
            } else {
                pos = head;
                while (pos.next != head) {
                    pos = pos.next;
                }
                pos.next = temp;
                temp.next = head;
            }
            size++;
        }
    
        /**
         * 插入元素， 在指定索引位置处插入
         * @param index
         * @param data
         */
        public void insert(int index, Object data) {
            CycleNode temp = new CycleNode(data);
            if (index < 0 || index > size - 1)
                throw new RuntimeException("索引错误" + index);
            int i = 0;
            pos = head;
            while (pos.next != head && i < index) {
                pos = pos.next;
                i++;
            }
            temp.next = pos.next;
            pos.next = temp;
            size++;
        }
    
        /**
         * 移除元素
         */
        public Object remove(int index) {
            Object value = null;
            if (index < 0 || index > size - 1)
                throw new RuntimeException("索引错误" + index);
            int i = 0;
            pos = head;
            while (pos.next != head && i < index) {
                pos = pos.next;
                i++;
            }
            value = pos.next.data;
            pos.next = pos.next.next;
            size--;
            return value;
        }
    
        /**
         * 替换元素
    
         */
        public Object replace(int index, Object newObj) {
            Object value = null;
            if (index < 0 || index > size - 1)
                throw new RuntimeException("索引错误" + index);
            int i = 0;
            pos = head;
            while (pos.next != head && i < index) {
                pos = pos.next;
                i++;
            }
            value = pos.next.data;
            pos.next.data = newObj;
            return value;
        }
    
        /**
         * 获取元素
         */
        public Object get(int index) {
    
            if (index < 0 || index > size - 1)
                throw new RuntimeException("索引错误" + index);
            int i = 0;
            pos = head;
            while (pos.next != head && i < index) {
                pos = pos.next;
                i++;
            }
            return pos.next.data;
        }
    
        /**
         * 查询元素索引
         * @param data
         * @return
         */
        public int indexOf(Object data) {
    
            int i = 0;
            pos = head;
            while (pos.next != head) {
                pos = pos.next;
                if (pos.data.equals(data))
                    return i;
                i++;
            }
            return -1;
        }
    
        /**
         * 判断是否包含指定元素
         */
        public void find(Object data) {
            pos = head;
            while (pos.next != head) {
                pos = pos.next;
                if (pos.data.equals(data))
                    System.out.println("含有该元素");
            }
            System.out.println("没有这个元素");
        }
    
        /**
         * 打印函数
         */
        public void print() {
            for (int i = 0; i < size; i++) {
                System.out.print(this.get(i) + "-->");
            }
            System.out.println();
        }
        public static void main(String[] args) {
        	CycleLinkedList list = new CycleLinkedList();
    		// 插入结点
    		list.add(10000);
    		list.add(10010);
    		list.add(10086);
    		list.add(12580);
    		list.add(12306);
    		System.out.println("初始链表：");
    		list.print();
    		list.insert(3, 12316);
    		System.out.println("插入链表：");
    		list.print();
    		list.remove(3);
    		System.out.println("删除指定索引链表：");
    		list.print();
    		System.out.println("查询链表：");
    		list.find(12110);
    	}
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pvY2tMaXU_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pvY2tMaXU_size_16_color_FFFFFF_t_70]: /images/20211029/f8d5ee533b004a53abcdbb58c9dc2c38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pvY2tMaXU_size_16_color_FFFFFF_t_70 1]: /images/20211029/1b2e405f49504ce4a11a3a042dc43d77.png