我正在处理一段很热的代码,我需要将一个LinkedList(l1)的元素添加到另一个LinkedList(l2)。

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

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

最佳答案

根据评论,目标是在级联列表上创建类似“ View ”的内容-这意味着不应复制数据。相反,给定的列表应像单个列表一样“出现”。

如何实现此目的的一种方法是扩展AbstractListget(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(),最终委托(delegate)给get(int),而AbstractSequentialList提供了“相反的”存根实现,例如最终委托(delegate)给get(int)iterator()。但是,这需要ListIterator<T>实现,这比上面的琐碎草图要复杂得多。

还要注意,我认为结果 View 应不可修改-但这应与给定的描述一致。

最后,请注意,(当然)已经有用于此任务和类似任务的实现,并且这些实现可能比上面概述的实现更复杂 。例如,Google Guava提供了不同的 Iterators#concat 方法,可让您串联多个迭代器。因此,如果您已经在使用 Guava ,则上面iterator()方法的实现可以归结为
@Override
public Iterator<T> iterator()
{
    return Iterators.concat(list0.iterator(), list1.iterator());
}

08-06 01:14
查看更多