java - 如何在链表的最后插入元素

Question

我必须在链接列表中实现 insertAtLast()。

我在为 insertAtLast() 编写的代码中遇到空指针异常。可能是因为我访问错误。

如何正确访问它并进行插入？

class myLinkedList {
private static class Node 
{
    private int data; 
    private Node next;

    public Node(int data, Node next) 
    {
        this.data = data;
        this.next = next; 
    }
}

private Node head;

// Constructs an empty list
public myLinkedList() 
{
    head = null; 
}

// Returns true if the list is empty otherwise returns false
public boolean isEmpty() 
{
    return (head == null); 
}

// Inserts a new node at the beginning of this list.    
public void insertAtBeginning(int element) 
{
    head = new Node(element, head); 
}

// Returns the first element in the list.
public int getFirstElement() 
{
    if(head == null) 
    {
        System.out.println("Empty linked list"); 
        throw new IndexOutOfBoundsException();
    }
    return head.data; 
}

// Removes the first node in the list.
public int removeFirstNode() 
{ 
    int tmp = getFirstElement(); 
    head = head.next;
    return tmp;
}

// Empties linked list 
public void clear() 
{
    head = null; 
}

// Returns the length of the linked list
public static int LLlength(Node head)
{ 
    int length = 0;
    Node currentNode = head; 

    while(currentNode != null)
    {
        length++;
        currentNode = currentNode.next; 
    }
    return length; 
}

// Displays the linked list elements
public static void display(Node head)
{ 
    if(head == null) 
    {
        System.out.println("Empty linked list");
        throw new IndexOutOfBoundsException(); 
    }

    Node currentNode = head; 

    while(currentNode != null)
    {
        System.out.print(currentNode.data+" ");
        currentNode = currentNode.next; 
    }
    System.out.println();
}

// Displays the linked list elements in reverse order 
public static void displayReverse(Node head)
{
    if(head == null){} 
    else
    {
        Node currentNode = head; 
        displayReverse(currentNode.next); 
        System.out.print(currentNode.data+" ");
    } 
}
//Displays the linked list's last element
public static int getLastElement(Node head)
{
    Node currentNode = head; 

    while(currentNode.next != null)
    {
        currentNode = currentNode.next; 
    }
    return currentNode.data;
}
public static void insertAtLast(Node head,int element)
{
    Node newNode=null;
    newNode.data = element;
    newNode.next = null;
    while(head.next != null)
    {
        head = head.next; 
    }
    head = newNode;
    //return head;

}

//Tells if a sepeific element is in the Linked List or not
public static boolean searchFor(Node head, int element)
{
    Node currentNode = head; 
    boolean flag = false;
    while(currentNode != null)
    {
        if (currentNode.data == element)
        {
            flag = true;
            break;
        } 
        currentNode = currentNode.next;
    }
    return flag;
}

} 

Answer 1

there exists three troubles in your insertAtLast method.

<小时/>

1. Node newNode=null; the newNode object is a null reference it don't reference a object of Node, you may change it into Node newNode = new Node(value,null)
2. after your while loop the head will make a reference with the last Node object, your works will only make head make a reference with a new Node object, it make no effect to the list self, for this new object have nothing with list.
3. after this method, the head will reference a new object of Node rather than the first of the List.

<小时/>

替代解决方案:

public static void insertAtLast(Node head,int element)
{
   Node newNode=new Node(0,null);
   newNode.data = element;
   newNode.next = null;
   Node temp = head;
   while(temp.next != null)
   {
       temp = temp.next; 
   }
   temp.next = newNode;
  //return head;
}