Danh sách liên kết Java - thêm phương thức

Question

Lớp cấu trúc dữ liệu, triển khai danh sách liên kết đơn lẻ với đầu, đuôi và các nút hiện tại. Có vấn đề với một phương pháp, có thể sử dụng một di chuyển đúng hướng.

Từ sự phân công, hãy viết phương pháp:

add (item): thêm mục (String) sau khi nút hiện trong danh sách và đặt con trỏ hiện tại để tham khảo các nút mới.

nỗ lực của tôi:

add My phương pháp duy nhất dường như làm việc khi tôi thêm mục vào giữa danh sách, không phải trên hai đầu. Nếu tôi sử dụng nó để thêm một vài mục và sau đó in danh sách, chỉ có một mục đầu tiên tôi thêm vào sẽ có trong danh sách, trong khi các phương thức nối thêm và nối thêm của tôi đã thử nghiệm tốt.

Có sự cố rõ ràng nào với mã của tôi không? Tôi cảm thấy như tôi đang thiếu một cái gì đó hiển nhiên.

All:

public class LinkedList { 
    Node head = null; /* Head of the list */ 
    Node tail = null; /* Tail of the list */ 
    Node curr = null; /* Current node in the list */ 

    public void prepend(String item) { 
     if (head == null) { 
      head = tail = new Node(item, null); 
      curr = head; 
     } else { 
      head = new Node(item, head); 
      curr = head; 
     } 
    } 

    public void append(String item) { 
     if (head == null) { 
      head = tail = new Node(item, null); 
      curr = tail; 
     } else { 
      tail.next = new Node(item, null); 
      tail = tail.next; 
      curr = tail; 
     } 
    } 

    public void add(String item) { 
     if (curr != null) { 
      Node newNode = new Node(item, curr.next); 
      curr.next = newNode; 
      curr = newNode; 
     } else { 
      head = tail = new Node(item, null); 
      curr = head; 
     } 
    } 

    public void delete() { 
     if (curr.next == null) { 
      Node temp = head; 
      while (temp.next != curr) { 
       System.out.println(temp.item); 
       temp = temp.next; 
      } 
      temp.next = null; 
      curr = head; 
     } 
    } 

    public void find(String item) { 
     Node temp = new Node(curr.item, curr.next); 
     if (item.equals(temp.item)) 
      curr = temp; 
     else { 
      temp = temp.next; 
      while (temp.next != null && temp != curr) { 
       if (item.equals(temp.item)) 
        curr = temp; 
      } 
     } 
    } 

    public String get() { 
     if (curr != null) 
      return curr.item; 
     else 
      return ""; 
    } 

    public boolean next() { 
     if (curr != tail) { 
      curr = curr.next; 
      return true; 
     } else 
      return false; 
    } 

    public void start() { 
     curr = head; 
    } 

    public void end() { 
     curr = tail; 
    } 

    public boolean empty() { 
     if (head == null) 
      return true; 
     else 
      return false; 
    } 
} 

Node lớp:

class Node { 
    Node next; 
    String item; 

    Node(String item, Node next) { 
     this.next = next; 
     this.item = item; 
    } 
} 

Answer 1

Tôi nghĩ vấn đề là

if (curr != null) { 
    Node newNode = new Node(item, curr.next); //<-- here (curr.next) 

//and 

Node(String item, Node next) { 
    this.next = next; //<-- here 

Try (Sửa):

Node newNode = new Node(item, curr); // pass curr to the constructor of Node 
curr = newNode; 

Answer 2

Tôi không thấy bất kỳ vấn đề nào ở đây, vì vậy tôi đoán vấn đề là ở nơi khác.

Được rồi, vấn đề duy nhất mà tôi thấy có trong xóa:

public void delete() 
{ 
    Node temp = head; 

    while(temp != null && temp.next != curr) { 
     System.out.println(temp.item); 
     temp=temp.next; 

    } 

    if (temp != null && temp.next != null) { 
     temp.next = temp.next.next; 
    } 
    curr = head; 

} 

Answer 3

Tôi nghĩ rằng tôi đã tìm thấy vấn đề của bạn. Nếu bạn sử dụng append() bạn thêm nó trực tiếp sau đuôi. Nhưng khi bạn đã thêm các nút trước đó sau đuôi bạn không đặt đuôi của bạn vào nút mới. Điều này có nghĩa rằng một khi bạn gọi append() hai lần bạn mất tất cả các nút mà bạn đã thêm sau khi nối thêm đầu tiên().

dụ Giới thiệu tóm tắt:

public static void main(String[] args) { 
    LinkedList list = new LinkedList(); 
    list.add("First add"); 
    list.append("First Append"); 
    list.add("Second add"); 
    list.prepend("First prepend"); 
    list.add("Third add"); 
    list.prepend("Second prepend"); 
    list.add("fourth add"); 
    list.append("Second Append"); 
    list.add("Fifth add"); 
    list.add("Sixth add"); 

    list.start(); 
    do { 
     System.out.println(list.get().toString()); 

    } while (list.next()); 
} 

Output:

Second prepend 
fourth add 
First prepend 
Third add 
First add 
First Append 
Second Append 

Kết luận: "Thứ hai Add" bị mất, cũng như "Fifth thêm" và "Thứ sáu thêm" bởi vì phương pháp của bạn bên cạnh() dừng lại ngay sau khi nó đến đuôi. Bạn cần luôn cập nhật đuôi nếu bạn thêm nút mới vào cuối.

Hy vọng điều này sẽ hữu ích. Chúc mừng, Chnoch

Answer 4

Thực sự có vấn đề trong add: nó không cập nhật tail khi các nút đã tồn tại.Xem xét chuỗi hành động này:

LinkedList list = new LinkedList(); 
list.add("one"); 
list.add("two"); 
list.append("three"); 

Nếu bạn đã sau đó in nó sử dụng này:

public void print() { 
    Node curr = this.head; 
    while(curr != null) { 
     System.out.println(curr.item); 
     curr = curr.next; 
    } 
} 

Như thế này:

list.print(); 

Bạn sẽ nhận được kết quả như sau:

one 
three 

Điều này xảy ra vì ause tail - mà append dựa vào - tiếp tục trỏ đến Node đầu tiên sau khi thao tác add thứ hai được thực hiện.