Segmentation Fault - Linked List

Question

I am learning how to build linked lists in C. My program compiles but for some reason I cannot figure out, I am getting a segmentation fault. I've been trying to figure out the problem for a while, but I am not having any luck. Here is the faulty code:

int len()
{
    struct list * current = head;
    int length = 0; 

    while (current != NULL)
    {
        length++;
        current = current -> next; //move to next node
    }
    return length; 
}


struct list * search ( int key)
{
    struct list * current = head;

    while (current != NULL && current->data != key)
        current = current -> next;

    if (current != NULL && current -> data == key)
        return current;
    return NULL;
}



/* Insert a new data element with key d into the end of the list. */
void insert(int d )  //  at the end
{
    struct list * current = head; 
    struct list * new;
    while (current -> next != NULL)
        current = current -> next;
    new = (struct list *)malloc(sizeof(struct list));
    new -> data = d; 
    current -> next = new;
    new -> next = NULL;     
}


void insertAfter(int d, int where )  //  insert at the middle
{
    struct list * marker = head;
    struct list * new;

    while(marker -> data != where)
        marker = marker -> next;
    new = (struct list*)malloc(sizeof(struct list));

    new -> next = marker -> next; 
    marker -> next = new;
    new -> data = d; 
}


/* Remove the node with value d from the list */
/* assume no duplicated keys in the list */
/* If the list is empty, call prtError() to display an error message and return -1. */

void delete(int d)
{
    struct list * current1 = head; 
    struct list * current2;

    if (len() == 0)
    { //prtError("empty");
        exit(0);
    }
    if (head -> data == d)
    { 
        head = head -> next;
    }

    //Check if last node contains element
    while (current1->next->next != NULL)
        current1 = current1->next;

    if(current1->next->data == d)
            current1->next == NULL; 


    current1 = head; //move current1 back to front */

    while(current1 -> next -> data != d)
        current1 = current1 -> next; 

    current2 = current1 -> next;
    current1 -> next = current2 -> next; 

}

I am getting a segmentation fault in the delete method at the line:

while(current1 -> next -> data != d)

Why is this wrong?

Answer 1

You have several issues, in insert:

while (current -> next != NULL)

you are not checking if current is NULL. There are similar issues in delete:

if (head -> data == d)

you need to check head here and:

while (current1->next->next != NULL)

is also a problem.

Answer 2

There is an error in insert after in that you will overrun the end of the list the element is not found.

Answer 3

There are many problems with the code that you post, but your mention in your comments you are concerned about insert(). The reason it crashes is that you will dereference a NULL pointer if head is NULL when insert() is called.

You will need a special case to insert at the head when it is NULL:

if (head) {
    while (current -> next != NULL)
        current = current -> next;
}
new = (struct list *)malloc(sizeof(struct list));
new -> data = d;
if (current) {
    current -> next = new;
} else {
    head = new;
}
new -> next = NULL;

You should check for similar issues in your other functions. Use your search() function as an example of avoiding dereferencing a NULL pointer in your loop.

Answer 4

In insert,

while(current->next != NULL) current = current->next;

This will guarantee that current == NULL.

current->next = new;

Crashes it every time.

Answer 5

Maybe it's in insertAfter:

while(marker -> data != where)
    marker = marker -> next;

If no node with data == where is found, marker will be a NULL pointer.
The NULL pointer is dereferenced later in your code:

new = marker -> next;

It makes a segfault. Checking if marker->next != NULL should avoid that:

while(marker->next != NULL && marker -> data != where)
    marker = marker -> next;

But you should try to compile your program with debugging symbols (-g option) and run it line-by-line in a debugger like GDB.