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

Question

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

不可能使用 addAll(Collection) 方法，因为它使用 Iterator 遍历整个 Collection。

在我看来，应该可以将 l1 的最后一个 Node 设置为指向 的第一个 Node >l2。但是我找不到合适的方法吗？我是否需要自己的 LinkedList 实现才能获得它？

Answer 1

根据评论，目标是在串联列表上创建类似于“ View ”的东西 - 这意味着数据应该不被复制。相反，给定的列表应该像单个列表一样“出现”。

如何实现这一点的一种方法是扩展 AbstractList . get(int)的执行和 size()相当微不足道。关键点是创建一个 Iterator对于串联列表。以下是如何实现这一点的非常简单的草图(但请参阅下面的注释)

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提供 stub 实现，例如的 iterator() ，最终委托(delegate)给 get(int) ，而 AbstractSequentialList提供“相反的” stub 实现，例如的 get(int)最终委托(delegate)给 iterator() .但是，这需要 ListIterator<T>实现，这比上面的简单草图要复杂一些。

另请注意，我假设生成的 View 应该不可修改 - 但这应该符合给定的描述。

最后，请注意，(当然)已经有此任务和类似任务的实现，并且这些实现可能比上面概述的远复杂。例如，Google Guava 提供不同的 Iterators#concat 允许您连接多个迭代器的方法。因此，如果您已经在使用 Guava，请执行 iterator()上面的方法可以归结为

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