在恒定时间内连接两个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设置为指向l2的第一个Node.但是我找不到适合的方法吗?我需要自己的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提供了相反的"存根实现，例如最终委托给iterator()的get(int).但是，这需要一个ListIterator<T>实现，它比上面的琐碎草图要复杂得多.

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提供了不同的

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屋！