linked list help

**tjoney** · February 17th, 2011, 05:36 PM

I am new to Java programming and my instructor has assigned us the task of writing our own linked list class and told us to construct an insertAt method. I am have problems getting it to work. Any help would be appreciated.

public class NodeLinkedList
{
	private IntegerNode head;
 
	private IntegerNode tail;
 
	private int numberOfItems;
 
	public NodeLinkedList()
	{
		head = null;
 
		tail = null;
 
		numberOfItems = 0;
	}
 
	public int getNumberOfItems()
	{
		return numberOfItems;
	}
 
	public void insert( int value )
	{
		IntegerNode n = new IntegerNode ( value );
		n.setNext( head );
		head = n;
		numberOfItems ++;
	}
 
	public void insertAt(int index, int value)
	{
		IntegerNode n1 = new IntegerNode ( value );
 
		if ( n1 == null )
		{
			N.next = head;
			head = N;
		}
		else
		{
			N.next = n1.next;
 
		}
	}
}

**javapenguin** · February 17th, 2011, 06:24 PM

IntegerNode class is not a standard java class. Therefore we don't have the code to it.

In future please use:

[highlight=java] [/highlight] around your code.
I can say that LinkedList looks like this

LinkedList<T>

where T is some class.

I'd recommend creating a private inner class called Node<T>

A primitive cannot be null anyway. Actually, all LinkedList classes I've seen store Objects (String, Integer, etc).

Now if your LinkedList is only supposed to store Integers, vs. just having it tested using Integers, then I'm not sure why you'd even need a generic parameter at all.

Inside your Node class, which should have a reference to a Node called next(the node after it), a reference to a Node called previous(the Node before it), and a generic parameter T object called data)

You should have

public T getData()
{
 
}
 
public void setData(T data)
{
 
}
 
public Node<T> getNext()
{
 
}
 
public void setNext(Node<T> next)
{
 
}
 
public Node<T> getPrevious()
{
 
}
 
public void setPrevious(Node<T> previous)
{
 
}

For insertAt(T data, int index)

Make a Node<T> variable called curr;

make a for loop to hop from head to index by having curr = curr.getNext();

(Go from 0 to 1 less than index I think...so that curr will point to Node where data is to be put.

Just after for loop,
say curr.setData(T);

Note, there are so other things you'll have to do.

For instance, if index is less than 0 or greater than numberOfItems, don't add it.

If index is 0 and this is your first item, set had and tail to curr and set data as usual.

If you add after tail and valid, then setTail to curr.

If you add at 0, set head to curr.

Also, make sure to increase numberOfItems every time you add an item(don't do this though if it's index. Instead have an if statement that will exit method.

if (index < 0 || index > numberOfItems)
{
return;
}

Also, if you add any data when you have more than one item,

then you set the item that was at that index to be the next item

Node<T> temp = curr;
 
 
curr.setNext(temp);
 
curr.setData(T);
 
temp.setPrevious(curr);

**copeg** · February 17th, 2011, 08:21 PM

Cross posted at Linked List Help. While cross posting is not against the rules of this forum, we ask that members be forthright in letting others know where else the same question was posted. For reasons why, see The problems with crossposting

**tjoney** · February 17th, 2011, 08:27 PM

Originally Posted by copeg

Cross posted at Linked List Help. While cross posting is not against the rules of this forum, we ask that members be forthright in letting others know where else the same question was posted. For reasons why, see The problems with crossposting

I apologize for that.

**tjoney** · February 28th, 2011, 06:54 PM

 
public class IntegerLinkedList
{
  private IntegerNode head;
  private int numberOfItems;
  private IntegerNode curr;
  private IntegerNode prev;
 
 
  public IntegerLinkedList( ) // default contructor, contructs an empty list
  {
    head = null;
    numberOfItems = 0;
 
  }
 
  public int getNumberOfItems( )// acessor for numberOfItems, returns numberOfItems
  {
    return numberOfItems;
  }
 
 
  public void insert( int value )// insert method, inserts node at head
  {
    IntegerNode nd = new IntegerNode( value );
    nd.setNext( head );
    head = nd;
    numberOfItems++;
  }
 
  public void insertAt( int index, int value )// insertAt method, inserts node at specified index
  {
	 if ( index >= 0 && index < numberOfItems )
	 {
		 IntegerNode nd1 = new IntegerNode(value);
		 curr = curr.getNext();
 
		for(int i = 0; i <= (index - 1 ); i++)
		{
 
			curr .setData(value);
		}
 
		nd1 = curr;
	 }
 
		else
		{
			insert(value);
		}
 
		numberOfItems++;
 
  }
 
 
 
  public boolean delete( int value )// delete method, deletes value and returns true if value was deleted, else false
  {
    IntegerNode current = head;
    IntegerNode previous = null;
    while ( current != null
            && current.getData( ) != value )
    {
      previous = current;
      current = current.getNext( );
    }
 
    if ( current == null ) // not found
      return false;
    else
    {
      if ( current == head )
        head = head.getNext( );  // delete head
      else
        previous.setNext( current.getNext( ) );
 
      numberOfItems--;
      return  true;
    }
  }
 
 
  public String toString( )// toString method, returns values in list
  {
    String listString = "";
    IntegerNode current = head;
    for ( int i = 0; i < numberOfItems; i++ )
    {
      listString += current.getData( ) + "  ";
      current = current.getNext( );
    }
    return listString;
  }
}

Thank you for your previous help. I am now able to actually compile my application, however when I test the new code I get a null pointer exception when the insertAt method executes.

**tjoney** · March 3rd, 2011, 06:27 PM

need to bump this.

**Junky** · March 3rd, 2011, 06:54 PM

Here is the general algorithm:

Create a temp node and set it to head
Loop to set temp to the next node index - 1 times
Set new node next to temp next
Set temp next to new node

If you look carefully your code is doing nothing like that. Also if you enter the else statement and call insert(value) method you increment numberOfItems twice.

Thread: linked list help

LinkBack

Thread Tools

Display

linked list help

Related threads:

Re: linked list help

Re: linked list help

Re: linked list help

Re: linked list help

Re: linked list help

Re: linked list help

Similar Threads

Finding min in linked list

[SOLVED] Linked List Help

Help with linked list

Simple linked list

Recursive function based on Linked list