在恒定时间内连接两个 java.util.LinkedList [英] Concatenate two java.util.LinkedList in constant time

问题描述

我正在编写一段非常热门的代码，我需要将一个 LinkedList (l1) 的元素添加到另一个 LinkedList (l2).

I'm working on some piece of code, which is quite hot, and I need to add elements of one LinkedList (l1) to another LinkedList (l2).

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

It's not possible to use addAll(Collection) method as it uses Iterator to iterate over the entire Collection.

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

It seems to me that it should be possible to just set the last Node of l1 to point to the first Node of l2. But I couldn't find any suitable method for this? Do I need my own LinkedList implementation to get that?

推荐答案

根据评论，目标是在连接列表上创建类似视图"的东西 - 意味着数据应该不 被复制.相反，给定的列表应该像单个列表一样出现".

According to the comments, the goal is to create something like a "view" on the concatenated list - meaning that the data should not be copied. Instead, the given lists should "appear" like a single list.

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

One way of how this could be implemented is to extend AbstractList. The implementation of get(int) and size() are fairly trivial. The crucial point is to create an Iterator for the concatenated list. The following is a very simple sketch of how this could be accomplished (but see the notes below)

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 实现，这比上面的简单草图要复杂一些.

Conceptually, it would make more sense to inherit from AbstractSequentialList: The AbstractList offers stub implementations, e.g. of iterator(), that eventually delegate to get(int), whereas AbstractSequentialList offers the "opposite" stub implementations, e.g. of get(int) that eventually delegate to iterator(). However, this requires a ListIterator<T> implementation, which is a bit more fiddly than the trivial sketch above.

另请注意，我假设生成的视图应该不可修改 - 但这应该与给定的描述一致.

Also note that I assumed that the resulting view should be unmodifiable - but this should be in line with the given description.

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

And finally, note that there are (of course) already implementations for this and similar tasks, and these implementations may be far more sophisticated than the one sketched above. For example, Google Guava offers different Iterators#concat methods that allow you to concatenate multiple iterators. So if you are already using Guava, the implementation of the iterator() method above could boil down to

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

这篇关于在恒定时间内连接两个 java.util.LinkedList的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！