去重排序List（Java实现）

去重排序List（Java实现）

• 去重排序ListJava实现
  • 需求描述
  • 链式实现
    • 本机性能测试结果
  • 其他尝试

需求描述

对于顺序产生的一系列整数进行去重排序。

链式实现

//去重自排序链表
public class AscendingIntegerList {
    private int size = 0;
    private Node first;

    public AscendingIntegerList() { }

    public void add(int index) {
        Node node = first;
        Node lastNode = null;
        int temp = 0;
        while(node != null) {
            temp = node.i.intValue();
            if(temp < index) {
                lastNode = node;
                node = node.next;
            } else if(temp == index) {
                //重复元素直接跳过
                return;
            } else {
                break;
            }
        }
        insertAfter(lastNode, index);
    }

    private void insertAfter(Node node, Integer i) {
        Node newNode = new Node(i, null);
        if(node == null) {
            newNode.next = first;
            first = newNode;
        } else {
            newNode.next = node.next;
            node.next = newNode;
        }
        size++;
    }

    public int size() {
        return size;
    }

    public void clear() {
        for(Node x = first; x != null; ) {
            Node next = x.next;
            x.i = null;
            x.next = null;
            x = next;
        }
        first = null;
        size = 0;
    }

    public static class Node {
        Integer i;
        Node next;
        Node(Integer i, Node next) {
            this.i = i;
            this.next = next;
        }
    }

    //返回一个迭代器供外部进行遍历
    public Iterator<Integer> listIterator() {
        return new ListItr();
    }

    private class ListItr implements Iterator<Integer> {
        private Node lastReturned = null;
        private Node next;

        ListItr() {
            next = first;
        }

        public boolean hasNext() {
            return next != null;
        }

        public Integer next() {
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            return lastReturned.i;
        }

        public void remove() {
            //we do nothing.
        }
    }
}

本机性能测试结果：

数据量	时间（s）
1万	0.25 ~0.3
10万	10 ~ 20

• 最初考虑尝试链表实现，是因为链表插入元素开销小。
• 以上算法的性能问题在于频繁创建节点(Node)和计算新增节点的插入位置，应对大量数据时算法效率低。

其他尝试

后来采用ArrayList存储+折半查找计算插入位置 性能更好。

• 折半查找优化插入位置的计算
• ArrayList批量自动扩容
• 唯一担心的在于需要对插入位置后面的元素进行“整体搬家”，ArrayList采用System.arraycopy效率还是蛮高的。