为什么List没有tail()或head()方法来获取最后一个或第一个元素？

Question

我最近和一个同事讨论了为什么Java中的List接口没有head()和tail()方法。

为了实现这样的功能，我们需要编写一个类似下面这样的包装器：

public E head() {
 if (underlyingList == null || underlyingList.isEmpty())
  return null;
 
 return underlyingList.get(0);
}


public E tail() {
 if (underlyingList == null || underlyingList.isEmpty())
  return null;
 
 return underlyingList.get(underlyingList.size()-1);
}

我对所有的List实现都不太了解，但我认为至少在LinkedList和ArrayList中，获取最后和第一个元素应该是非常简单的（常数时间）。

所以问题是：

是否有特定的原因，不建议为任何List实现提供一个tail方法？

- leifg

---

DequeжО•еП£дЄ≠ињШжЬЙgetFirst()еТМgetLast()жЦєж≥ХгАВ - michael667

传统上，tail 函数应该返回列表中除了头部以外的元素。这是任何函数式语言都会返回的结果。 - Renato

@Renato是正确的。那不是一个尾部方法。这个问题的答案说“这很简单”，因此不适用于尾部，只适用于头部。 - SigmaX

因术语使用不当，该问题已被投下反对票。请重新措辞问题，将“head”替换为“last”（至少在这里实现的是Haskell名称）。 - jameshfisher

很抱歉这让你感到困惑，但在Java API文档中，“head”和“tail”这些术语被多次使用，所以我认为在此上下文中它们是正确的术语。 - leifg

Answer 1

List接口有一个subList方法，几乎相当于head和tail。您可以按以下方式进行包装

public List head(List list) {
    return list.subList(0, 1);
}

public List tail(List list) {
    return list.subList(1, list.size());
}

编辑

按照 @Pablo Grisafi 的回答，这里是一个 Java 快速排序的实现 - 不是泛型的，也不高效。正如预期的那样，head() 应该返回一个元素而不是列表。

public class QSort {

    public static List<Integer> qsort(List<Integer> list) {
        if (list.isEmpty()) {
            return list;
        } else {
            return merge(
                    qsort(lesser
                            (head(list), tail(list))),
                    head(list),
                    qsort(greater(
                            head(list), tail(list)))
            );
        }
    }

    private static Integer head(List<Integer> list) {
        return list.get(0);
    }

    private static List<Integer> tail(List<Integer> list) {
        return list.subList(1, list.size());
    }

    private static List<Integer> lesser(Integer p, List<Integer> list) {
        return list.stream().filter(i -> i < p).collect(toList());
    }

    private static List<Integer> greater(Integer p, List<Integer> list) {
        return list.stream().filter(i -> i >= p).collect(toList());
    }

    private static List<Integer> merge(List<Integer> lesser, Integer p, List<Integer> greater) {
        ArrayList list = new ArrayList(lesser);
        list.add(p);
        list.addAll(greater);

        return list;
    }

    public static void main(String[] args) {
        System.out.println(qsort(asList(7, 1, 2, 3, -1, 8, 4, 5, 6)));
    }
}

- David Soroko

---

“head” 方法应该返回一个元素而不是子列表，即 public <T> T head(List<T> list) { return list.get(0); }。 - Jan Molak

你也可以这样做。这可能符合“head”和“tail”的常见含义。 - David Soroko

终于有人知道tail()应该是什么了。 - Lawrence Dol

@averasko，我认为在空列表上定义head() / tail()是无效的。 - David Soroko

如果您认为在空列表上调用head / tail是异常情况，那么可以抛出异常。但请注意，许多列表处理习惯用法（特别是递归/函数式）认为这种情况完全有效。 - David Soroko

Answer 2

Java集合框架由Joshua Bloch编写。他的API设计原则之一是： 高功率重量比。

tail()和head()可以通过get()和size()实现，因此不必将tail()和head()添加到非常通用的接口java.util.List中。一旦用户使用这些方法，您就没有机会将它们删除，并且必须永久维护这些不必要的方法。这很糟糕。

- 卢声远 Shengyuan Lu

---

问题在于这些方法并非多余的——如果没有它们，函数式列表处理会非常麻烦。 - Aivar

不只是麻烦，它还没什么用。假设我有一个懒加载列表，我想获取它的尾部。我该怎么办？而且为了得到列表的尾部，我必须遍历整个列表以计算其长度。这太浪费了。 - divs1210

这听起来像是Oracle在其数据库中没有布尔值的论据。 - dstibbe

Answer 3

如果您想在函数式编程中递归处理列表，通常会使用头和尾部，这时您可以使用Iterator（迭代器）。

Integer min(Iterator<Integer> iterator) {
    if ( !iterator.hasNext() ) return null;
    Integer head = iterator.next();
    Integer minTail = min(iterator);
    return minTail == null ? head : Math.min(head, minTail);
}

- Kevin Wong

Answer 4

