java - 在 Java 中实现特殊的链表方法

Question

是否可以在 Java 中创建一个链接列表，并能够在列表的中间（不仅仅是开头或结尾）的任何位置添加新链接 - 如果可能的话，无需在内存中复制粘贴列表的大部分以适应新链接的输入？

如果是这样，请发布您的示例！

Answer 1

您可以使用 LinkedList 来执行此操作。

List<Integer> ints = new LinkedList<Integer>();
for (int i = 0; i <= 10; i++)
    ints.add(i / 2, i);
System.out.println(ints);

印刷

[1, 3, 5, 7, 9, 10, 8, 6, 4, 2, 0]

如您所见，它一直在列表中间添加条目。

Answer 2

Java 中的LinkedList类已经通过它的add(index, element)方法做到了这一点。

Answer 3

在伪代码中，链接是一个很好的起点：

public LinkedList<E> implements List<E>{
    ...

    public void add(int index, E element){
        Node<E> current=findNodeAt(index);
        //add in your logic to insert this node at this location
        //probably something like (depending on your linking)
        element.setNext({current nodes next value})
        current.setnext(element);      
    }

    private Node<E> findNodeAt(index){
        //iterate through list until you reach the index or end of the list
        //then return that node
    }

    ...
}





public Node<E>{
    private Node<E> next;
    ... 

    Node<E> setNext(Node<E> next){
        Node<E> previousNext=next;
        this.next=next;
        return previousNext;
    }

    ...
}

Answer 4

LinkedList实现“列表”接口，它具有您需要的添加方法：http: //docs.oracle.com/javase/7/docs/api/java/util/List.html#add%28int,%20E%29