Linked List - inserting value to correct position

[Josh Theisen]

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:

public static void sorted() {

		LinkedList<Integer> list = new LinkedList<Integer>();
		ListIterator iterator = list.listIterator();

		boolean notQuit = true;

		while (notQuit) {
			System.out.print("Enter integer to input (-1 to exit): ");
			int x = scanner.nextInt();

			if (x == -1) {
				notQuit = false;
			}

			else {

				if (list.size() == 0) {
					list.add(x);
				} else {
					//Something goes here...
				}
			}

		}
	}

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]

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.

[Harsha Smith]

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]

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?

for (int i = 0; i > bound; i++)

.

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]

Sorting runs in On long n time and multiple insertion runs in quadratic time.

[Campbell Ritchie]

Josh Theisen wrote:. . .

for (int i = 0; i > bound; i++)

. . .

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]

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]

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]

Understanding the following code may give you some idea. This is a not solution for your assignment.

int[] array = { 1, 4, 3, 6, 8, 2 };

		LinkedList<Integer> list = new LinkedList<Integer>();

		  for (int i : array) {
			boolean isInserted = false;
			for (int k = 0; k < list.size(); k++) {
				if (list.get(k) >= i) {

					list.add(list.indexOf(list.get(k)), i);
					isInserted = true;
					break;
				}
			}
			if (!isInserted) {
				list.addLast(i);
			}
		}
		System.out.println(list);

[Joanne Neal]

Line 10

list.add(list.indexOf(list.get(k)), i);

can be more simply written as

list.add(k, i);

[Joanne Neal]

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]

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]

Yesterday, I wrote:Sorting runs in On long n time . . .

What a spelling error! That should read log not long.