java - Java中的LinkedList数据结构

Question

我正在处理一个 LinkedList，我想打印所有值及其先前的列表值。我收到 NullPointerException。我该如何修正程序？

我有一些额外的方法，但如果我觉得它们与程序的上下文无关，我可以删除它们。向前打印链接列表的方法名为 display，而打印包含先前值的值的方法名为 displayInDetails。

谢谢。

import java.util.* ;

class Node {

    public int data;    
    public Node next; 
    public Node previous; 

    public Node( int data ){

        this.data = data;
    }

    public Node (){

    }

    public void display(int data ){

        System.out.print( Integer.toString(data));
    }
}


class Result {

    public  Node node;
    public int count;

    public Result( Node n, int c) {
        node = n;
        count = c;
    }

}

class IntWrapper {

    public int value = 0;

}


public class LinkedList {

    public Node head; 
    public Node tail; 
    public Node current; 

    LinkedList(){

        head = null;
        tail = null;
        current = null;         

    }

    public boolean isEmpty(){

        return(head == null);       
    }

    public void insertToTail( int data){

        Node newNode = new Node(data);
        Node tmp = tail; 
        // 

        if (head == null ){

            head = newNode;
            tail = head;

        }

        else {

            tail.next = newNode;
            tail = newNode;
        }   

        tail.previous = tmp;
        head.previous = null; 

    }

    public Node removeFirst(){

        Node linkReference = head;

        if(!isEmpty()){

            // Removes the Link from the List

            head = head.next;

        } else {

            System.out.println("Empty LinkedList");

        }

        return linkReference;

    }

    public void display(){

        Node current = head;
        List<Node> myNodeList = new ArrayList<Node>();

        System.out.println();
        while(current != null){

            System.out.print( current.data );

            if ( myNodeList.contains(current))
                break;

            myNodeList.add(current);

            if (current.next != null)
                System.out.print(" -> ");
            current = current.next;         
        }

        System.out.println();

    }


    public void displayInDetails(){


        Node current = head;
        List<Node> myNodeList = new ArrayList<Node>();

        System.out.println();

        while(current != null){

            if ( current.previous != null || current != null )
                System.out.println( current.previous.data + " <-"+ current.data ) ;

            if ( myNodeList.contains(current))
                break;

            myNodeList.add(current);

            current = current.next;         
        }

        System.out.println();

    }


    public int getLength ( ){

        int length = 0;
        // LinkedList ll = this;

        if (this==  null)
            return -1;

        Node current = this.head;

        while( current != null){

            length += 1;
            current = current.next;
        }

        return length;

    }


    public Node getNode( int data){

        Node theLink = head;

        if(!isEmpty()){

            while(theLink.data != data ){

                // Checks if at the end of the LinkedList

                if(theLink.next == null){

                    // Got to the end of the Links in LinkedList
                    // without finding a match

                    return null;

                } else {

                    // Found a matching Link in the LinkedList

                    theLink = theLink.next;

                }

            }

        } else {

            System.out.println("Empty LinkedList");

        }

        return theLink;

    }

    public Node removeLink(int data){

        Node currentLink = head;
        Node previousLink = head;

        // Keep searching as long as a match isn't made

        while(currentLink.data != data){

            // Check if at the last Link in the LinkedList

            if(currentLink.next == null){

                // bookName not found so leave the method

                return null; 

            } else {

                // We checked here so let's look in the
                // next Link on the list

                previousLink = currentLink; 
                currentLink = currentLink.next;
            }

        }

        if(currentLink == head){

            // If you are here that means there was a match
            // in the reference stored in head in the
            // LinkedList so just assign next to head

            head = head.next;

        } 

        else {

            // If you are here there was a match in a Link other 
            // than the head. Assign the value of next for
            // the Link you want to delete to the Link that's 
            // next previously pointed to the reference to remove

            System.out.println("FOUND A MATCH");
            System.out.println("currentLink: " + currentLink);
            System.out.println("head: " + head);

            previousLink.next = currentLink.next;

        }

        return currentLink; 
    }

