Java中LinkedList的最简遍历方式及两种实现的性能疑问

先看你提供的代码：

public static void main(String[] args) {
    LinkedList<Integer> pres = new LinkedList<Integer>();
    pres.add(112);
    pres.add(114);
    pres.add(326);
    pres.add(433);
    pres.add(119);
// ---------------------------------- METHOD 1 ---------------------------------
    for (int i = 0; i < pres.size(); i++) {
        System.out.print(pres.get(i) + (i == pres.size() - 1 ? "" : ","));
    }

// ---------------------------------- METHOD 2 ---------------------------------
    for (int courseIndex : pres) {
        System.out.print(courseIndex + (courseIndex == pres.getLast() ? "" : ","));
    }
}

针对你的疑问逐一解答：

1. 方法1中pres.get(i)的遍历机制 #

Java的LinkedList基于双向链表实现，但get(int index)方法每次都会从头或尾开始遍历，不会在上一次的位置继续移动。具体逻辑是：如果索引小于链表长度的一半，就从头部开始遍历到目标索引；如果大于等于一半，就从尾部开始遍历。因此方法1的时间复杂度是O(n²)，数据量大时性能会很差。

2. 方法2的foreach与getLast的性能问题 #

• foreach循环本质是通过LinkedList的ListIterator实现的，迭代器会维护当前遍历的节点指针，每次移动到下一个节点都是O(1)操作，遍历整个链表的时间复杂度为O(n)，确实避免了方法1的O(n²)问题。
• Java的LinkedList是双向链表，内部维护了first和last两个指针，所以getLast()是O(1)操作，直接返回last节点的元素。但方法2存在逻辑隐患：如果后续链表出现与最后一个元素重复的值（即使当前无重复），会提前停止添加逗号，导致格式错误；另外每次循环调用getLast()虽为O(1)，但完全可以提前缓存最后一个元素来减少不必要的调用。

Java中遍历LinkedList的最简方式 #

如果要实现无重复元素的LinkedList按逗号分隔打印，最简且高效的方式有两种：

方式一：迭代器手动处理逗号（兼容性好） #

Iterator<Integer> it = pres.iterator();
if (it.hasNext()) {
    System.out.print(it.next());
    while (it.hasNext()) {
        System.out.print("," + it.next());
    }
}

仅遍历一次链表，时间复杂度O(n)，逻辑清晰无冗余判断。

方式二：Java 8+ Stream API（代码最简洁） #

System.out.println(String.join(",", pres.stream().map(String::valueOf).toArray(String[]::new)));

利用String.join直接完成拼接，底层采用高效遍历实现，代码极简。

内容的提问来源于stack exchange，提问作者Miles