Thread: LinkedList -- insert()

For this program I am dealing with the linkedlist interface. I am designing a method "insert" that will add a new member to a specified location provided by the user (public insert(T newMem, int index) ). Now, I'm not sure how to find the desired index within the list and test whether that index is available to insert the new member. If the list is empty, the new member will be added to the list (should it be added to the head? that just seems confusing to me, because if that member is at index 0 instead of index 7 ... would it be possible to insert the newMember into the desired index of the list? ). Within the final else clause I want to try whether the index is available and if it is empty(), insert the newMember...if it is !empty(), move the member in that index to the tail. Any tips? Is this a good approach?

public void insert(T newMember, int index) {
 
        if(empty()){
 
        }
        else if(index < 0) { 
            System.out.println("Index Out Of Bound");
        }      
        else{
            try{
                member.setData(newMember);
            }catch(Exception e){
 
            }
        }
    }

Posted here to make sure it notified you.

cannot find symbol
symbol: method next()
location: variable newNode of type ListNode<T>
where T is a type-variable:
T extends Object declared in class MySinglyLinkedListD

That is all the error message contained.

next() is defined within the same class where I am trying to use it---that's what I don't understand. I'm having the same issue when I try to use my insert method. And the tail is of the same type as both methods...

public class MySinglyLinkedListD<T> implements SinglyLinkedList<T> {
 
    protected ListNode<T> head, tail, current;
    String name;
    int size = 0;
 
    //Simple constructor
    public MySinglyLinkedListD() {        
    }
    //Constructor for a list with title
    public MySinglyLinkedListD (String name) {
        this.name = name;
}
    private int size() {
            return size;
    }
    //Method to move cursor to beginning of list
    public void reset () {
        current = head;
    }
   //Prints contents for entire list
    public void traverse () {
        if (!empty ())
           {
               reset ();
               System.out.println (current);
               while (hasNext ())
               {
                    current = current.getNode ( );
                    System.out.println (current);
                }
           }
    }
 
    public void addFirst(T t) {
        ListNode<T> newNode = new ListNode<T> (t);
 
        newNode.setNode (head);
        head = newNode;
 
        if(!empty())
            tail = head;
    }
 
    public void addLast(T newMember) {
         if (empty ()){
            addFirst (newMember);
            head = tail;
    }
        else
        {
            tail = new ListNode<T>();
            tail.next() = tail;
 
        }
         size++;
    }
 
    public void insert(T newMember, int index) throws IndexOutOfBoundsException{
        ListNode<T> newNode = head;
 
        if(index == size()){
            addLast(newMember);
            System.out.println("Tail entry at index " + size++);
        }
        else if(index < 0) throw new IndexOutOfBoundsException();
 
        else{
            for(int i = 1; i < index; i++) {
                current = current.nextNode;
                newNode = new ListNode<T>();
                newNode = current;
                newNode.next() = newMember;
                size++;
            }
        }
    }
    ///Method to search from any node in list
    public ListNode search(T key) {
 
        ListNode  found = null;
        if (!empty())
        {
            reset();
            do
            {
                if (current.getElement ().equals (key))
                {
                    found = current;
                    break;
                }
                else
                {
                    if (hasNext ( ))
                        current = current.getNode ( );
                    else
                        break;
                }
 
            } while (true);
        }
        return found;
    }
    ///Method to search for specific string/char in list
    public ListNode searchSpecific(T member) {
        ListNode found = null;
        if(!empty()){
            reset();
            do{
 
            }while(true);
        }
 
        return found;
    }
 
    public boolean delete(T key) {
        //Create object to search node
        ListNode  found = search (key);
        //Test whether node exists
        if (found == null)
        {
            System.out.println ("\nkey = " + key + " not found");
            return false;
        }
        else
        {
             if (found == head)
             {
                 head = found.getNode ();
                 reset ();
             }
            else
             {
                 current = found;
                 try
                 {
                    getPrevious ( );
                 }
                 catch (PointerOutOfBoundException ex)
                 {
                     ;
                 }
                 current.setNode (found.getNode ());
             }
 
             System.out.println (key + " deleted");
             return true;
        }
    }
 
    public boolean empty(){
        return(head == null);
    }
 
    public boolean hasNext() {
        if(current == null) {           
            return false;
        }
        return(current.getNode() != null);
    }
 
    public ListNode<T> next() throws PointerOutOfBoundException {
        if(hasNext()){
            current = current.getNode();
            return current;
        }
        else throw new PointerOutOfBoundException ();
    }
}

I'm not trying to compile it yet...I'm not ready for that. I have my other classes...I just provided the class with the issue. I thought the issue was contained within this class alone.

Is it possible create a single Node class (Node<T>) that can account for a list for integers and a list for strings? Or is it better to create a separate class to do this?

That is very well possible, every good LinkedList implementation does it that way.
Why do you think it would not be possible? At what point does it matter to the Node-class what type its content is?

