सिर और पूंछ संदर्भ

Question

का उपयोग करके तत्व को हटाकर एकल रूप से लिंक की गई सूची मुझे अपने प्रोजेक्ट के लिए एक सिंगल लिंक्ड सूची लागू करना है और मुझे काम करने के लिए निकालने की विधि प्राप्त करने में परेशानी हो रही है। मैंने यहां उत्तर के लिए खोज की है लेकिन मुझे पूंछ संदर्भ शामिल करने वाला कोई भी नहीं मिला है। मेरी परियोजना में सूची में एक सिर और पूंछ संदर्भ होना चाहिए और जहां भी आवश्यक हो, अद्यतन किया जाना चाहिए।

public class BasicLinkedList<T> implements Iterable<T> { 
public int size; 

protected class Node { 
    protected T data; 
    protected Node next; 

    protected Node(T data) { 
     this.data = data; 
     next = null; 
    } 
} 

protected Node head; 
protected Node tail; 

public BasicLinkedList() { 
    head = tail = null; 
} 

public BasicLinkedList<T> addToEnd(T data) { 
    Node n = new Node(data); 
    Node curr = head; 
    //Check to see if the list is empty 
    if (head == null) { 
     head = n; 
     tail = head; 
    } else { 
     while (curr.next != null) { 
      curr = curr.next; 
     } 
     curr.next = n; 
     tail = n; 

    } 
    size++; 
    return this; 
} 

public BasicLinkedList<T> addToFront(T data) { 
    Node n = new Node(data); 
    if(head == null){ 
     head = n; 
     tail = n; 
    } 
    n.next = head; 
    head = n; 
    size++; 
    return this; 
} 

public T getFirst() { 
    if (head == null) { 
     return null; 
    } 
    return head.data; 
} 

public T getLast() { 
    if(tail == null){ 
     return null; 
    } 
    return tail.data; 
} 

public int getSize() { 
    return size; 
} 

public T retrieveFirstElement() { 
    // Check to see if the list is empty 
    if (head == null) { 
     return null; 
    } 
    Node firstElement = head; 
    Node curr = head.next; 
    head = curr; 
    size--; 
    return firstElement.data; 

} 

public T retrieveLastElement() { 
    Node curr = head; 
    Node prev = head; 
    // Check to see if the list is empty 
    if (head == null) { 
     return null; 
    } else { 
     // If there's only one element in the list 
     if (head.next == null) { 
      curr = head; 
      head = null; 
     } else { 
      while (curr.next != null) { 
       prev = curr; 
       curr = curr.next; 
      } 

      tail = prev; 
      tail.next = null; 
     } 
    } 
    size--; 
    return curr.data; 
} 

public void remove(T targetData, Comparator<T> comparator) { 
    Node prev = null, curr = head; 
    while (curr != null) { 
     if (comparator.compare(curr.data, targetData) == 0) { 
      //Check to see if we need to remove the very first element 
      if (curr == head) { 
       head = head.next; 
       curr = head; 
      } 
      //Check to see if we need to remove the last element, in which case update the tail 
      else if(curr == tail){ 
       curr = null; 
       tail = prev; 
       prev.next = null; 
      } 
      //If anywhere else in the list 
      else { 
       prev.next = curr.next; 
       curr = curr.next; 
      } 
      size--; 
     } else { 
      prev = curr; 
      curr = curr.next; 
     } 
    } 
} 

public Iterator<T> iterator() { 
    return new Iterator<T>() { 

     Node current = head; 

     @Override 
     public boolean hasNext() { 
      return current != null; 
     } 

     @Override 
     public T next() { 
      if(hasNext()){ 
       T data = current.data; 
       current = current.next; 
       return data; 
      } 
      return null; 
     } 

     @Override 
     public void remove(){ 
      throw new UnsupportedOperationException("Remove not implemented."); 
     } 

    }; 
} 

}

मैं इस विधि के कई पुनरावृत्तियों माध्यम से चला गया है और हर बार मैं या तो सिर संदर्भ, पूंछ संदर्भ खो देते हैं या मैं न निकालें: यह मेरी कक्षा और निकालें विधि है तत्व और मैं इसे समझने की कोशिश कर रहा हूँ। संदर्भ के लिए यहां परीक्षण है जिसे मैं चला रहा हूं। मैं परीक्षण में भी असफल नहीं हूं, यह केवल विफलता ट्रेस कहता है।

public void testRemove(){ 
      BasicLinkedList<String> basicList = new BasicLinkedList<String>(); 
    basicList.addToEnd("Blue"); 
    basicList.addToEnd("Red"); 
    basicList.addToEnd("Magenta"); 
    //Blue -> Red -> Magenta -> null 
    basicList.remove("Red", String.CASE_INSENSITIVE_ORDER); 
    //Blue -> Magenta -> null 
    assertTrue(basicList.getFirst().equals("Blue")); 
    //getLast() returns the tail node 
    assertTrue(basicList.getLast().equals("Magenta")); 
    } 

संपादित करें: यह उल्लेख करना भूल गया कि निकालने विधि सूची से लक्षित डेटा के सभी उदाहरणों को हटा देना चाहिए।

Answer 1

मुझे केवल 1 बग दिखाई देता है। अपनी सूची शुरू में निम्न विधि खाली है एक पाश जहां एक नोड जिसका अगले है कारण होगा, तो ही को दर्शाता है:

public BasicLinkedList<T> addToFront(T data) { 
    Node n = new Node(data); 
    // The list was empty so this if is true 
    if(head == null){ 
     head = n; 
     tail = n; 
    } 
    n.next = head; 
    // now head == n and n.next == head == n so you've got a circle 
    head = n; 
    size++; 
    return this; 
} 

तुम बहुत तरह इसे ठीक कर सकते हैं:

public BasicLinkedList<T> addToFront(T data) { 
    Node n = new Node(data); 
    if(head == null){ 
     tail = n; 
    } 
    n.next = head; 
    head = n; 
    size++; 
    return this; 
}