Java双向链表打印

Question

我已经多次发布此代码，如果您继续查看此问题，我深表歉意。我已经在这方面工作了一段时间，所以任何帮助都会有所帮助，到目前为止我已尽我所能。但是当我的程序打印数据时，它交换了 8 和 7，我不明白为什么!这是所有代码。而且我还没有开始制作我的删除方法，所以忽略该功能。

public class MyLinkedList<AnyType> implements Iterable<AnyType> {
    private int theSize;
    private Node<AnyType> beginMarker;
    private Node<AnyType> endMarker;

    public class Node<AnyType> {
        public Node(AnyType data, Node<AnyType> head, Node<AnyType> tail) {
            myData = data;
            myHead = head;
            myTail = tail;
        }

        public AnyType myData;
        public Node<AnyType> myHead;
        public Node<AnyType> myTail;

    }

    public MyLinkedList() {
        beginMarker = new Node(null, endMarker, null);
        endMarker = new Node(null, null, beginMarker);
        theSize = 0;
    }

    public void clear() {
        beginMarker.myHead = endMarker;
        endMarker.myTail = beginMarker;

    }

    public int size() {
        return theSize;
    }

    public boolean exist(AnyType newVal) {
        beginMarker.myHead.myData = newVal;

        if (newVal != null) {
            return true;
        }

        return false;
    }

    private void addBefore(Node<AnyType> previousNode, AnyType newNode) {
        Node<AnyType> new_node = new Node<>(newNode, previousNode.myTail, previousNode);

        new_node.myTail.myHead = new_node;
        previousNode.myTail = new_node;
        theSize++;
    }

    public boolean add(AnyType newVal) {
        {
            add(size(), newVal);
            return true;
        }
    }

    public boolean add(int index, AnyType newVal) {
        addBefore(getNode(index, 0, size()), newVal);

        return true;
    }

    private Node<AnyType> getNode(int index) {
        return getNode(index, 0, size() - 1);
    }

    public Node<AnyType> get(AnyType nodeData) {
        Node<AnyType> node = beginMarker;

        while (node != endMarker) {

            // Means node.data = nodeData
            if (node.myData.equals(nodeData)) {
                return node;
            }
        }
        return null;
    }

    // Added method
    private Node<AnyType> getNode(int index, int lower, int upper) {
        Node<AnyType> x;

        if (index < lower || index > upper)
            throw new IndexOutOfBoundsException();

        if (index < size() / 2) {
            x = beginMarker.myHead;
            for (int i = 0; i < index; i++)
                x = x.myHead;
        } else {
            x = endMarker.myTail;
            for (int i = size(); i > index; i--) {
                x = x.myTail;

            }
        }
        return x;
    }

    public void printList() {
        Node temp = beginMarker.myHead;

        while (temp != null) {
            System.out.println(temp.myData);
            temp = temp.myHead;
        }
    }

    public java.util.Iterator<AnyType> iterator() {
        return new LinkedListIterator();
    }

    public void remove(AnyType removeVal) {
        /*
         * if(node.myData.equals(nodeData))
         * 
         * MyLinkedList testList = new MyLinkedList();
         * 
         * Node temp = testList.beginMarker.myData; while(temp != null){
         * 
         * if(temp == removeVal){ temp.myTail = temp.myHead; temp.myHead =
         * temp.myTail; } else{ temp.myHead = temp; }
         * 
         * 
         * }
         */
    }

    private class LinkedListIterator implements java.util.Iterator<AnyType> {

        private Node<AnyType> node_ = beginMarker;

        public void remove() {

        }

        public boolean hasNext() {
            if (node_.myHead != null) {
                return true;
            }
            return false;
        }

        public AnyType next() {
            if (!hasNext()) {
                return null;
            }
            node_ = node_.myHead;
            return node_.myData;
        }
    }

    private static void testListIntegers() {
        MyLinkedList<Integer> testList = new MyLinkedList<Integer>();
        testList.add(new Integer(5));
        testList.add(new Integer(4));
        testList.add(new Integer(3));
        System.out.println(" We have so far inserted " + testList.size() + " elements in the list");
        testList.remove(4);
        System.out.println(" Now, there is only " + testList.size() + " elements left in the list");
        testList.add(1, new Integer(7));
        testList.add(2, new Integer(8));
        System.out.println(" About to print content of the list");
        testList.printList();
    }

    private static void testListStrings() {
        MyLinkedList<String> testList = new MyLinkedList<String>();
        testList.add(new String("hello"));
        testList.add(new String("this is"));
        testList.add(new String("cs3345 project 2"));
        System.out.println(" We have so far inserted " + testList.size() + " elements in the list");
        testList.remove("this is");
        System.out.println(" Now, there is only " + testList.size() + " elements left in the list");
        testList.add(1, "a modified version of");
        testList.add(2, "cs3345 project 2, call it version 2");
        System.out.println(" About to print content of the list");
        testList.printList();
    }

    public static void main(String args[]) throws Exception {
        // Add whatever code you need here
        // However, you will need to call both testListIntegers()
        // and testListStrings()
        testListIntegers();
        testListStrings();

    }
}

输出如下:

 We have so far inserted 3 elements in the list
 Now, there is only 3 elements left in the list
 About to print content of the list
8
7
3
4
5
 We have so far inserted 3 elements in the list
 Now, there is only 3 elements left in the list
 About to print content of the list
cs3345 project 2, call it version 2
a modified version of
cs3345 project 2
this is
hello

Answer 1

问题出在 addBefore 方法上:

private void addBefore(Node<AnyType> previousNode, AnyType newNode) {
    Node<AnyType> new_node = new Node<>(newNode, previousNode.myTail, previousNode);

    new_node.myTail.myHead = new_node;
    previousNode.myTail = new_node;
    theSize++;
}

它是一样的:

private void addBefore(Node<AnyType> previousNode, AnyType newNode) {
    Node<AnyType> new_node = new Node<>(newNode, previousNode.myTail, previousNode);

    previousNode.myHead = new_node;
    previousNode.myTail = new_node;
    theSize++;
}

所以基本上你正在破坏双向链表。

编辑:

根据算法描述here这个方法应该是这样的:

private void addBefore(Node<AnyType> previousNode, AnyType newNode) {
    Node<AnyType> new_node = new Node<>(newNode, previousNode, previousNode.myTail);
    if(previousNode.myTail==null){
        beginMarker.myHead = new_node;
    } else {
        previousNode.myTail.myHead = new_node;
    }
    previousNode.myTail = new_node;
    theSize++;
}

查看您的列表是从 0 开始索引的，因此输出应该是:

5
7
8
4
3

下一个问题是在 printList 方法中(无限循环)，因为某个地方错误地使用了开始/结束标记。