但行好事  莫问前程

自己实现集合框架(六):可排序单链表的实现

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

一. 什么叫可排序的单链表?

1. 场景描述:
在项目中我们常常会有这样的需求,存放元素的时候可以预先按照数值大小进行排序(升序或降序),那么在取出数据的时候就不需要再次排序了。

2. 什么叫可排序的单链表?
可排序的单链表指单链表各结点的数据域data的值按照递增(由小到大)或者递减(由大到小)的方式链接起来。

3. 如何实现可排序的单链表?
我们知道java里面的TreeSet集合是可排序的,并且支持自然排序和定制排序两种方式。那么可排序的单链表是如何做到可排序的呢?

单链表要实现可排序,则结点data域的对象必须是可比较大小的,即已经实现了java.lang.Comparable接口的compareTo()方法,该方法返回一个整数值,当一个对象调用该方法与另外一个对象进行比较时,例如obj1.compareTo(obj2),如果该方法返回0,则表明这两个对象相等;如果该方法返回一个正整数,则表明obj1大于obj2;如果该方法返回一个负整数,则表明obj1小于obj2

二. 可排序单链表的实现

1.定义可排序单链表

可排序单链表类SortedHeadSinglyLinkedList继承自带头结点的单链表类HeadSinglyLinkedList,二者相同的方法不再介绍,请参见之前的文章自己实现集合框架(五):带头结点单链表的实现,只是在插入元素和移除元素的时候都需要比较大小,代码如下所示:

package org.light4j.dataStructure.linearList.linkList.head.sorted;

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

/**
 * 排序的单链表,继承至带头结点的单链表类HeadSinglyLinkedList
 * 
 * @author longjiazuo
 */
public class SortedHeadSinglyLinkedList<E> extends HeadSinglyLinkedList<E> {
    public SortedHeadSinglyLinkedList() {
        super();
    }
}

2. 可排序单链表的插入

       /**
     * 根据指定对象的大小把对象插入到合适的位置上,操作成功返回true
     */
    @Override
    public boolean add(E element) {
        // 不能插入null或者非Comparable对象
        if (element == null || !(element instanceof Comparable)) {
            return false;
        }
        @SuppressWarnings("unchecked")
        Comparable<E> cmp = (Comparable<E>) element;
        Node<E> front = this.head;
        Node<E> p = front.next;// front结点是p的前驱结点
        while (p != null && (cmp.compareTo(p.data) > 0)) {// 比较对象大小
            front = p;
            p = p.next;
        }
        front.next = new Node<E>(element, p);// 插入元素,插入位置在p结点之前
        if (p == null) {
            this.rear = front.next;// 尾插入则需要修改尾指针
        }
        this.n++;
        return true;
    }

代码解释:

插入的元素对象不能为空,并且需要实现Comparable接口。

插入规则是,从空链表开始,逐个插入结点建立排序的单链表,每插入一个结点,首先要从单链表的第0个节点开始,将待插入元素elment依次与当前结点的data值比较大小,以确定插入位置并进行插入操作,时间复杂度为O(n)

3. 可排序单链表的移除

/**
     * 删除指定对象,操作成功则返回true
     * 
     * @param element
     * @return
     */
    public boolean remove(E element) {
        if (element == null || !(element instanceof Comparable)) {
            return false;
        }
        @SuppressWarnings("unchecked")
        Comparable<E> cmp = (Comparable<E>) element;
        Node<E> front = this.head;
        Node<E> p = front.next;// front结点是p的前驱结点
        while (p != null && (cmp.compareTo(p.data) > 0)) {// 比较对象大小
            front = p;
            p = p.next;
        }

        if (p == null || cmp.compareTo(p.data) == 0) {// 没有找到指定的结点,删除失败
            return false;
        }
        front.next = p.next;// 删除p结点
        if (p == this.rear) {
            this.rear = front;
        }
        this.n--;
        return true;
    }

代码解释:

可排序单链表的删除,在实际的操作逻辑上和可排序的单链表的插入比较类似,都是需要比较大小,然后移动数据元素,时间复杂度为O(n)

三.测试

测试代码如下所示:

package org.light4j.dataStructure.linearList.linkList.head.sorted;

public class Test {
    public static void main(String[] args) {
        SortedHeadSinglyLinkedList<Integer> list = new SortedHeadSinglyLinkedList<Integer>();
        int n = 10;
        System.out.print("insert:   ");
        for (int i = 0; i < n; i++) {
            int k = (int) (Math.random() * 100);// 产生随机数
            list.add(new Integer(k));
            System.out.print(k + "    ");
        }
        System.out.println("\nlist  " + list.toString());
    }
}

代码解释:

java里面的很多类已经实现了java.lang.Comparable接口,例如StringInteger等。如果自定义的类需要使用可排序的单链表必须要实现java.lang.Comparable接口,并重写compareTo()方法。

运行效果如下图所示:

四.源代码示例

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

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

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

分享到:更多 ()

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

联系我关于我