但行好事  莫问前程

自己实现集合框架(七):循环单链表的实现

这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现,从而对常用的数据结构和java集合有个大概的了解。当然实现没有java集合的实现那么复杂,功能也没有那么强大,但是可以通过这些简单的实现窥探到底层的一些共性原理。

一. 什么是循环单链表?

循环单链表是指单链表的最后一个结点的next域指向单链表的头结点head,使单链表成为环形结构。设rear是单链表的尾结点,rear.next=head使得一条单链表成为循环单链表,如下图所示:

head.next==head满足时,循环单链表为空,如下图所示:

二. 循环单链表的实现

1.定义循环单链表

循环单链表类CircularSinglyLinkedList继承带头结点的单链表类HeadSinglyLinkedList,二者相同的方法不再介绍,请参见之前的文章自己实现集合框架(五):带头结点单链表的实现,只是在尾插入元素尾移除元素清空元素的时候会有不一样的地方,也就是需要把尾结点的next域指向head结点,CircularSinglyLinkedList类定义如下所示:

package org.light4j.dataStructure.linearList.linkList.circular;

import org.light4j.dataStructure.linearList.linkList.Node;
import org.light4j.dataStructure.linearList.linkList.head.HeadSinglyLinkedList;

/**
 * <p>
 * 循环单链表类
 * </p>
 * 
 * @author longjiazuo
 * 
 * @param <E>
 */
public class CircularSinglyLinkedList<E> extends HeadSinglyLinkedList<E> {
    /**
     * 构造空单链表
     */
    public CircularSinglyLinkedList() {
        this.head = new Node<E>(null);
        this.rear = this.head;
        this.head.next = this.head;
        this.n = 0;
    }
}

2. 循环单链表的插入

        /**
     * 在指定位置插入非空的指针对象
     */
    @Override
    public boolean add(int index, E element) {
        if (element == null) {// 不允许插入非空元素
            return false;
        }
        if (index >= this.n) {// 尾插入,插入在最后
            this.add(element);
        } else {
            Node<E> p = this.head;
            int i = 0;
            while (p.next != null && i < index) {
                i++;
                p = p.next;
            }
            // 下面操作可以包含头插入和中间插入
            Node<E> q = new Node<E>(element);
            q.next = p.next;
            p.next = q;// 将q结点插入到p结点之后
            this.n++;
            return true;
        }
        return false;
    }

    /**
     * 在单链表的最后插入元素对象,时间复杂度是O(1)
     */
    @Override
    public boolean add(E element) {
        if (element == null) {// 不允许插入非空元素
            return false;
        }
        this.rear.next = new Node<E>(element);// 尾插入
        this.rear = this.rear.next;// 移动尾指针
        this.rear.next = this.head;//把尾结点的next域指向head结点
        this.n++;// 链表长度增加
        return true;
    }

代码解释

在尾插入的时候,需要把尾结点的next域指向head结点:this.rear.next = this.head;

3. 循环单链表的移除

/**
     * 移除索引index处的结点,操作成功返回被移除的对象,失败则返回null
     */
    @Override
    public E remove(int index) {
        E old = null;
        if (index >= 0) {// 头删除,中间删除,尾删除
            Node<E> p = this.head;
            int i = 0;
            while (p.next != null && i < index) {// 从头结点开始遍历,定位到待删除结点的前驱结点
                i++;
                p = p.next;
            }
            if (p.next != null) {
                old = p.next.data;
                if (p.next == this.rear) {// 如果p结点的后一个结点是尾结点,则移除之后尾结点指针前移
                    this.rear = p;
                    this.rear.next = this.head;//把尾结点的next域指向head结点
                }
                p.next = p.next.next;// 删除p结点的后继结点
                this.n--;// 链表长度减少
                return old;
            }
        }
        return old;
    }

代码解释

在尾移除的时候,需要把尾结点的next域指向head结点:this.rear.next = this.head;

4. 清空循环单链表

@Override
    public void clear() {
        this.head.next = this.head;
        this.n = 0;
    }

代码解释

清空循环单链表,需要执行this.head.next = this.head;

5. 重写toString()方法

由于循环单链表的最后一个结点的next域不为空,需要重写toString(),代码如下:

@Override
    public String toString() {// 返回所有元素值对应的字符串
        String str = "(";
        Node<E> p = this.head.next;
        while (p.data != null) {
            str += p.data.toString();
            p = p.next;
            if (p != null) {
                str += ", ";
            }
        }
        return str + ")";
    }

三.测试

测试代码如下所示:

package org.light4j.dataStructure.linearList.linkList.circular;

import org.light4j.dataStructure.linearList.LList;

public class Test {
    public static void main(String[] args) {
        LList<String> list = new CircularSinglyLinkedList<String>();
        for (int i = 0; i < 10; i++) {
            list.add(0, new String((char) ('A' + i) + ""));
        }
        System.out.println(list.toString());
        System.out.println(list.get(1));//获取第一个元素
        list.remove(0);// 移除第一个元素
        System.out.println(list.toString());
    }
}

运行效果如下图所示:

四.源代码示例

github地址:点击查看
码云地址:点击查看

打赏
欢迎关注人生设计师的微信公众账号
公众号ID:longjiazuoA

未经允许不得转载:人生设计师 » 自己实现集合框架(七):循环单链表的实现

分享到:更多 ()

人生设计师-接受不同的声音

联系我关于我