Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
The moose likes Beginning Java and the fly likes Linked List - inserting value to correct position Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Linked List - inserting value to correct position" Watch "Linked List - inserting value to correct position" New topic
Author

Linked List - inserting value to correct position

Josh Theisen
Ranch Hand

Joined: Sep 23, 2011
Posts: 31
Here's what I have for this assignment. Basically our teacher wants us to prompt the user to enter some integers (i.e. 1,4,3,6,8,2).
Then the method is supposed to insert those in the correct position so when we print it out, it'd print out as: 1,2,3,4,6,8

Here's what I have so far:



I'm prompting to enter a value - if it's "-1" then it'd finish the loop and quit. Else it's going to
check if the list is empty -- if it is, it will insert it right away.
Now this next part is where I'm getting tripped up. I know I"ll need to iterate through the list
(hence the list iterator) and see where to input the next value.

Any tips/pointers to help me get rolling on this?

If you need any more details, shout.
Thanks!
Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3418
    
  12
In order to insert a value at a specific place in the list you need to use the add(int index, E element) method.
Whilst you could do it using an iterator, a simple for loop and the List.get(int index) method would be better.
And you don't need to check that the list is empty. Get your for loop right and it will handle that condition.
Give it a go and if you have any problems, post your code and tell us what is not working correctly.


Joanne
Harsha Smith
Ranch Hand

Joined: Jul 18, 2011
Posts: 287
Beyond Assignment

Add all elements in the order given by the user.

use Collections.sort(List<T> list>) to sort the elements in ascending order.

use Collections.reverse(List<T> list>) to sort the elements in descending order
Josh Theisen
Ranch Hand

Joined: Sep 23, 2011
Posts: 31
Joanne Neal wrote:In order to insert a value at a specific place in the list you need to use the add(int index, E element) method.
Whilst you could do it using an iterator, a simple for loop and the List.get(int index) method would be better.
And you don't need to check that the list is empty. Get your for loop right and it will handle that condition.
Give it a go and if you have any problems, post your code and tell us what is not working correctly.

Interesting. How would I use a 'for' loop to do this though? I guess what I don't understand is
how you would determine the bounds of the loop? .



Harsha Smith wrote:
Beyond Assignment

Add all elements in the order given by the user.

use Collections.sort(List<T> list>) to sort the elements in ascending order.

use Collections.reverse(List<T> list>) to sort the elements in descending order

Yeah, this would be nice, but it isn't how he wants us to handle it though.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37923
    
  22
Sorting runs in On long n time and multiple insertion runs in quadratic time.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37923
    
  22
Josh Theisen wrote:. . . . . .
Your list has a method for its size, which you can use as your upper bound. You might need two nested loops, one which iterates your inputs and the other which iterates the LinkedList looking for the place to insert it. You would require two tests in the middle of the for loop (the continuation condition).

And are you quite sure it’s i > ??
Josh Theisen
Ranch Hand

Joined: Sep 23, 2011
Posts: 31
Campbell Ritchie wrote:And are you quite sure it’s i > ??

Whoops! Early morning here.

I think maybe I wasn't clear enough with what he wants us to do ... If so, sorry.
Here's an example:
-Program prompts user to enter and integer for an input: 1
-The list is of size 1 and then it asks for another input:4
-Size is 2 and it asks for another: 3
-The list should now insert 3 between 1 and 4
-Enter: -1
Program now exits and would then print out the list 1,3,4

With that being said, would a 'for' loop still work? The way I see it we don't know the actual size of the list since
it's being updated in 'real-time' (?)



Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3418
    
  12
Josh Theisen wrote:I think maybe I wasn't clear enough with what he wants us to do ... If so, sorry.
.
.
.
With that being said, would a 'for' loop still work? The way I see it we don't know the actual size of the list since
it's being updated in 'real-time' (?)

You were totally clear.

The size of the list is fixed whilst you are searching through it to find where to insert the new value. You would restart the for loop for each value and you don't actually insert the new value until the for loop has completed (assuming you get the conditional part of the for loop correct . As a hint - you will need to check two conditions and you don't need to loop throught the entire list each time).


Harsha Smith
Ranch Hand

Joined: Jul 18, 2011
Posts: 287
Understanding the following code may give you some idea. This is a not solution for your assignment.

Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3418
    
  12
Line 10 can be more simply written as
Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3418
    
  12
Hints to OP - not sure if this is helping too much. I guess it will be deleted if it is.

Simplify line 10 as above.
Then move it outside the loop (you'll have to change the variable declarations a bit).
Merge the if condition on line 8 into the line 7 for condition
Get rid of the boolean variable and the break;
Get rid of the remaining extraneous code.

That should leave you with 2 lines of code inside the outer for loop (the one that starts on line 5)
Josh Theisen
Ranch Hand

Joined: Sep 23, 2011
Posts: 31
Thanks for all the replies. I found out that my teacher might have wanted me to do it a different way...
With my own Node class and pointers. But if I can do it this way, I'll definitely refer back.

Thanks!
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37923
    
  22
Yesterday, I wrote:Sorting runs in On long n time . . .
What a spelling error! That should read log not long.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Linked List - inserting value to correct position
 
Similar Threads
Printing out a linked list
cannot insert into linkedlist after delete
[resolved] Problem with generic methods
'else' without 'if'
integer bit values