在双向链表中的旧链表之后添加新链表

Question

你好，我有一个界面；

public interface List<Type> {
    void addAll(List<Type> list);
    int addAll(int index, List<Type> list);    
}

以及如您所见的清晰实施；

public  class DoublyLinkedList<Type> implements List<Type> {
    @Override
    public void addAll(List<Type> list) {
        Node<Type> old = first();  //returns old linked list.Also I can call the tail node with 
        // tail variable.
    }
    
    @Override
    public int addAll(int index, List<Type> list) {
        // TODO Auto-generated method stub
        return 0;
    }
}

并有一个构造函数 class;

public class Node<Type> {
        
    protected Type data;
    protected Node<Type> next;
    protected Node<Type> previous;
            
            
    public Node(Type data, Node<Type> next,Node<Type> previous) {
        this.data = data;
        this.next = next;
        this.previous = previous;       
    }
            
    public Type getData() {
        return data;
    }
            
    public Node<Type> getNext() {
        return next;
    }
    
    public Node<Type> getPrevious() {
        return previous;
    }
}

我没有把我所有的方法都放在上面。因为我的项目所以，我的问题是如何实施这些方法？我想通过接口在旧的链表之后添加一个新的链表。

Answer 1

可能有不同的方法来实现您的要求。下面是我的实现。请注意，我更改了名称。我将接口命名为 Listing，以免与 java.util.List 冲突。此外，类型参数的约定是单个大写字母，因此我将 Type 更改为 T。我将 class Node 更改为 ListNode 因为已经有很多 Node classes。我还在 class ListNode 和 class DoublyLinkedList 中添加了一个 toString() 方法作为测试辅助。我还将方法 main() 添加到 class DoublyLinkedList 以便可以测试实现。最后，我将方法 add() 添加到 class DoublyLinkedList 以使得创建非空列表成为可能。

解释以下代码的工作原理需要大量文字，可能还需要几张图表。我建议您只是运行调试器中的代码，而不是那样做。大多数 IDE 都有调试器。

界面Listing

public interface Listing<T> {

    /**
     * Append 'list' to the end of this 'Listing'.
     *
     * @param list list to append.
     */
    void addAll(Listing<T> list);

    /**
     * Insert 'list' after element at 'index'. If 'index' greater than size of this
     * 'Listing', append 'list' to this 'Listing'.
     *
     * @param index insertion index
     * @param list  list to insert
     *
     * @return The index after which 'list' was inserted.
     */
    int addAll(int index, Listing<T> list);
}

Class ListNode

public class ListNode<T> {
    protected T data;
    protected ListNode<T> next;
    protected ListNode<T> previous;

    public ListNode(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public ListNode<T> getNext() {
        return next;
    }

    public ListNode<T> getPrevious() {
        return previous;
    }

    public String toString() {
        return String.format("<-%s->", String.valueOf(data));
    }
}

Class DoublyLinkedList

public class DoublyLinkedList<T> implements Listing<T> {
    private ListNode<T> head;

    public void add(T data) {
        ListNode<T> newNode = new ListNode<T>(data);
        if (head == null) {
            head = newNode;
        }
        else {
            ListNode<T> current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.previous = current;
        }
    }

    @Override
    public void addAll(Listing<T> list) {
        if (list instanceof DoublyLinkedList) {
            DoublyLinkedList<T> lst = (DoublyLinkedList<T>) list;
            if (lst.head != null) {
                if (head == null) {
                    head = lst.head;
                }
                else {
                    ListNode<T> current = head;
                    while (current.next != null) {
                        current = current.next;
                    }
                    current.next = lst.head;
                    lst.head.previous = current;
                }
            }
        }
    }

    @Override
    public int addAll(int index, Listing<T> list) {
        if (index < 0) {
            throw new IllegalArgumentException("Negative index.");
        }
        int counter = 0;
        if (list instanceof DoublyLinkedList) {
            DoublyLinkedList<T> lst = (DoublyLinkedList<T>) list;
            if (lst.head != null) {
                if (head == null) {
                    if (index == 0) {
                        head = lst.head;
                    }
                }
                else {
                    ListNode<T> current = head;
                    while (current.next != null && counter < index) {
                        counter++;
                        current = current.next;
                    }
                    if (counter < index) {
                        current.next = lst.head;
                        lst.head.previous = current;
                    }
                    else {
                        current.previous.next = lst.head;
                        ListNode<T> tmp = current;
                        ListNode<T> curr = lst.head;
                        while (curr.next != null) {
                            curr = curr.next;
                        }
                        curr.next = tmp;
                        curr.previous = tmp.previous;
                        tmp.previous = curr;
                    }
                }
            }
        }
        return counter;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (head != null) {
            ListNode<T> current = head;
            while (current != null) {
                sb.append(current);
                current = current.next;
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        DoublyLinkedList<String> list1 = new DoublyLinkedList<>();
        list1.add("One");
        DoublyLinkedList<String> list2 = new DoublyLinkedList<>();
        list2.add("First");
        list1.addAll(list2);
        System.out.println(list1);
        DoublyLinkedList<String> list3 = new DoublyLinkedList<>();
        list3.add("TOO");
        int result = list1.addAll(1, list3);
        System.out.printf("[%d] %s%n", result, list1);
    }
}

在双向链表中的旧链表之后添加新链表

Adding new linked list after old linked list in a doubly-linked list

java

data-structures

generic-list