Java双链表克隆方法 [英] Java Doubly Linked List Clone Method

问题描述

我正在根据自己的时间编写一些数据结构的代码.我注意到克隆方法没有按预期复制列表.我将结果贴在代码下，因为main方法在类的底部附近.这是我到目前为止编写的课程:

I'm working on coding some data structures on my own time. I've noticed that the clone method is not copying the list as I expect. I'll post my results underneath the code as the main method is near the bottom of the class. Here is the class I have written so far:

public class DoublyLinkedList<E> implements Cloneable {
    //------------nested Node class------------
    private static class Node<E> {
        private E element;       // reference to stored element
        private Node<E> prev;    // reference to previous element
        private Node<E> next;    // reference to next element

    /** The constructor that creates a node */
    public Node(E e, Node<E> p, Node<E> n) {
        element = e;
        prev = p;
        next = n;
    }

    // methods
    /** getter for the element */
    public E getElement() {
        return element;
    }

    /** getter for previous node in list */
    public Node<E> getPrev() {
        return prev;
    }

    /** getter for next node in list */
    public Node<E> getNext() {
        return next;
    }

    /** setter for previous node */
    public void setPrev(Node<E> p) {
        prev = p;
    }

    /** setter for the next node */
    public void setNext(Node<E> n) {
        next = n;
    }
} //------------end of nested node class------------

// instance variables of DoublyLinkedList
private Node<E> header;     // head sentinel
private Node<E> trailer;    // tail sentinel
private int size = 0;       // number of elements in list

/** List constructor */
public DoublyLinkedList() {
    header = new Node<E>(null, null, null);      // create header
    trailer = new Node<E>(null, header, null);   // header precedes trailer
    header.setNext(trailer);                     // trailer follows header
}

// access methods
/** Returns the size of the doubly linked list */
public int getSize() {
    return size;
}

/** Tests whether the linked list is empty */
public boolean isEmpty() {
    return size == 0;
}

/** Returns but does not remove the first element in the list */
public E first() {
    if (isEmpty()) {
        return null;
    } else {
        return header.getNext().getElement();  // return first node's element
    }
}

/** Returns but does not remove the last element in the list */
public E last() {
    if (isEmpty()) {
        return null;
    } else {
        return trailer.getPrev().getElement();  // return last node's element
    }
}

//update methods
/** Adds element e to the front of the list */
public void addFirst(E e) {
    addBetween(e, header, header.getNext());
}

/** Adds element e to the back of the list */
public void addLast(E e) {
    addBetween(e, trailer.getPrev(), trailer);
}

/** Removes and returns the first element of the list */
public E removeFirst() {
    if (isEmpty()) {
        return null;
    } else {
        return remove(header.getNext());
    }
}

/** Removes and returns the last element of the list */
public E removeLast() {
    if (isEmpty()) {
        return null;
    } else {
        return remove(trailer.getPrev());
    }
}

// private update helpers
/** Does the heavy lifting for adding an element to the list */
private void addBetween(E e, Node<E> predecessor, Node<E> successor) {
    // create and link a new node
    Node<E> newest = new Node<>(e, predecessor, successor);
    predecessor.setNext(newest);
    successor.setPrev(newest);
    size++;
}

/** Does the heavy lifting for removing an element from the list */
private E remove(Node<E> node) {
    Node<E> predecessor = node.getPrev();
    Node<E> successor = node.getNext();
    predecessor.setNext(successor);
    successor.setPrev(predecessor);
    size--;
    return node.getElement();
}
// equals and clone methods
    /** Equals method currently assumes that the list must be of the same
     *  type in order to be equal. This means that a doubly linked list will
     *  not be equal to a circularly linked list or a singly linked list even
     *  if the elements are identical. Because of type erasure in Java, we have
     *  to use Objects and casts to handle any type rather than generics. */
    @SuppressWarnings({ "rawtypes" })
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }

        // at this point, the classes have to be the same.
        if (getClass() != o.getClass()) {
            return false;
        }

        DoublyLinkedList other = (DoublyLinkedList) o;  // use non-parameterized type (erasure)

        // the size must be the same for them to be equal
        if (size != other.size) {
            return false;
        }

        Node walkA = header;                             // traverse primary list
        Node walkB = other.header;                       // traverse secondary list

        // We don't want to compare the trailers, so size - 1
        for(int i = 0; i < size; i++) {
            if (!walkA.getElement().equals(walkB.getElement())) {
                return false; // mismatch
            }
            walkA = walkA.getNext();
            walkB = walkB.getNext();
        }
        return true;             // if we reach this, then they are equal.
    }

    /** The clone method that performs a deep clone of the list */
    @SuppressWarnings("unchecked")
    public DoublyLinkedList<E> clone() throws CloneNotSupportedException {
        // always use inherited Object.clone() to create initial copy
        DoublyLinkedList<E> other = (DoublyLinkedList<E>) super.clone(); // safe cast
        if (size > 0) {                      // we need independent node chain
            other.header = new Node<>(null, null, null);
            other.trailer = new Node<>(null, other.header, null);
            other.header.setNext(other.trailer);
            Node<E> walk = header.getNext();   // walk through remainder of original list
            Node<E> otherWalk = other.header;  
            for(int i = 0; i < size; i++) {           // make new node storing same element
                Node<E> newest = new Node<>(walk.getElement(), null, null);
                otherWalk.setNext(newest);   // link previous node to this one
                otherWalk = newest;
                otherWalk.setPrev(newest);   // link node back to the previous one
                walk = walk.getNext();
            }
        }
        return other;
    }

    /** Test driver for the circularly linked list class */
    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static void main(String args[]) {
        DoublyLinkedList theList = new DoublyLinkedList();
        DoublyLinkedList clonedList;
        theList.addFirst(1);
        theList.addFirst(2);
        theList.addLast(3);
        try {
            clonedList = theList.clone();
            System.out.println("Original List values");
            while(theList.first() != null) {
                System.out.println(theList.removeFirst());
            }

            System.out.println("Cloned List values");
            while(clonedList.first() != null) {
                System.out.println(clonedList.removeFirst());
            }
            System.out.println(theList.equals(clonedList));
        } catch (CloneNotSupportedException e) {
            System.err.println("I AM ERROR: List didn't clone.");
            e.printStackTrace();
        }
    }

} //------------ end of doubly linked list class ------------

