CODEWITHSUNDEEP
cpointersdoubly-linked-list
MFave
MFave

Reputation: 1074

Doubly linked list in C: Why do I have to explicitly reassign head and tail even when they are not changed?

I have a doubly linked list where you can add to the head or tail via a pointer to the pointer of the head or tail node.

This way you can just update the head and tail pointer to the address of the newest head or tail node.

I have those "pointer to pointers" initiated in their own function and stored in a structure that holds both.

When I add to the tail or head, I have to explicitly save the old head and reassign it, and the opposite for the tail. Otherwise, the structure gets mutated and the head also becomes the tail, or the tail becomes the head.

I'm trying to understand what is going on. Maybe the head/tail retaining struct has to be defined statically / globally?

Source here:

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

typedef struct dcl_node {
  char *content;
  struct dcl_node *next;
  struct dcl_node *prev;
} Node;

Node *create_node (char *content) {
  Node *n = malloc(sizeof(Node));
  n->content = content;
  n->next = NULL;
  n->prev = NULL;
  return n;
}

typedef struct dc_list {
  struct dcl_node **head;
  struct dcl_node **tail;
} DCList ;

DCList *init_list (char *content_head, char *content_tail) {
  Node *head = create_node(content_head);
  Node *tail = create_node(content_tail);
  head->next = tail;
  tail->prev = head;
  DCList *list = malloc(sizeof(DCList));
  list->head = &head;
  list->tail = &tail;
  return list;
}

void insert_head (char *content, DCList *list) {
  Node *old_head = *list->head;
  Node *old_tail = *list->tail; // note the saving here
  Node *node = create_node(content);
  node->next = old_head;
  old_head->prev = node;
  *list->head = node;
  *list->tail = old_tail; // and reassigning here
}

void insert_tail (char *content, DCList *list) {
  Node *old_head = *list->head; // note the saving here
  Node *old_tail = *list->tail;
  Node *node = create_node(content);
  node->prev = old_tail;
  old_tail->next = node;
  *list->head = old_head; // and reassigning here
  *list->tail = node;
}

int main (int argc, char *argv[]) {
  DCList *list = init_list("c", "d");

  insert_head("b", list);

  // If I don't explicitly save and reassign the tail node, 
  // in this case both head and tail would become the "b node".
    printf("head: %s\ntail: %s\n",
      (*list->head)->content, (*list->tail)->content);

  return 0;
}

Upvotes: 0

Views: 593

Answers (1)

Stack Exchange Broke The Law
Stack Exchange Broke The Law

Reputation: 58929

Because list->head and list->tail are pointers to local variables in the init_list function.

These variables are destroyed when init_list returns and the memory they were stored in can be reused.

By coincidence, when you save them in insert_head and insert_tail your saved head and tail variables (probably!) get the same memory addresses, so they don't get overwritten. Otherwise, the old head could be overwritten by node.

This is an approximate explanation - it's hard to tell what the compiler is actually doing. But the key point is that head and tail are destroyed when init_list returns and then your list->head and list->tail are pointing to free memory that can be reused.

Upvotes: 2

Related Questions