C Doubly Linked List Segmentation Fault

I have written my own linked list implementation in C, and it works fine for storing values, but whenever I try to run through the list I get a segmentation fault. I'm not sure why the issue arises, and I spent a decent amount of time trying to run through the program myself but to no avail. Could you guys help me find the reason for the error? Here is my code:

#include <stdlib.h>
#include <stdio.h>

// A double linkd list node
struct list
{
    struct list * prev;
    int data;
    struct list * next;
};
typedef struct list node;
node *head = NULL;
node *tail = NULL;

// Adds an item to the end of the list
void append(int item);
// Adds an item at the given index
int insert(int item, int index);
// Removes and returns an item at the specified index
int remove_node(int index);
// Gets an item at the specified index
int get(int index);
// Returns the node at the specified index
node* get_node(int idex);


// Adds an item to the end of the list
void append(int item)
{
    // If no items have been added to the list yet   
    if(head == NULL)
    {
        head = (node*) malloc(sizeof(node));
        head->prev = NULL;
        head->data = item;
        head->next = NULL;
        tail = head;
        printf("Successfully added the head\n");
    }
    // If items have previously been added to the list
    else
    {
        node *current = (node*) malloc(sizeof(node));
        printf("Successfully allocated memory for the next item\n");
        current->prev = tail;
        printf("Assigned current previous link to tail\n");
        current->data = item;
        printf("Assignd current's data value: %d\n", item);
        current->next = NU开发者_运维问答LL;
        printf("Assigned current's next value to NULL\n");
        tail = current;
        printf("Assigned tail to current\n\n\n");
    }
}


// Adds an item at the given index
// Returns an int. Nonzero means there was an error
int insert(int item, int index)
{
    node *current, *new;
    current = head;

    for( ; index > 0; index--)
    {
        current = current->next;
    }

    // Make a new node and properly connect it
    new = (node*) malloc(sizeof(node));
    new->prev = current->prev;
    new->data = item;
    new->next = current;
    current->prev = new;

    return 0;
}


// Removes and returns an item at the specified index
int remove_node(int index)
{
    int ret;
    node *current = head;

    for( ; index > 0; index--)
    {
        current = current->next;
    }
    ret = current->data;

    // Connect the nodes on both sides of current
    (current->prev)->next = current->next;
    (current->next)->prev = current->prev;

    free(current);
    return ret;
}


// Gets an item at the specified index
int get(int index)
{
    return (get_node(index))->data;
}

// Returns the node at the specified index
node* get_node(int index)
{
    node *current = head;
    for( ; index > 0; index--)
    {
        current = current->next;
    }
    return current;
}


int main(void)
{
    int i;
    for(i = 0; i < 10; i++)
    {
        append(i);
    }

    node *current = head;
    for(i = 0; i < 10; i++)
    {
        printf("%d\n", current->data);
        current = current->next;
    }

    return 0;
}

Your append() function is incorrect - it also needs to set tail->next = current; (before changing tail).

Your insert() function similarly needs to set current->prev->next = new; if current->prev is not NULL; otherwise it needs to set head = new;. It also needs to handle current being NULL.

Your remove_node() function needs to handle the cases of current->prev and/or current->next being NULL (it should update head and tail respectively in those cases).

It would also be a good idea if your functions that take an index take care not to run off the end of the list, if the index given is out of bounds.

In this section of your code:

else
{
    node *current = (node*) malloc(sizeof(node));
    printf("Successfully allocated memory for the next item\n");
    current->prev = tail;
    printf("Assigned current previous link to tail\n");
    current->data = item;
    printf("Assignd current's data value: %d\n", item);
    current->next = NULL;
    printf("Assigned current's next value to NULL\n");
    tail = current;
    printf("Assigned tail to current\n\n\n");
}

You don't set tail->next to current anywhere, so next will always be NULL. In general, this kind of bug should be easy to spot with a debugger attached. Just step through the code line-by-line and you'll see that in your loop where you're printing out the values, current->next is NULL.

