代码之家 › 专栏 › 技术社区 › Alex G

Java中的链表

singly-linked-list linked-list java

Alex G · 技术社区 · 7 年前

代码编译和运行,但addToEnd方法不起作用,这似乎是正确的,但我不知道哪里的错误是,有人能指导我什么或哪里的代码需要修复

 public class LinkedList {
 private Node head;


 /**
  * constructor
  * pre: none
  * post: A linked list with a null item has been created.
  */
 public LinkedList() {
  head = null;
 }

 /** 
  * Activity: finds size of the Linked List.
  * Pre-Condition: none
   * Post-Condition: The size of the list is returned
  */
 public int size() {
   int counter  = 0;
   Node current = head;

   while(current != null) {
    counter++;
    current = current.getNext();
  }
   return counter;   
}

  /** 
  * Adds a node to the end of the linked list.
  * pre: String parameter
  * post: The linked list has a new node at the end.
  */
 public void addAtEnd(String s) {
  Node current = head;
  Node newNode = new Node(s);
   if(head == null) {
     head = newNode;
     head.setNext(null);
   } 
   else {
     while(current.getNext() == null) {
       current.setNext(newNode);
       current = newNode;
   } 
 }
 }

 private class Node {
 private String data;
 private Node next;


  /**
   * constructor
   * pre: none
   * post: A node has been created.
   */
  public Node(String newData) {
   data = newData;
   next = null;
  }


  /**
   * The node pointed to by next is returned
   * pre: none
   * post: A node has been returned.
   */
  public Node getNext() {
   return(next);
  }


  /**
   * The node pointed to by next is changed to newNode
   * pre: none
   * post: next points to newNode.
   */
  public void setNext(Node newNode) {
   next = newNode;
  }


  /**
   * The node pointed to by next is returned
   * pre: none
   * post: A node has been returned.
   */
  public String getData() {
  return(data);
  }
 }
}

以下是我的主类代码,Blume和Dahl从未添加到列表中:

 public class LinkedListDemo {

 public static void main(String[] args) {
 LinkedList list = new LinkedList();

  list.addAtFront("Sachar");
  list.addAtFront("Osborne");
  list.addAtFront("Suess");
  System.out.println("List has " + list.size() + " items.");
  System.out.println(list);

  list.addAtEnd("Blume");
  list.addAtEnd("Dahl");
  System.out.println(list);
}
    }

3 回复 | 直到 7 年前

kkica 6 年前

 public void addAtEnd(String s) {
  Node current = head;
  Node newNode = new Node(s);
   if(head == null) {
     head = newNode;
     head.setNext(null);
   } 
   else {// problem is here. You need to find the  node that has getNext()==null, 
         //so you need to loop all nodes where get next != null
     while(current.getNext() == null) { 
       current.setNext(newNode);
       current = newNode;
   } 
 }

else{ 
    //iterate to the last node
    while(current.getNext() != null) { 
    current = current.getNext(); 
    } 
    //Append the new node to the end
    current.setNext(newNode);  
}

Jacob G. 7 年前

while (current.getNext() == null) {
    current.setNext(newNode);
    current = newNode;
}

这是不正确的;因为您没有跟踪列表的尾部,所以需要遍历整个列表,然后添加 newNode 最后(我相信你已经理解了)。要做到这一点,只要继续设置 current 到 current.getNext() 直到是 null ,然后打电话 current.setNext(newNode);

Node next;

while ((next = current.getNext()) != null) {
    current = next;
}

current.setNext(newNode);

Mead 7 年前

public void addAtEnd(String s) {
    Node current = head;
    Node newNode = new Node(s);
    if(current == null) {
        head = newNode;
    } else {
        while(current.getNext() != null) {
            current = current.getNext();
        }
        current.setNext(newNode); 
    }
}