有空空闲列表数据结构吗？

Question

我正在使用 LinkedList 数据结构 serverList 来存储其中的元素。截至目前，它还可以在 LinkedList serverList 中插入 null，这不是我想要的。是否有任何其他我可以使用的数据结构不会在 serverList 列表中添加空元素但保持插入顺序？

    public List<String> getServerNames(ProcessData dataHolder) {
        // some code

        String localIP = getLocalIP(localPath, clientId);
        String localAddress = getLocalAddress(localPath, clientId);

        // some code

        List<String> serverList = new LinkedList<String>();

        serverList.add(localIP);
        if (ppFlag) {
            serverList.add(localAddress);
        }
        if (etrFlag) {
            for (String remotePath : holderPath) {
                String remoteIP = getRemoteIP(remotePath, clientId);
                String remoteAddress = getRemoteAddress(remotePath, clientId);
                serverList.add(remoteIP);
                if (ppFlag) {
                    serverList.add(remoteAddress);
                }
            }
        }

        return serverList;
    }

此方法将 return 一个列表，我以正常方式在 for 循环中对其进行迭代。如果一切都为空，我可以有空 serverList，而不是在我的列表中有四个空值。在我上面的代码中，getLocalIP、getLocalAddress、getRemoteIP 和 getRemoteAddress 可以 return null 然后它会在链表中添加 null 元素。我知道我可以添加一个 if 检查，但是我需要在添加到链接列表之前添加四次 if 检查。我可以在这里使用更好的数据结构吗？

我的一个限制是——这个库在非常重的负载下使用，所以这段代码必须很快，因为它会被调用多次。

Answer 1

使用 Apache Commons Collection:

ListUtils.predicatedList(new ArrayList(), PredicateUtils.notNullPredicate());

向此列表添加 null 会引发 IllegalArgumentException。此外，您可以通过任何您喜欢的 List 实现来支持它，如果需要，您可以添加更多要检查的谓词。

一般来说 Collection 也是如此。

Answer 2

有些数据结构不允许空元素，例如 ArrayDeque，但它们会抛出异常而不是静默地忽略空元素，因此您无论如何都必须在插入之前检查空元素。

如果您坚决反对在插入前添加空检查，您可以遍历列表并在 return 之前删除空元素。

Answer 3

最简单的方法是在 getServerNames() 方法中覆盖 LinkedList#add()。

List<String> serverList = new LinkedList<String>() {
    public boolean add(String item) {
        if (item != null) {
          super.add(item);
          return true;
        } else
          return false;
    }
};

serverList.add(null);
serverList.add("NotNULL");
System.out.println(serverList.size()); // prints 1

如果您随后发现自己在多个地方使用它，您可能可以将其变成 class。

Answer 4

您可以使用普通的 Java HashSet 来存储您的路径。 null 值可以添加多次，但它只会在 Set 中出现一次。您可以从 Set 中删除 null，然后在返回之前转换为 ArrayList。

Set<String> serverSet = new HashSet<String>();

    serverSet.add(localIP);
    if (ppFlag) {
        serverSet.add(localAddress);
    }
    if (etrFlag) {
        for (String remotePath : holderPath) {
            String remoteIP = getRemoteIP(remotePath, clientId);
            String remoteAddress = getRemoteAddress(remotePath, clientId);
            serverSet.add(remoteIP);
            if (ppFlag) {
                serverSet.add(remoteAddress);
            }
        }
    }

serverSet.remove(null);     // remove null from your set - no exception if null not present
List<String> serverList = new ArrayList<String>(serverSet);

return serverList;

Answer 5

I am using LinkedList data structure serverList to store the elements in it.

考虑到您的目标是速度，这很可能是错误的。 ArrayList 会快得多，除非您将它用作 Queue 或类似的东西。

I know I can add a if check but then I need to add if check four time just before adding to Linked List. Is there any better data structure which I can use here?

集合默默地忽略 nulls 将是一个坏主意。它有时可能很有用，而在其他时候可能会非常令人惊讶。此外，它会违反 List.add 合同。 所以你不会在任何严肃的库中找到它，你不应该实现它。

随便写个方法

void <E> addIfNotNullTo(Collection<E> collection, E e) {
     if (e != null) {
         collection.add(e);
     }
}

并使用它。它不会让您的代码真正变短，但会让代码更清晰。

One constraint I have is - This library is use under very heavy load so this code has to be fast since it will be called multiple times.

请注意，任何 IO 都比简单的列表操作慢很多数量级。

Answer 6

由于您使用 Guava（已标记），如果您有能力 return 一个 Collection 而不是 List，我有这个选择。

为什么 Collection？因为 List 强制您 return true 或抛出异常。 Collection 允许您 return false 如果您没有添加任何内容。

class MyVeryOwnList<T> extends ForwardingCollection<T> { // Note: not ForwardingList
  private final List<T> delegate = new LinkedList<>(); // Keep a linked list
  @Override protected Collection<T> delegate() { return delegate; }

  @Override public boolean add(T element) {
    if (element == null) {
      return false;
    } else {
      return delegate.add(element);
    }
  }

  @Override public boolean addAll(Collection<? extends T> elements) {
    return standardAddAll(elements);
  }
}

有空空闲列表数据结构吗？

Is there any null free list data structure?

java

linked-list

guava

data-structures