Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 7 of 7

Thread: linked list help

  1. #1
    Junior Member
    Join Date
    Feb 2011
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default linked list help

    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;
     
    		}
    	}
    }
    Last edited by helloworld922; February 17th, 2011 at 11:59 PM.


  2. #2
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: linked list help

    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);
    Last edited by javapenguin; February 17th, 2011 at 06:40 PM. Reason: Correcting spelling error.

  3. #3
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: linked list help

    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

  4. #4
    Junior Member
    Join Date
    Feb 2011
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: linked list help

    Quote Originally Posted by copeg View Post
    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.

  5. #5
    Junior Member
    Join Date
    Feb 2011
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: linked list help

     
    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.

  6. #6
    Junior Member
    Join Date
    Feb 2011
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: linked list help

    need to bump this.

  7. #7
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,545
    My Mood
    Grumpy
    Thanks
    0
    Thanked 167 Times in 158 Posts

    Default Re: linked list help

    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.

Similar Threads

  1. Finding min in linked list
    By lieles in forum What's Wrong With My Code?
    Replies: 1
    Last Post: February 7th, 2011, 02:06 AM
  2. [SOLVED] Linked List Help
    By lieles in forum What's Wrong With My Code?
    Replies: 1
    Last Post: February 4th, 2011, 10:32 PM
  3. Help with linked list
    By joecool594 in forum Collections and Generics
    Replies: 3
    Last Post: November 28th, 2010, 12:33 PM
  4. Simple linked list
    By Koren3 in forum Collections and Generics
    Replies: 10
    Last Post: November 2nd, 2009, 03:33 AM
  5. Recursive function based on Linked list
    By rosh72851 in forum Collections and Generics
    Replies: 1
    Last Post: March 9th, 2009, 06:23 PM