有没有Java LinkedList的方法可以用作环形链表?

huangapple go评论74阅读模式
英文:

Is there a Java LinkedList method to use as a ring list?

问题

如果我有一个链表:

值 A B C D E F
索引 0 1 2 3 4 5

我想重新排列链表或者例如将索引为 D(索引 3)的元素作为新的头部,但保持顺序,如下:

值 D E F A B C
索引 0 1 2 3 4 5

这个功能是否可以直接通过链表来实现,基本上实现了一个环形结构?还有其他已经实现了这个功能的类吗?

英文:

If I have a LinkedList:

Value A B C D E F
Index 0 1 2 3 4 5

I want to reorder the list or an Iterator for example at D(index 3) to be the new head but keep the order like:

Value D E F A B C
Index 0 1 2 3 4 5

Is this a functionality that can be achieved with LinkedList out of the box, basically realizing a ring? Is there another class that offers this already implemented?

答案1

得分: 8

你可以对实现了 List 接口的类使用 Collections.rotate 方法:

List<String> list = Arrays.asList("A", "B", "C", "D", "E", "F");
Collections.rotate(list, 3);
System.out.println(list);

输出

[D, E, F, A, B, C]

英文:

You can use Collections.rotate for classes that implement the List interface:

List&lt;String&gt; list = Arrays.asList(&quot;A&quot;, &quot;B&quot;, &quot;C&quot;, &quot;D&quot;, &quot;E&quot;, &quot;F&quot;);
Collections.rotate(list, 3);
System.out.println(list);

Output:

[D, E, F, A, B, C]

答案2

得分: 2

不,这在Java中不能使用任何标准类来实现。您必须基于任何有序随机访问集合(如数组、列表)创建自己的实现。

以下解决方案可能不是最优的,但它可以工作,并且在5分钟内编写完成。

public static void main(String... args) throws IOException {
    Deque<Character> deque = new LinkedList<>();
    deque.addAll(Arrays.asList('A', 'B', 'C', 'D', 'E', 'F'));
    System.out.println(deque);
    reorder(deque, 3);
    System.out.println(deque);
    reorder(deque, 3);
}

public static void reorder(Deque<Character> deque, int offs) {
    offs %= deque.size();

    for (int i = 0; i < offs; i++)
        deque.add(deque.removeFirst());
}

输出:

[A, B, C, D, E, F]
[D, E, F, A, B, C]

附注: 正如您所看到的,该方法接受了Deque,因此您可以使用此接口的任何实现。

英文:

No, this is not possible using any standard class in Java. You have to create you own implementation base on any ordered random access collection like: Array, List.

Following solution probably not optimal, but it works and was written in 5 minutes.

public static void main(String... args) throws IOException {
    Deque&lt;Character&gt; deque = new LinkedList&lt;&gt;();
    deque.addAll(Arrays.asList(&#39;A&#39;, &#39;B&#39;, &#39;C&#39;, &#39;D&#39;, &#39;E&#39;, &#39;F&#39;));
    System.out.println(deque);
    reorder(deque, 3);
    System.out.println(deque);
    reorder(deque, 3);
}

public static void reorder(Deque&lt;Character&gt; deque, int offs) {
    offs %= deque.size();

    for (int i = 0; i &lt; offs; i++)
        deque.add(deque.removeFirst());
}

Output:

[A, B, C, D, E, F]
[D, E, F, A, B, C]

P.S. As you can see the method accepted Deque, so you could use any implementation of this interface.

答案3

得分: 2

以下是翻译好的内容:

这里有一个非常简单的方法,使用 List::subList(int fromIndex, int toIndex)

List<String> list = Arrays.asList("A", "B", "C", "D", "E", "F");

int index = list.indexOf("D"); // 或者是一个固定的数字,取决于你的实现

List<String> newList = new ArrayList<>();
newList.addAll(list.subList(index, list.size()));  // 右侧部分 [D, E, F] 首先
newList.addAll(list.subList(0, index));            // 左侧部分 [A, B, C] 其次

newList 将包含 [D, E, F, A, B, C],然而它并没有充分利用链式结构的优势。

英文:

Here is a really simple way using List::subList(int fromIndex, int toIndex):

List&lt;String&gt; list = Arrays.asList(&quot;A&quot;, &quot;B&quot;, &quot;C&quot;, &quot;D&quot;, &quot;E&quot;, &quot;F&quot;);

int index = list.indexOf(&quot;D&quot;); // or a fixed number, depends on your implementation

List&lt;String&gt; newList = new ArrayList&lt;&gt;();
newList.addAll(list.subList(index, list.size()));  // right part [D, E, F] first
newList.addAll(list.subList(0, index));            // left part [A, B, C] then

The newList will contain [D, E, F, A, B, C], however it doesn't use any advantage of the linked structures.

huangapple
  • 本文由 发表于 2020年8月19日 05:04:10
  • 转载请务必保留本文链接:https://go.coder-hub.com/63476590.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定