Sorted insert function for linked list

Question

I need to insert a node into a sorted link list, but I'm getting errors. Can someone help with what's wrong?

struct NodeType
{
ItemType value;
NodeType * next;
}


void sortedInsert( NodeType * & head, int data )
{
    NodeType * p = head;
    NodeType * prev = NULL;
    while (p->value < data)
    {
        prev = p;
        p= p -> next;
    }
    NodeType * newnode = new NodeType;
    newnode -> value = data;
    newnode -> next = prev;
    p -> next = newnode ;

I changed the program below but I'm getting an Thread 1: EXC_BAD_ACCESS (code=1, address=0x8) error on the line prev -> next = newnode, how can I change that line?

void sortedInsert( NodeType * & head, int data ){

NodeType * p = head;
NodeType * prev = NULL;
while (p->value < data)
    {
        prev = p;
        p= p -> next;
    }
NodeType * newnode = new NodeType;
    newnode -> value = data;
    newnode -> next = p;
    prev -> next = newnode;
if(head== nullptr)
{
    NodeType * newnode = new NodeType;
    newnode -> value = data;
    newnode -> next = head;
    return;
}
}

Explain to your Rubber duck what will happen at while (p->value < data) if head is null. — user4581301
– user4581301, Commented Oct 30, 2019 at 21:10
You also need to consider the case where the head node itself needs to be replaced. — user4581301
– user4581301, Commented Oct 30, 2019 at 21:13
You also mixed up the meaning of p and prev after the loop. Try choosing better identifier names. Draw 3 boxes on a piece of paper, write a value inside each box, and label the boxes prev, newnode, and p. Then connect them with arrows. Now look at your code and check it's doing what your drawing says it should do. — paddy
– paddy, Commented Oct 30, 2019 at 21:14
More like if(head== nullptr) { head = new NodeType { data, head }; return; }. If there is no head, the new node has nowhere else but the head to go. — user4581301
– user4581301, Commented Oct 30, 2019 at 21:40

user4581301 · Accepted Answer · 2019-10-30 22:38:47Z

A possible solution:

What's going on is tricky, so I explain it line by line as it happens.

void sortedInsert( NodeType * & head, int data )
{
    NodeType ** p = &head; // You don't really want to find a node, you want to
                           // find where the new node goes, so rather than
                           // tracking nodes, track their next pointers. Once 
                           // you find it, you know exactly where to put the 
                           // new node

                           // head exists to tell you where the first node is. 
                           // That makes it a glorified next pointer. We can 
                           // hide the different name by adding an extra level 
                           // of indirection. Now head and any next all look the 
                           // same and no special cases are needed to manage
                           // insertion at the head

    while (*p &&  // make sure there is a node. Don't want to peek into a node 
                  // that doesn't exist. This also finds the end of the list 
                  // for us
           (*p)->value < data) // the current node goes before the new node
                               // don't want to insert here, so keep looking
    {
        p= &(*p) -> next; // advance p to point at the current node's next
    }

    // now we've found where the new node has to go - the end of the list or
    // the insertion point before the first larger node
    NodeType * newnode = new NodeType;
    newnode -> value = data; // set the data
    newnode -> next = *p; // point at the current node's next
    *p = newnode ; // insert new node at insertion point found earlier 

    // note: the preceding four lines probably could be
    // *p = new NodeType{data, *p};
}

And once more without all the commentary and fluff

void sortedInsert( NodeType * & head, int data )
{
    NodeType ** p = &head; 
    while (*p &&  (*p)->value < data)
    {
        p= &(*p) -> next;
    }
    *p = new NodeType{data, *p};
}

pastoruri · Accepted Answer · 2019-10-30 21:46:41Z

You are redefining pointers in these lines:

prev = p;
p = p -> next;

You are defining prev as p, then you are changing p, because you are using pointers, you are also redifining prev. You can avoid doing this by doing something like this

while(p->next -> value < data){
p = p->next;
} //Whats this is doing is analizing the next value, so there's no need to use a prev
because your p is prev.

Once you have reached the point where it stops, you are going to have something like this:

eg:

Say I have data = 12, when the process stops, my p is going to be in this position in this example array.

5 7 9 10  11 14
---------[P]--

Now I must do (pseudo code)

auto aux = p.next;

node mynode(data);

mynode.next = aux;

p.next = mynode;

Hope this is useful :)

Collectives™ on Stack Overflow

Sorted insert function for linked list

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related