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

Question

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

它不可能使用addAll(Collection)方法Iterator来迭代整个方法Collection.

在我看来,它应该是可以只设置最后Node的l1指向第一Node的l2.但我找不到合适的方法吗？我需要自己的LinkedList实现来实现吗？

Answer 1

根据该意见,我们的目标是创造这样拼接列表上的"视图" -这意味着该数据应该不会被复制.相反,给定的列表应该"出现"像一个列表.

如何实现这一点的一种方法是扩展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提供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());
}

Answer 2

标准库似乎不支持所需的功能。但是，您可以在合并链表时使用反射来实现恒定时间。我还没有正确测试以下代码，只是为了展示如何实现它：

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;
}

}