    /* question 2-1 */
    /* remove the duplicates from an unsorted linked list */
    public static void deleteDupsB( Node head) {

        if (head == null) return;

        Node current = head;
        while (current != null) {
            /* Remove all future nodes that have the same value */
            Node runner = current;
            while (runner.next != null) { 
                if (runner.next.data == current.data) {
                    runner.next = runner.next.next;
                } else {
                    runner = runner.next;
                }
            }
            current = current.next;
        }
    }

    public static void deleteDupsA( Node n) {

        HashSet<Integer> set = new HashSet<Integer>();
        Node previous = null;
        while (n != null) {
            if (set.contains(n.data)) {
                previous.next = n.next;
            } else {
                set.add(n.data);
                previous = n;
            }
            n = n.next;
        }
    }


    public static void deleteDupsC( Node head) {

        if (head == null) return;

        Node previous = head;
        Node current = previous.next;

        while ( current != null ) {

            // Look backwards for dups, and remove any that you see.
            Node runner = head;

            while (runner != current) { 

                if (runner.data == current.data) {

                    Node tmp = current.next;
                    previous.next = tmp;
                    current = tmp;

                    /* 
                        We know we can't have more than one dup preceding
                        our element since it would have been removed 
                        earlier. 
                    */
                    break;
                }
                runner = runner.next;
            }

            /* If runner == current, then we didn't find any duplicate 
             * elements in the previous for loop.  We then need to 
             * increment current.  
             * If runner != current, then we must have hit the ‘break’ 
             * condition, in which case we found a dup and current has
             * already been incremented.*/
            if (runner == current) {
                previous = current;
                current = current.next;
            }
        } 
    }
    /* end of question 2-1 */