Immediate problems:

1/ When you append, you do not set the current tail's next pointer to be the new node.

2/ When inserting, you do not check that you've moved beyond the end of your list.

3/ Likewise, when removing, you don't check that you're trying to move beyond the bounds of your list.

4/ When removing, you don't check the edge cases. For example, removing the current head will cause you to try and set (current->prev)->next to something even though current->prev is NULL.

5/ The loop in main, along with item 1 above is what's causing your segfault. That's because head->next is never being set to the tail so, even though your creating items, they're not is the list that head knows about.

It's actually a strange approach to take inasmuch as what's normally done is that you remove based on value rather than index. If you're going to remove (or print or process in any way) a node based on index, you should handle the case where the index given is beyond the bounds of the list.

I've often found that it's useful to draw the current list with paper and pencil then bench-run your code to make sure it's working as expected. For a wonderful example of this, see here.

By way of explaining what's wrong with your append code (where ? represents an unknown value and ! means an unknown pointer, forward links at the top, backward links at the bottom):

head
    \
     NULL
         \
          tail

Append (7):

# head = (node*) malloc(sizeof(node));
head   !
    \ /
     ?      NULL
    /           \
   !             tail

# head->prev = NULL;
head   !
    \ /
     ?
    /
NULL        NULL
                \
                 tail

# head->data = item;
head   !
    \ /
     7
    /
NULL        NULL
                \
                 tail

# head->next = NULL;
head   NULL
    \ /
     7
    /
NULL        NULL
                \
                 tail

# tail = head;
head   NULL
    \ /
     7
    / \
NULL   tail

Now that all looks okay. You could traverse that forwards and backwards without issue. Now let's append another value.

# Initial state.
head   NULL
    \ /
     7
    / \
NULL   tail

Append (9):

# node *current = (node*) malloc(sizeof(node));
head   NULL          !
    \ /             /
     7             ? <- curr
    / \           /
NULL   tail      !

# current->prev = tail;
head   NULL          !
    \ /             /
     7             ? <- curr
    / \___________/
NULL   tail

# current->data = item;
head   NULL          !
    \ /             /
     7             9 <- curr
    / \___________/
NULL   tail

# current->next = NULL;
head   NULL          NULL
    \ /             /
     7             9 <- curr
    / \___________/
NULL   tail

# tail = current;
head   NULL          NULL
    \ /             /
     7             9 <- curr
    / \___________/ \
NULL                 tail

Now you should be able to see easily what's missing there. There's no link from head to the node that we're adding.

That means that any loop starting at head will only ever see one element in the list. It also means that, if you try to dereference head->next (such as using a 10-iteration for loop for example), you will get undefined behaviour, which is what's causing your segfault.

To fix it, back up one step and insert tail->next = current; before the tail = current;:

# current->next = NULL; // Back up a bit.
head   NULL          NULL
    \ /             /
     7             9 <- curr
    / \___________/
NULL   tail

# tail->next = current; // This is the step we're adding.
head   ___________   NULL
    \ /           \ /
     7             9 <- curr
    / \___________/
NULL   tail

# tail = current;
head   ___________   NULL
    \ /           \ /
     7             9 <- curr
    / \___________/ \
NULL                 tail

And there's our new list, fully traversable in both directions. You can add another one using the same method to verify that the behaviour is correct.

for( ; index > 0; index--)
{
    current = current->next;
}

could try to look for a NULL's next which leads to Segmentation fault. If you meant retrieving the elements of the list by 'run through' that is.

You are crashing here because current->data is null:

node *current = head;
for(i = 0; i < 10; i++)
{
    printf("%d\n", current->data);  // here 
    current = current->next;
}

Instead of the for loop you could have something like while (current). You still have another problem but this is causing your seg fault.

You can find line causing the error with gdb:

> gcc -g list.c
> gdb a.out
(gdb) run