Thank you guys. I thought so, but I just wanted to make sure -- I saw an example where they created separate classes for the two but they weren't using generics.

public class NodeList<T> {
	public T element;
	public String elementString;
	public int elementInt;
	public NodeList next;
 
	public NodeList(String s, NodeList next) {
		this.next = next;
		this.elementString = s;
	}
 
	public NodeList(int n, NodeList next){
		this.next = next;
		this.elementInt = n;
	}
 
	public NodeList() {
	}
 
	public void setNext(NodeList next) {
		this.next = next;
	}
 
	public NodeList getNext() {
		return next;
	}
 
	public void setElement(T element) {
		this.element = element;
	}
 
}

Would you mind explaining to me exactly what is going on here. What is newNode.next = tail accomplishing? In my class NodeList, next is defined as NodeList<T>...which is the format I've adopted from another source. Not sure exactly what it mean. Thanks.

public void addFirst(T newMember) {
		if(empty()) {
			NodeList<T> newNode = new NodeList<T>();
			newNode.element = newMember;
			newNode.next = tail;
		} else {
			tail = new NodeList<T>();
			tail = tail.next;
			tail.element = newMember;
		}
	}

It's unclear what new NodeList<T() creates. It appears it creates a new Node that will be added as an element to an existing list, but the name, 'NodeList', suggests that a new List is being created. This demonstrates just one of many reasons why programmers should document their code AND give their variables and methods helpful names.

Looking back at the code you posted in Post #9, it appears you've attempted to make that code your own by making subtle changes and adding new features, posting that result in Post #17, but your changes aren't correct. Explaining to you what is going on in Post #17 is a futile exercise, because it's confusing at best and probably wrong.

I recommend you comment the original addFirst() method and study that until you completely understand it. If you have questions, post the commented version here, and we'll help you understand it. Once you've done that, comment in the changes you'd like to make to that method and attempt to code them, again coming back with commented code when you need help.

Ok, lets start with the addToFront method:
1. I understand the if statement...its saying if a node is empty, add the new node with its member, assign it as head, and link it with old head.
2. If the list is not empty - as I understand it - I create a temp node that will be linked with the head node (head = temp.next. After doing this, assign head pointer to tempNode (tempNode = head).
Hopefully this will be enough information that it won't be as confusing.
Variables defined within class

public class MySinglyLinkedList<T> implements SinglyLinkedList<T> {
	private Node<T> head, tail, newNode, temp;
	int size = 0;
}

private class Node<T> {
 
		public T element;  //contents within node
		Node<T> next, previous;    //node pointer
 
public Node(T element) {
			this.element = element;
		}
}

public void addToFront(T newMember) {
		newNode = new Node<T>(newMember);	//Node object
		//Determine whether list exists, or head is empty.
		if (empty()) {
			newNode = head;		   //move node pointer to empty node(tail)
			tail = head;
                         size++;				//increase list size by 1
		}  //if node !empty(), create a node to   
		else {
			Node temp = new Node<T>();	//a temp node to link with current head node
			head = temp.next;		
			newNode = head;
		}
	}

temp.next will have the address of the current head node...but it will contain the newest member in the list. Head should always remain the first link in the list -- that is why I used newNode = head; The new node's value will point to the previous first node(now second).

Yes, I see what you mean now about newNode being local to method. Why are we unable to modify the visibility of the methods from LinkedList interface? just curious as to why.

private boolean empty() returns head == null

public void addToFront(T newMember) {
		Node<T> firstNode = new Node<T>(newMember);	//Node object
		//Determine whether list exists, or head is empty.
		if (empty()) {
			firstNode.next = head;   //new node linked with head
			firstNode = head;		   //move node pointer to empty node(head)
			size++;				//increase list size by 1
		}  //if node !empty(), create a node to   
		else {
			Node<T> temp = new Node<T>();	
			head = temp.next;		//
			head = firstNode;
		}
	}

I've checked my code against several different source and I don't see any serious difference. there is nothing unique about my code and yet it still returns a nullpointer error. Can you guys please explain to me what is wrong?

MySinglyLinkedList<String> myStringList = new MySinglyLinkedList<String>();
		myStringList.addToFront("Orion");
		System.out.println(myStringList.getNext());

public void addToFront(T newMember) {
		Node<T> firstNode = new Node<T>(newMember);
 
		if (empty()) {
			firstNode.setLink(head);
			firstNode = head;
			current = head;
			System.out.println(newMember);
		} 
		else {
			Node<T> newNode = new Node<T>();
			newNode.link = head;
			head = newNode;
		}
	}

public Node<T> getNext() throws PointerOutOfBoundsException {
 
		if (hasNext()) {
			current = current.getLink();
			return current;
		} else
			throw new PointerOutOfBoundsException();
	}
 
	public boolean hasNext() {
		if (current == null) {
			return false;
		}
		return (current.getLink() != null);
	}