CODEWITHSUNDEEP
c++
ronnie
ronnie

Reputation: 13

Sorted insert function for linked list

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;
}
}

Upvotes: 0

Views: 93

Answers (2)

user4581301
user4581301

Reputation: 33931

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};
}

Upvotes: 1

pastoruri
pastoruri

Reputation: 31

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 :)

Upvotes: 0

Related Questions