Inserting Node into middle of Linked List, and accidentally inserting null node as well

JayneCobb's_HatDesigner picture JayneCobb's_HatDesigner · Nov 7, 2012 · Viewed 11.4k times · Source

I'm working on a program that does not use Java's built in Linked List class; I'm building it from scratch. I've been successful with everything except writing a method that inserts a Node into a particular position of the linked list.

I have a method that sets a particular Node as the "current" Node. So, for example, I have a linked list that looks like this: cats --> dogs --> make --> good --> pets, and "current" is equal to 2; that means that the "current" Node is "dogs".

From here, let's say I want to insert a new Node at the position of "current" whose info field reads and. If done correctly, the final linked list will be: cats --> and --> dogs --> make --> good --> pets; "and" will replace "dogs" at position 2.

So here's my problem: my method works to insert a new Node at position two, but something's going wrong with linking the newly created node to pre-existing nodes. Not only am I inserting my new node into the list, but I'm also inserting a node with no information before "dogs". As my code currently runs, the output looks like this: cats --> and --> (blank) --> dogs --> make --> good --> pets.

I'm 99.9% sure the problem lies in the (if current != null) portion of the code, I just can't figure out how to fix it.

Any thoughts on why I'm inserting a blank node in addition to the node I actually want to add?

public void insert () {

    System.out.println("Please enter the text you wish to insert, or type \"end\" if you are done inserting.");
    String theString;
    theString = console.nextLine();

    while (!theString.equals("end")){
        newNode = new Node ();
        newNode.info = theString;
        newNode.next = null;

        if (first == null){
            first = newNode;
            last = newNode;
        } else if (current != null){
            Node p = new Node (current.info, current.next);
            current.info = newNode.info;
            current.next = p;
        }
        else {
            last.next = newNode;
            last = newNode;
        }

        System.out.println("Please enter the text you wish to insert, or type \"end\" if you are done inserting.");
        theString = console.nextLine();
    }   
}

EDIT

The entire program is quite long, but here is the "setLine" method which sets current equal to whatever position the user wishes to insert their Node at. It takes a parameter "int line" which is obtained via a user prompt.

public Node setLine(int line) {

    int index = 0;
    current = first;
    while (index < line) {
        previous = current;
        current = current.next;
        index++;
    }
    return current;
}

Answer

Zzz picture Zzz · Nov 7, 2012

Here is a code that inserts the node properly. This should be a good starting point, good luck(you can read more here: http://www.algolist.net/Data_structures/Singly-linked_list/Insertion).

public class SinglyLinkedList {

      public void addLast(SinglyLinkedListNode newNode) {    
            if (newNode == null)    
                  return;    
            else {    
                  newNode.next = null;    
                  if (head == null) {    
                        head = newNode;    
                        tail = newNode;    
                  } else {    
                        tail.next = newNode;    
                        tail = newNode;    
                  }    
            }    
      }

      public void addFirst(SinglyLinkedListNode newNode) {    
            if (newNode == null)    
                  return;    
            else {    
                  if (head == null) {    
                        newNode.next = null;    
                        head = newNode;    
                        tail = newNode;    
                  } else {    
                        newNode.next = head;    
                        head = newNode;    
                  }    
            }    
      }

      public void insertAfter(SinglyLinkedListNode previous,    
                  SinglyLinkedListNode newNode) {    
            if (newNode == null)    
                  return;    
            else {    
                  if (previous == null)    
                        addFirst(newNode);    
                  else if (previous == tail)   
                        addLast(newNode);    
                  else {    
                        SinglyLinkedListNode next = previous.next;    
                        previous.next = newNode;    
                        newNode.next = next;    
                  }    
            }    
      }    
}