Member Avatar for Member #884252

I need help with an add boolean method in a singly linked list, The only difference is that i start off with a dummy head. The method's job is to add non-repeating objects to the linked list. Please help:

public boolean add(Object newData){
      Node current = head.getNext();
      Node v = new Node(newData, null);
      tail = v;
      if(current == null){//list is empty
          head.setNext(v);
          return true;
      }
      else{
          while(current!= null){
              if(newData != current.getElement()){
                  current = current.getNext();
                  current.setNext(v);
              }
              else return false;
          }
      }
      return true;
  • 2 Contributors
  • 3 Replies
  • 216 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by Member #884252

Dani AI

Generated

A few concrete fixes that address the bugs hit and the points raised:

  • Don’t pre-create the new Node; only make it after you know you’ll append.
  • Compare objects with equals (null-safe) instead of !=.
  • While walking the list, set the new node on the previous node when you reach the end — not on the node after you advance, which causes the infinite loop/NullPointerException.
  • Update tail only when you actually append.

Example (keeps the dummy head):

public boolean add(Object newData) {
    Node prev = head;                // dummy head
    Node cur  = head.getNext();

    while (cur != null) {
        if (java.util.Objects.equals(cur.getElement(), newData)) {
            return false;           // duplicate found
        }
        prev = cur;
        cur  = cur.getNext();
    }

    Node newNode = new Node(newData, null);
    prev.setNext(newNode);          // attach after last node (or after head if empty)
    tail = newNode;                 // update tail only when appended
    return true;
}

Notes and quick checks:

  • If you can’t use Objects.equals (very old Java), do a null-safe compare: cur.getElement() == null ? newData == null : cur.getElement().equals(newData).
  • Keeping a tail helps O(1) append, but since you must scan to detect duplicates this add is still O(n). If you need faster membership checks, maintain a parallel HashSet of elements (remember to keep both structures in sync).
  • Test edge cases: empty list, single-element list, duplicate at head, duplicate at tail, and null elements.

Recommended Answers

All 3 Replies

Member Avatar for stultuske

I do have some questions here.
first of all, why do you initialize v before you know if you'll need it or not? in case you don't need it, you're just occupying memory and resources for something you don't need.
but, here:

while(current!= null){
if(newData != current.getElement()){
current = current.getNext();
current.setNext(v);
}
else return false;
}

you only reach this code when current != null so, unless you actually get into the situation where current == newData (which, btw is NOT the right way to compare objects for equality, you should use the equals method), you're entering an endless loop.

but the next line really makes me wonder:
current = current.getNext();
do you have a node containing node's, or is there an error here?

Member Avatar for Member #884252

So the v is initialized because i'm trying to store the new object into a new Node. So that way when i reach the end of the list i can replace null in the last node to setNext(v). I do enter an infinite loop.

Also the current = current.getNext(); assigns the current node to the next one.

Member Avatar for Member #884252

here is my node class:

public class Node {
  private Object element; // we assume elements are character strings
  private Node next;
  /** Creates a node with the given element and next node. */
  public Node(Object s, Node n) {
    element = s;
    next = n;
  }
  public void addNodeAfter(Object newElem){
      next = new Node(newElem, next);
  }
  /** Returns the element of this node. */
  public Object getElement() { return element; }
  /** Returns the next node of this node. */
  public Node getNext() { return next; }
  // Modifier methods:
  /** Sets the element of this node. */
  public void setElement(Object newElem) { element = newElem; }
  /** Sets the next node of this node. */
  public void setNext(Node newNext) { next = newNext; }
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.