在常数时间内连接两个java.util.LinkedList

Question

我正在处理一些热门代码，需要将一个LinkedList (l1)的元素添加到另一个LinkedList (l2)中。

由于addAll(Collection)方法使用Iterator遍历整个Collection，因此无法使用该方法。

我认为只需将l1的最后一个Node指向l2的第一个Node就可以实现。但是我找不到合适的方法？我需要自己实现一个LinkedList来完成吗？

- user3663882

---

似乎标准的LinkedList实现不支持这个功能，可以参考这个SO帖子。 - Tim Biegeleisen

只使用一个列表的列表并在以后迭代它们是否有意义？ - Silverclaw

我认为 google-collections Iterables.concat 是你正在寻找的：https://dev59.com/lXE95IYBdhLWcg3wCJNf#2494530 - Jordi Castilla

你应该会发现将一个ArrayList附加到另一个ArrayList上会更快，因为指针追踪的次数更少。 - Peter Lawrey

您需要结果是具有特定功能的 LinkedList 吗？还是仅实现 List 接口就足够了？您确定不会对结果列表进行索引访问，而是仅仅通过迭代器进行迭代吗？（将两个列表简单地包装成一个继承 AbstractList 的新类，并提供一个简单的“连接迭代器”可能是可能的） - Marco13

Answer 1

根据评论，目标是创建类似于连接列表的“视图”，这意味着数据不应该被复制。相反，给定的列表应该“显示”为单个列表。

实现这一点的一种方法是扩展AbstractList。get(int)和size()的实现相当简单。关键点是为连接列表创建一个迭代器。以下是如何实现这一点的非常简单的草图（但请参见下面的注释）。

import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class MergedListTest
{
    public static void main(String[] args)
    {
        testBasic();
        testEmptyA();
        testEmptyB();
    }

    private static void testBasic()
    {
        List<Integer> list0 = Arrays.asList(0,1,2);
        List<Integer> list1 = Arrays.asList(3,4,5);
        List<Integer> expected = Arrays.asList(0,1,2,3,4,5);
        List<Integer> actual = new MergedList<Integer>(list0, list1);
        System.out.println(actual.equals(expected));
    }

    private static void testEmptyA()
    {
        List<Integer> list0 = Collections.emptyList();
        List<Integer> list1 = Arrays.asList(3,4,5);
        List<Integer> expected = Arrays.asList(3,4,5);
        List<Integer> actual = new MergedList<Integer>(list0, list1);
        System.out.println(actual.equals(expected));
    }

    private static void testEmptyB()
    {
        List<Integer> list0 = Arrays.asList(0,1,2);
        List<Integer> list1 = Collections.emptyList();
        List<Integer> expected = Arrays.asList(0,1,2);
        List<Integer> actual = new MergedList<Integer>(list0, list1);
        System.out.println(actual.equals(expected));
    }

}


class MergedList<T> extends AbstractList<T>
{
    private final List<T> list0;
    private final List<T> list1;

    MergedList(List<T> list0, List<T> list1)
    {
        this.list0 = list0;
        this.list1 = list1;
    }

    @Override
    public T get(int index)
    {
        if (index < list0.size())
        {
            return list0.get(index);
        }
        return list1.get(index - list0.size());
    }

    @Override
    public Iterator<T> iterator()
    {
        return new Iterator<T>() 
        {
            private Iterator<T> current = list0.iterator();
            private boolean first = true;

            @Override
            public boolean hasNext() 
            {
                return current != null && current.hasNext();
            }

            @Override
            public T next() 
            {
                T result = current.next();
                if (!current.hasNext())
                {
                    if (first)
                    {
                        current = list1.iterator();
                    }
                    else
                    {
                        current = null;
                    }
                }
                return result;
            }
        };
    }

    @Override
    public int size()
    {
        return list0.size() + list1.size();
    }
}

从概念上讲，从AbstractSequentialList继承更有意义: AbstractList提供了存根实现，例如iterator()，最终委托给get(int)，而AbstractSequentialList提供了相反的存根实现，例如get(int)，最终委托给iterator()。但是，这需要一个ListIterator<T>实现，比上面简单的草图要棘手一些。

还要注意，我假设生成的视图应该是不可修改的 - 但这应该符合给定的描述。

最后，请注意已经有针对此类任务的实现方法，这些实现可能比上面草图中的实现要复杂得多。例如，Google Guava提供了不同的Iterators＃concat方法，允许您连接多个迭代器。因此，如果您已经在使用Guava，则上述iterator()方法的实现可以简化为

@Override
public Iterator<T> iterator()
{
    return Iterators.concat(list0.iterator(), list1.iterator());
}

- Marco13

Answer 2

不可以。你不能通过O(1)的时间复杂度将两个java.util.LinkedList相加得到另一个LinkedList。

从概念上讲，确实可以通过O(1)的时间复杂度将两个LinkedList数据结构相加，但是需要以正确的方式进行实现。正如你所提到的，实现应该通过将最后一个节点连接到第一个节点来合并两个列表，并且不会遍历任何一个列表。

- isak gilbert

Answer 3

看起来标准库不支持所需的功能。但是，您可以使用反射来实现合并链表时的常数时间。

我还没有充分测试以下代码，只是为了展示如何实现：

public class ListConcatenation {

public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException, ClassNotFoundException {
    LinkedList<String> list1 = new LinkedList<>();
    list1.add("a");
    list1.add("b");
    list1.add("c");

    LinkedList<String> list2 = new LinkedList<>();
    list2.add("d");
    list2.add("e");
    list2.add("f");

    System.out.println(merge(list1, list2));
}

public static List<String> merge(List<String> list1, List<String> list2) throws NoSuchFieldException, IllegalAccessException, ClassNotFoundException {
    Field first = getDeclaredField(LinkedList.class, "first");
    Field last = getDeclaredField(LinkedList.class, "last");
    Field size = getDeclaredField(LinkedList.class, "size");

    Class<?> nodeClass = Class.forName("java.util.LinkedList$Node");
    Field next = nodeClass.getDeclaredField("next");
    next.setAccessible(true);

    Object list1Last = last.get(list1);
    Object list2First = first.get(list2);
    Object list2Last = last.get(list2);

    // link the last element of list1 with the first element of list2
    next.set(list1Last, list2First);
    // set last element of list1 equal to the last element of list2
    last.set(list1, list2Last);
    // update list1 size
    size.set(list1, list1.size() + list2.size());

    return list1;
}

private static Field getDeclaredField(Class<?> clazz, String name) throws NoSuchFieldException {
    Field field = clazz.getDeclaredField(name);
    field.setAccessible(true);
    return field;
}

}

- Michael Potter

---

这确实是一个“hacky”的解决方案，因为它涉及到了java.util.LinkedList的具体实现细节，所以不能保证在未来（或过去）的Java版本中能正常工作。这不是建议使用的解决方案。 - Jesper