此类中的主要方法仅用于测试.它应该非常简单.但是，无论何时运行此代码，我都会得到以下结果: 原始列表值 2个 1个 3 克隆清单值 2个 2个 2个 是

The main method in this class is just for testing. It should be pretty straightforward. However, whenever I run this code, I get the following result: Original List values 2 1 3 Cloned List values 2 2 2 true

我不确定为什么克隆列表"值与原始列表中的值不同.我尝试将代码中的2更改为4，以查看是否可以从克隆列表中获得3个4，确实如此.也许列表没有走动，并在列表中获取了n次元素.

I'm not sure why the Cloned List values are not the same as those in the original list. I tried changing the 2 in the code to a 4 to see if I would get three 4s out of my cloned list, and indeed I did. Perhaps the list is not walking and grabs the element at the front of the list n times.

你们中有人看到我的错误吗?

Do any of you see my mistake?

推荐答案

使用现有的API创建正确的DoubleLinkedList怎么样?

What about using the already existing API to create a correct DoubleLinkedList?

public DoublyLinkedList<E> clone() throws CloneNotSupportedException {
    // always use inherited Object.clone() to create initial copy
    DoublyLinkedList<E> other = new DoublyLinkedList<>();
    if (size > 0) {
        Node<E> walk = header.getNext();
        for(int i = 0; i < size; i++) {
            other.addLast(walk.getElement());
            walk = walk.getNext();
        }
    }
    return other;
}

这样，您不必担心多个地方的整个列表逻辑.

That way you don't have to worry about your entire list logic in multiple places.

或者保持当前的方法，您可以执行以下操作

Alternatively keeping your current approach you can do the following

public DoublyLinkedList<E> clone() throws CloneNotSupportedException {
    // always use inherited Object.clone() to create initial copy
    DoublyLinkedList<E> other = (DoublyLinkedList<E>) super.clone();
    if (size > 0) {
        other.header = new Node<>(null, null, null);
        other.trailer = new Node<>(null, other.header, null);
        other.header.setNext(other.trailer);
        Node<E> walk = header.getNext();
        Node<E> otherWalk = other.header;
        for(int i = 0; i < size; i++) {
            Node<E> newest = new Node<>(walk.getElement(), otherWalk, otherWalk.getNext());
            otherWalk.getNext().setPrev(newest);
            otherWalk.setNext(newest);
            otherWalk = otherWalk.getNext();
            walk = walk.getNext();
        }
    }
    return other;
}

这篇关于Java双链表克隆方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！