Linked List. Insert integers in order

Question

I have a linked list of integers. When I insert a new Node I need to insert it not at the end, but in oder... i.e. 2, 4, 5, 8, 11, 12, 33, 55, 58, 102, etc. I don't think I am inserting it in the correct position. Do see what Im doing wrong?

 Node newNode = new Node(someInt);
 Node current = head;

        for(int i=0; i<count; i++){
            if(current == tail && tail.data < someInt){
                tail.next = newNode;
            }   
            if(current.data < someInt && current.next.data >= someInt){
                newNode.next = current.next;
                current.next = newNode;
            }
        }

Unless you want retrieval by index or duplicates, I'd suggest you to use a SortedSet<Node> and Node implements Comparable<Node> instead. — BalusC
– BalusC, Commented May 2, 2010 at 20:50
@BalusC: I'm pretty sure this is a write-your-own X HW assignment, based on user69514 question history and the question itself. Which I suspect means real answers are out, though SortedSet<Integer> would probably suffice, since it seems that's all the data Node holds. — Carl
– Carl, Commented May 3, 2010 at 1:22

Chris J · Accepted Answer · 2010-05-02 23:46:07Z

4

I think this might be closer to what you are looking for.

Node newNode = new Node(someInt);
Node current = head;
//check head first
if (current.data > newNode.data) {
  newNode.next = head;
  head = newNode;
}

//check body
else {
  while(true){
    if(current == tail){
      current.next = newNode;
      tail = newNode;
      break;
    }   
    if(current.data < someInt && current.next.data >= someInt){
      newNode.next = current.next;
      current.next = newNode;
      break;
    }
    current = current.next;
  }
}

edited May 2, 2010 at 23:46

answered May 2, 2010 at 20:56

Chris J

9,2827 gold badges42 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user69514 Over a year ago

this look better, but it goes into an infinite loop

Chris J Over a year ago

whoops, forgot to update the current reference at the end of the loop

McAden · Accepted Answer · 2010-05-02 20:54:44Z

2

You're never moving forward in the list. you need an else that sets:

current = current.next

You can also add a break statement after you've inserted the node since at that point you're done with the loop.

edited May 2, 2010 at 20:54

answered May 2, 2010 at 20:48

McAden

14k5 gold badges39 silver badges63 bronze badges

Comments

Paige Ruten · Accepted Answer · 2010-05-02 20:48:48Z

1

It doesn't look like you're updating current... try inserting something like this in your loop:

current = current.next;

answered May 2, 2010 at 20:48

Paige Ruten

177k37 gold badges183 silver badges199 bronze badges

Comments

Dominik · Accepted Answer · 2010-05-02 21:09:01Z

0

Looks like you missing the case, when the new element is lesser than all existing ones.

answered May 2, 2010 at 21:09

Dominik

1,2721 gold badge14 silver badges32 bronze badges

Collectives™ on Stack Overflow

Linked List. Insert integers in order

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related