How to Initialize the tail pointer in a Doubly Linked List for it to not give Segmentation Fault

Question

Now I have created a loop to make 25 nodes for the doubly linked list. By Initializing head pointer as NULL in the main function, now the forward_traversing and show_first functions do work as intended. But the tail value cannot by initialized NULL and I don't know what to assign it or to change in this code to allow for the backward_traversing and show_last function to work.

During Debugging it throws Exception of "Segmentation Fault" in the functions:- backward_traversal and show_last.

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

typedef struct Node
{
    int value;
    struct Node *next_link;
    struct Node *prev_link;
} Node;

Node *create_node(int value)
{
    Node *new_node = malloc(sizeof(Node));
    new_node->value = value;
    new_node->next_link = NULL;
    new_node->prev_link = NULL;

    return new_node;
}

void forward_traversing(Node *head)
{
    Node *temp = head;

    while (temp != NULL)
    {
        printf("%d ", temp -> value);
        temp = temp->next_link;
    }
    printf("\n");
}

void backward_traversing(Node *tail)
{
    Node *temp = tail;

    while (temp != NULL)
    {
        printf("%d ", temp->value);
        temp = temp->prev_link;
    }
    printf("\n");
}

void show_first(Node *head)
{
    printf("%d is the first value\n", head->value);
}

void show_last(Node *tail)
{
    printf("%d is the last value\n", tail->value);
}

int main()
{
    Node *head = NULL , *temp = NULL , *tail = NULL;

    for (int i = 25; i >= 0; i--){
        temp = create_node(i);
        temp -> next_link = head;
        temp -> prev_link = tail;
        head = temp;
    }
    
    forward_traversing(head);
    backward_traversing(tail);
    show_first(head);
    show_last(tail);

    free(head);
    free(tail);
    free(temp);
    
    return 0;
}

I am currently trying to make several functions to insert at the start, end and in reference to another node and maybe somehow make that automate my making node process.

For OS I have Windows 11 and Compiler is GNU default compiler in Vs Code

Answer 1

There are a few issues in your code:

• As you already found out, you never update tail to anything else than NULL. This means that:

  1. All your created nodes will have NULL as value for their prev_link member.
  2. A backward traversal will not do anything useful as you pass NULL to it. Even if you would pass it the pointer to the first created node, it would only print that node because of the first point.
  3. free(tail) will fail

• Your list creation loop body only sets two pointers to add a node to a list, but it doesn't take care of setting any pointers towards that new node. If you add a node to the end of a list (either end), you need to have code to update the currently last (or first) node so it gets a pointer to the new node you want to add.

  I would suggest to extend the create_node function with an extra parameter that represents the node after which the new node should be inserted (if it is not NULL). That way you take that logic out of your main function.

• free(head) and free(tail) are not a good idea. These calls will free exactly 2 nodes, but this is problematic:

  1. As your list has more nodes than 2, this means all other nodes are not freed.
  2. If you would use this code to create a list of just one node (and would do it correctly), then head and tail would be equal, and so you would call free twice on the same pointer: that is an error.
  3. If you would use this code on a list that is empty (with head and tail equal to NULL) you would also make invalid calls to free.

  The way to go is to write a function that iterates the list and frees every node in it.

Here is how the above remarks would affect the following functions in your code:

Node *create_node(int value, Node *prev) // Add parameter
{
    Node *new_node = malloc(sizeof(Node));
    new_node->value = value;
    // Use extra argument to insert node after given node:
    Node *next = prev ? prev->next_link : NULL;
    new_node->prev_link = prev;
    new_node->next_link = next;
    // Adjust links TOWARDS the new node:
    if (prev) prev->next_link = new_node;
    if (next) next->prev_link = new_node;
    return new_node;
}

// Function to free a complete list
void free_list(Node *head) {
    while (head) {
        Node *temp = head;
        head = head->next_link;
        free(temp);
    }
}

int main()
{
    Node *head, *tail;
    // Treat the first node outside of the loop, so 
    //   you can update head just this one time:
    head = tail = create_node(0, NULL);
    for (int i = 1; i < 25; i++) {
        // Appending a node becomes easy when logic is
        //    completely in create_node function:
        tail = create_node(i, tail);
    }
    
    printf("Forward: ");
    forward_traversing(head);
    printf("Backward: ");
    backward_traversing(tail);
    show_first(head);
    show_last(tail);
    // Free *any* node in the list
    free_list(head);
    return 0;
}

