LinkedList 自定义实现比 Java LinkedList 更快

Question

我最近开始了 Cracking the Code Interview，我刚开始接触 LinkedLists。我做了问题 2.1，从书中的 LinkedList 实现中删除了重复的条目。

当我计算删除重复项时，我发现这本书的实现比 Java LinkedList 更快。

我已经实现了四种重复删除方法，每种方法都有不同的参数。本书的 LinkedList 实现被称为 Node.

    static void removeDupes(LinkedList<Integer> list) {
        HashSet<Integer> integerHashSet = new HashSet<>();
        for (int i = 0; i < list.size(); i++) {
            if (integerHashSet.contains(list.get(i))) {
                list.remove(list.get(i));
            } else {
                integerHashSet.add(list.get(i));
            }
        }
    }

    static void removeDupes(ArrayList<Integer> list) {
        HashSet<Integer> integerHashSet = new HashSet<>();
        for (int i = 0; i < list.size(); i++) {
            if (integerHashSet.contains(list.get(i))) {
                list.remove(list.get(i));
            } else {
                integerHashSet.add(list.get(i));
            }
        }
    }

   static void removeDupes(Node currentNode) {
        HashSet<Integer> integerHashSet = new HashSet<>();
        while(currentNode != null) {
            if (integerHashSet.contains(currentNode.data)) {
                currentNode.prev.next = currentNode.next;
                if (currentNode.next != null) {
                    currentNode.next.prev = currentNode.prev;
                }
            } else {
                integerHashSet.add(currentNode.data);
            }
            currentNode = currentNode.next;
        }
    }

    static void removeDupesNoBuffer(Node currentNode) {
        while (currentNode != null) {
            Node runnerNode = currentNode;
            while(runnerNode.next != null) {
                if (runnerNode.next.data == currentNode.data) {
                    runnerNode.next = runnerNode.next.next;
                    if (runnerNode.next != null) {
                        runnerNode.next.prev = runnerNode;
                    }
                } else {
                    runnerNode = runnerNode.next;
                }
            }
            currentNode = currentNode.next;
        }
    }

图书的 LinkedList 实现：

public class Node {
    Node prev;
    Node next;
    int data;

    Node(int d) {
        data = d;
    }

    void add(int d) {
        Node newNode = new Node(d);
        Node currentNode = this;
        while (currentNode.next != null) {
            currentNode = currentNode.next;
        }
        currentNode.next = newNode;
        newNode.prev = currentNode;
    }
}

每个列表或节点，我填充了 100000 的长度，其中每个奇数索引为 0，其他所有内容都是唯一的。

我的结果是：

节点：18ms
节点无缓冲区：5154ms
链表：2734ms
数组列表：1392 毫秒

我哪里不明白？

编辑：

正如评论和解决方案所指出的那样，当我将带有 LinkedList 参数的删除重复项交换为增强的 for 循环时，它变得同样快。

    static void removeDupes(LinkedList<Integer> list) {
        HashSet<Integer> integerHashSet = new HashSet<>();
        for(Integer i : list) {
            if (integerHashSet.contains(i)) {
                list.remove(i);
            } else {
                integerHashSet.add(i);
            }
        }
    }

Answer 1

原因是你做的效率低下。如果您使用索引遍历链表，则该列表必须计算每个节点引用以找到正确的节点。然后它作用于那个。

像这样尝试一下，看看有什么不同。计算 N 项的链表的偶数值。第二次迭代会快很多。

首先，索引 for 循环。

List<Integer> list1 = new LinkedList<>();
Random r = new Random();
int N = 100_000;
for(int i = 0; i < N; i++) {
    list1.add(r.nextInt(10000));
}
// copy the list
List<Integer> list2 = new LinkedList<>(list1);

System.out.println("Starting list1");
int sumEvens = 0;
for(int i = 0; i < list1.size(); i++) {
    if (list1.get(i) % 2 == 0) {
        sumEvens++;
    }
}
System.out.printf("There were %d even values%n", sumEvens);

现在是使用迭代器的增强型 forloop。

System.out.println("Starting list2");
sumEvens = 0;
for(int i : list2) {
    if ( i%2 == 0) {
        sumEvens++;
    }
}
System.out.printf("There were %d even values%n", sumEvens);

最后，Arraylists访问快，删除慢。这是因为删除一个项目时，必须将所有后续项目复制到一个单元格中以弥补差距。但是链表可以通过简单地让前一个节点指向下一个节点来删除一个项目。因此，列表的使用方式决定了列表实现的选择。

LinkedList 自定义实现比 Java LinkedList 更快

LinkedList Custom Implementation Faster than Java LinkedList

java

linked-list

arraylist