CODEWITHSUNDEEP
clinked-list
Austin
Austin

Reputation: 11

c - insertBefore linked list

Ok so I have been working on my first singly linked list project and I have hit a wall. One of the algorithms I am trying to implement is to insert a node before a node specified by the user. The problem I am having is that when the node is inserted it is placed at the correct location but then it also deletes all nodes before it. If my list originally contained: 1 2 3 4 5 And I wanted to insert 0 before 4 the result is: 0 4 5

struct node *insertBefore(struct node *start, int data, int x)
{
    struct node *marker = NULL;
    struct node *prev = NULL;
    struct node *temp = NULL;

    temp = (struct node*)malloc(sizeof(struct node));

    marker = start;

    while(marker != NULL && marker->info != x)
    {
        prev = marker;
        marker = marker->link;
    }
    if(!marker)
    {
        printf("*Element containing %d not found*\n", x);
        return;
    }
    if(marker == start)
    {
        temp->info = data;
        temp->link = marker;
        return;
    }
    temp->info = data;
    temp->link = prev->link;
    prev->link = temp;
    temp->link = marker;

    return; 
}

Upvotes: 1

Views: 4000

Answers (1)

Mateen Ulhaq
Mateen Ulhaq

Reputation: 27201

Think carefully about what you're doing.

If you are inserting one node, you should not create three!

temp = (struct node*)malloc(sizeof(struct node));
marker = (struct node*)malloc(sizeof(struct node));
prev = (struct node*)malloc(sizeof(struct node));

The way you should approach this is:

// Search for relevant node
while(marker != NULL && marker->info != x) {
    prev = marker;
    marker = marker->link;
}

// Verify you found somewhere to insert
if(marker == NULL) {
    // No x found
    return start;
}

// Allocate and initialize node
struct node* insert_node = (struct node*)malloc(sizeof(struct node));
insert_node->info = data;
insert_node->link = marker;

if(prev == NULL) {
    // Inserted node is the new start node
    start = insert_node;
}
else {
    // Relink chain
    prev->link = insert_node;
}

// Return the NEW start node.
// This is needed in case the new node is inserted before the original start node!
return start;

If you code cleverly (this means thinking!), you can write it very simply and avoid corner cases. Corner cases include:

  • Empty input list
  • First element is x
  • No x within list

Looking at your code again, you're doing a few unusual things. One is that you allocate memory before you're sure that you want to insert an element:

temp = (struct node*)malloc(sizeof(struct node));

Also, you change temp->link twice, consecutively.

temp->link = prev->link;
prev->link = temp;
temp->link = marker;

You don't have any mechanism to update the start node in case the first element in the list changes.

Upvotes: 1

Related Questions