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

9ceoxa92  于 2021-07-06  发布在  Java
关注(0)|答案(1)|浏览(425)

你好,我有一个接口;

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;
    }
}

有一个构造函数类;

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;
    }
}

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

flmtquvp

flmtquvp1#

可能有不同的方法来实现您的需求。下面是我的实现。注意我改了名字。我给接口命名了 Listing 以免与…发生冲突 java.util.List . 类型参数的约定也是一个大写字母,所以我改了 TypeT . 我换了班 NodeListNode 因为已经有很多 Node 班级。我还添加了一个 toString() 方法到类 ListNode 还有上课 DoublyLinkedList 作为测试辅助。我还添加了方法 main() 上课 DoublyLinkedList 使测试实现成为可能。最后,我添加了方法 add() 上课 DoublyLinkedList 使创建非空列表成为可能。
解释下面的代码是如何工作的需要大量的文本,可能还需要一些图表。与其这样做,我建议您只需在调试器中运行代码。大多数ide都有一个调试器。
接口 Listing ```
public interface Listing {

/**
 * 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);

}

班级 `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));
    }
}

班级 DoublyLinkedList ```
public class DoublyLinkedList implements Listing {
private ListNode 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);
}

}

相关问题