    /* question 4-2 */
    /* get the n-th number from last in a linked list */
    public static Node nthToLast( Node head, int n) {

        Node p1 = head;
        Node p2 = head;

        if (n <= 0) return null;

        // Move p2 n nodes into the list.  Keep n1 in the same position.
        for (int i = 0; i < n - 1; i++) { 
            if (p2 == null) {
                return null; // Error: list is too small.
            }
            p2 = p2.next;
        }

        if (p2 == null) { // Another error check.
            return null;
        }

        // Move them at the same pace.  When p2 hits the end, 
        // p1 will be at the right element.
        while (p2.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

    public static Result nthToLastR3Helper( Node head, int k) {

        if (head == null) {
            return new Result(null, 0);
        }

        Result res = nthToLastR3Helper( head.next, k);
        if (res.node == null) {
            res.count++;
            if (res.count == k) {
                res.node = head;
            } 
        }
        return res;
    }

    public static Node nthToLastR3( Node head, int k) {

        Result res = nthToLastR3Helper(head, k);
        if (res != null) {
            return res.node;
        }
        return null;
    }       


    public static int nthToLastR1( Node head, int n) {

        if (n == 0 || head == null) {
            return 0;
        }
        int k = nthToLastR1(head.next, n) + 1;
        if (k == n) {
            System.out.println(n + "th to last node is " + head.data);
        }
        return k;
    }
    /* question 4-2 end */


    /* question 2-3 */
    /* write an algorithm to delete a node to middle of a singly linked list given only access to that node */
    public static boolean deleteNode( Node n) {

        if (n == null || n.next == null) {
            return false; // Failure
        } 

        Node next = n.next; 
        n.data = next.data; 
        n.next = next.next; 
        return true;
    }


    /* question 2-4 */
    /* add values in two linked list */
    public int addListsHelper( Node first, Node second  ){

        int addvalue = 0 ;

        if( first != null ){
            addvalue += first.data;
        }

        if ( second!= null ){
            addvalue += second.data; 
        }

        return addvalue;
    }


    private  void addLists( LinkedList l1, LinkedList l2) {

        if (l1 == null && l2 == null) {
             return;
        }

        int carry = 0 ;

        Node curr1 = l1.head;
        Node curr2  =  l2.head; 

        // Node res1 = result.head;

        int [] f_result = null; 


        while ( curr1 != null ||curr2 != null) {

            int ll = addListsHelper( curr1 , curr2 );


            System.out.println("carry = "+ carry );
            int tt = (ll+carry) % 10;
            // carry =0;

            if ( ll >= 10)
                carry =1; 

            curr1 = curr1.next;
            curr2 = curr2.next;

            System.out.println(" "+ tt );
        }

    }
    /* end of addLists */


    public static Node findBeginning( Node head) {

        Node slow = head;
        Node fast = head; 

        // Find meeting point
        while (fast != null && fast.next != null) { 
            slow = slow.next; 
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }

        // Error check - there is no meeting point, and therefore no loop
        if (fast == null || fast.next == null) {
            return null;
        }

        /* Move slow to Head. Keep fast at Meeting Point. Each are k steps
        /* from the Loop Start. If they move at the same pace, they must
         * meet at Loop Start. */
        slow = head; 
        while (slow != fast) { 
            slow = slow.next; 
            fast = fast.next; 
        }

        // Both now point to the start of the loop.
        return fast;
    }


    public void createLoop( int disToTail){

        if (this.getLength() <  disToTail )
            return;

        else {
            Node curr = nthToLast( head, disToTail );
            tail.next = curr;
        }
    }

    public static void main(String[] args) {

        LinkedList myLL = new LinkedList();

        int length = 10;
        // insert values ( int ) to the tail of the linked list 
        for ( int j=0; j < length; j++ ){

            myLL.insertToTail( j*2 );
        }

        myLL.display(); 
        System.out.println();

        /* display the linked list with it's previous, current and the next values */
        myLL.displayInDetails();    
        System.out.println();


        // int list_length = 100;
        // int k = 10;


        // LinkedListNode[] nodes = new LinkedListNode[list_length];
        // for (int i = 0; i < list_length; i++) {
        //  nodes[i] = new LinkedListNode(i, null, i > 0 ? nodes[i - 1] : null);
        // }


        /*int nToLast = 4;
        System.out.println( myLL.nthToLastR3( myLL.head, nToLast ).data );
        int test =  myLL.nthToLastR1( myLL.head, nToLast );*/


        /* question 2-1 */
        /* remove the duplicates from an unsorted linked list */
        /*myLL.deleteDupsC( myLL.head);
        myLL.display(); 
        System.out.println();*/

        /* find the node with it's int value */
        /*
        int getNode = 12;
        System.out.println( myLL.getNode(getNode).data );
        */

        /* question 2-3 */
        /* write an algorithm to delete a node to middle of a singly linked list given only access to that node */
        /*int deleteNode = 12;
        myLL.deleteNode( myLL.getNode(deleteNode) );
        myLL.display();
        System.out.println();*/


        /* question 2-4 */
        /*      
        System.out.println("the length of the linked list = "+ myLL2.getLength( ) );
        myLL.addLists(myLL1, myLL2 );   
        */


        /* question 2-5 */
        /* find the head of the circular linked list */
        /*myLL.createLoop( 15 );
        myLL.display(); 
        System.out.println();

        if ( myLL.findBeginning( myLL.head ) == null ){
            System.out.println("No cycle");
        }
        else
            System.out.println( "head of the loop is = "+ myLL.findBeginning( myLL.head ).data );*/
    }

}

Answer 1

我发现 displayInDetails() 中的代码存在短路或 ||:

if ( current.previous != null || current != null )

看，如果 current != null 仍然 current.previous 可以是 NULL。因此

current.previous.data

会给你NullPointerException。

因此，不要使用或，而是尝试和 &&，如下所示:

if (current != null && current.previous != null)