链表的一般使用

Question

我知道您可以创建自己的链接列表 class 或使用 java.util 导入一个。像这样:

import java.util.*;  

LinkedList<String> ll=new LinkedList<String>();

然后用现有的方法对列表做一些事情，比如添加、获取、设置... 但是你也可以像那样创建你自己的链表：

class LinkedList {
Node head; // head of list


class Node {
    int data;
    Node next;

    Node(int d) { data = d; }
}
}

但如果您这样做，则需要创建所有方法。我的问题很简单，我应该使用方法 1 还是方法 2？如果两者都很好，什么时候使用一个比另一个更好。

Answer 1

除非您需要现有轮子无法提供的极其具体的东西，否则不要重新发明轮子。

此外，可能值得一提的是，链表具有较差的性能特征，因为它们占用的内存不连续，导致从主内存中多次读取 (link)。

Answer 2

如果您需要通用 List，请使用 java.util.LinkedList。它是一个标准 class，成熟，经过良好测试，几乎所有 Java 开发人员都能很好地理解...而且，当然，它很简洁，因为您不必实施它。

实际上，不要使用它：使用 java.util.ArrayList 或 java.util.ArrayDeque，它们几乎在所有情况下都优于 LinkedList。参见 When to use LinkedList over ArrayList in Java?

如果你真的需要更专业的东西，实现你自己的，但前提是你真的，真的需要它。

仅在您确实需要时才实施 class 实施 java.util.List。

避免必须在接口中实现“一切”的一个很好的起点是扩展 java.util.AbstractList：这只需要您提供 get(int)、size() 和，如果您希望列表是可修改的，set(int, E)（您可能希望覆盖其他列表以获得更好的链接列表性能）。

General use of Linked List