在我看来，tail和head这两个词对于有函数编程背景的人更为熟悉。当你开始传递函数时，它们非常有用，这就是为什么大多数函数式语言都已经实现了它们，并且甚至已经有了快捷方式来引用它们，比如在Haskell中或者即使在Scala中（即使它不是那么函数式，我知道）。

在“(几乎)所有东西都是对象但方法是以过程方式创建的”Java世界中，传递函数至少是困难的，而且总是笨拙的，因此head/tail方法并不是那么有用。

例如，请查看这个Haskell实现的快速排序：

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

它依赖于诸多因素，包括易于分离头部和尾部的能力，以及使用谓词过滤集合的能力。Java实现（请参考http://www.vogella.de/articles/JavaAlgorithmsQuicksort/article.html）看起来完全不同，它更低级，并且不依赖于分离头部和尾部。
注意：下一个句子是完全主观的，基于我的个人经验，可能被证明是错误的，但我认为这是真的：
大多数函数式编程算法依赖于头/尾，在过程式编程中，您依赖于访问给定位置的元素。

- Pablo Grisafi

---

我尝试在我的答案中使用Java实现函数式快速排序。虽然不像Haskell那样简洁，但是可行的。 - David Soroko

Answer 5

List 是 SequencedCollection

自从 Java 21 版本以来，有一个 SequencedCollection 接口，它是 List 的超接口。除了其他方法外，它还提供了 getFirst() 和 getLast() 方法：

jshell> List.of(1, 2, 3, 4, 5).getFirst() = 1
jshell> List.of(1, 2, 3, 4, 5).getLast() = 5

- Nolequen

Answer 6

据我所知，List 没有 element 方法。然而，LinkedList 有 getFirst() 和 getLast() 方法，可以实现您所描述的功能。

- Daniel

---

“Get last” 不等同于 “tail”。 - Mark Canlas

问题错误地定义了tail()，并且答案也重复了这个错误。 - SigmaX

Answer 7

在良好的 API 设计中，总是必须做出选择。有许多方法可以添加到 API 中，但您必须找到使 API 对大多数人可用的细微差别，并避免使其过于混乱和冗余。目前，您可以按照您展示的方式以高效的方式为大多数列表实现实现 tail 方法，而 LinkedList 已经有了 getLast() 方法。

- jtahlborn

---

这个答案复制了问题中的错误，从而给tail()函数提供了错误的定义。Tail表示列表除去头部，而不是列表的最后一个元素。 - Lawrence Dol

@LawrenceDol - 看起来你的问题是关于问题本身，而不是这个答案，因为这个答案已经按照问题所问进行了回答。你的解释似乎是维基百科中两种有效解释之一：“列表的‘尾部’可能指头部后面的其余部分，也可能指列表中的最后一个节点。” - jtahlborn

@LawrenceDol - 请撤回您错误的负评。 - jtahlborn

Answer 8

你可以在列表上获取那些可用于Stream的：

头部

myList.stream().findFirst() // Optional<T>, return empty for empty list

尾部（传统意义）

myList.stream().skip(1).collect(toList()) // or don't collect & continue with a Stream

最后一个（如果列表是无限的可能会很危险！）：

myList.stream().reduce((a,b) -> b) // Optional<T>, return empty for empty list

- Juh_

Answer 9

你应该使用列表，这样会更容易。 当你在列表上使用递归时，你需要这样思考... 列表有一个头部（第一个元素）和一个尾部（除了头部的所有其他元素）。 使用递归，你需要对头部执行想要的操作，然后在尾部调用函数，这样你总是有一个大小为 size - 1 的列表。

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    
    list.add(11);
    list.add(12);
    list.add(0);
    list.add(3);
    list.add(1);
    list.add(4);
    list.add(11);
    
    System.out.println(countOccurrences(list, 11));
    
}



public static int countOccurrences(List<Integer> list, int n) {
    if (list.size() == 0) {//if list is empty return 0
        return 0;
    }else {
        if(list.get(0) == n) {//if head of list is equal to n add 1 and call the function on the tail of the list
            return 1 + countOccurrences(list.subList(1, list.size()), n);
        }else {//else if it's not equal to n call the function on the tail of the list without adding 1
            return countOccurrences(list.subList(1, list.size()), n);
        }
    }
}

- AlexM28

Answer 10

peekLast 方法已经在 Deque 接口中定义。
此外，Deque 必须具有这样的功能。因此，在 List 或任何其他接口中定义它是没有意义的。
将功能拆分开来只是为了方便。如果您需要随机访问，则应实现 List。如果您需要高效地访问尾部，则应实现 Deque。您可以轻松地实现它们两个（LinkedList 实际上就是这样做的）。

- default locale

---

这个答案复制了问题中的错误，导致tail()函数的定义不正确。Tail的意思是列表减去头部，而不是列表的最后一个元素。 - Lawrence Dol

@LawrenceDol，你的定义并不是唯一的。例如，请查看Deque.peekLast的javadoc，“此deque的尾部，如果此deque为空，则为null”。Java集合的文档将尾部定义为最后一个元素。原始问题也使用了这个定义。 - default locale