Defining a list data structure

Once you start working with more than one list, it becomes impractical to manage head and tail for each of those. Then it becomes handy to also define a struct for lists, which would have those two members (head and tail). Once you have that you would use that as argument type for many of the functions you have.

Another point to make concerns separation of concerns. Printing is something you want to keep out of most functions. In particular, a traversal over a list could be useful for other purposes also, like for calculating the sum of the entries. It would be wasteful if you had to create a separate traversal function just to get a sum, and another one to get a count, ...etc. Better would be to make the traversal generic, so that you can decide with a function argument what should happen with each visited value.

Here is an illustration of what you could do:

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

typedef struct Node
{
    int value;
    struct Node *next_link;
    struct Node *prev_link;
} Node;

typedef struct List {
    Node *head;
    Node *tail;
} List;

Node *create_node(int value, Node *prev) {
    Node *new_node = malloc(sizeof(Node));
    new_node->value = value;
    Node *next = prev ? prev->next_link : NULL;
    new_node->prev_link = prev;
    new_node->next_link = next;
    if (prev) prev->next_link = new_node;
    if (next) next->prev_link = new_node;
    return new_node;
}

int is_empty(List *list) {
    return !list->head;
}

void append(List *list, int value) {
    list->tail = create_node(value, list->tail);
    if (!list->head) list->head = list->tail;
}

int pop(List *list) {
    if (is_empty(list)) return -1;
    Node *temp = list->tail;
    list->tail = list->tail->prev_link;
    if (!list->tail) list->head = NULL;
    int value = temp->value;
    free(temp);
    return value;
}

void clear_list(List *list) {
    while (!is_empty(list)) pop(list);
}

void forward_traversing(List *list, void (*f)(int)) {
    Node *temp = list->head;
    while (temp) {
        f(temp->value);
        temp = temp->next_link;
    }
}

void backward_traversing(List *list, void (*f)(int)) {
    Node *temp = list->tail;
    while (temp) {
        f(temp->value);
        temp = temp->prev_link;
    }
}

void print_int(int n) {
    printf("%d ", n);
}

int peek_first(List *list) {
    return is_empty(list) ? -1 : list->head->value;
}

int peek_last(List *list) {
    return is_empty(list) ? -1 : list->tail->value;
}

int main() {
    List list = {NULL, NULL};
    for (int i = 0; i < 25; i++) {
        append(&list, i);
    }
    
    // All printing is taken out of the list-specific functions
    printf("Forward: ");
    backward_traversing(&list, print_int);
    printf("\n");
    printf("Backward: ");
    backward_traversing(&list, print_int);
    printf("\n");
    printf("%d is the first value\n", peek_first(&list));
    printf("%d is the last value\n", peek_last(&list));
    clear_list(&list);
    return 0;
}

Answer 2

As your code adds new elements to the front of the list, you should only set tail when inserting first element. So:

Instead of:

temp -> prev_link = tail;

Do:

temp -> prev_link = NULL;
if (tail == NULL) tail = temp; // First element so update tail

When head isn't NULL, you also need to update head->prev_link

    if (head != NULL) head->prev_link = temp;

Further, you write: "Now I have created a loop to make 25 nodes"

Well, no you don't. This code:

for (int i = 25; i >= 0; i--){

will run 26 times so you create 26 nodes.

It's more common to make a loop starting from 0 so I would suggest this instead:

#define NODES 25

for (int i = 0; i < NODES; ++i){
    temp = create_node(NODES - 1 - i);
    temp -> next_link = head;
    temp -> prev_link = NULL;
    if (tail == NULL) tail = temp; // First element so update tail
    if (head != NULL) head->prev_link = temp;
    head = temp;
}

or perhaps a bit more clear:

for (int i = 0; i < NODES; ++i){
    temp = create_node(NODES - 1 - i);
    if (head == NULL) {
        head = temp;
        tail = temp;
    } else {
        temp -> next_link = head;
        head->prev_link = temp;
        head = temp;
    }
}