Doubly Linked LIst

dll.c

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

struct Node {
  int data;
  struct Node *next;
  struct Node *prev;
};

void printList(struct Node *node) {
  printf("Head ");
  while (node != NULL) {
    printf(" --> | %p | %d | %p | ", node->prev, node->data, node->next);
    node = node->next;
  }
  printf(" -> NULL\n\n");
}

void insertFront(struct Node **head, int data) {
  /* allocate the memory for newNode */
  struct Node *newNode = malloc(sizeof(struct Node));
  if (newNode == NULL) {
    return;
  }
  /* assign the data to newNode */
  newNode->data = data;

  /* point next to the first existing node */
  newNode->next = *head;
  /* point prev to null */
  newNode->prev = NULL;

  /* point prev of the first node to the new node */
  if ((*head) != NULL) {
    (*head)->prev = newNode;
  }
  /* point head to newNode */
  *head = newNode;
}

void insertAfter(struct Node *prev_node, int data) {
  /* check if previous node is NULL */
  if (prev_node == NULL) {
    return;
  }

  /* allocate the memory for newNode */
  struct Node *newNode = malloc(sizeof(struct Node));
  if (newNode == NULL) {
    return;
  }
  /* assign the data to newNode */
  newNode->data = data;

  /* set the next of newNode to point to next_node (which is prev_node->next) */
  newNode->next = prev_node->next;

  /* make newNode prev_node's next */
  prev_node->next = newNode;

  /* make prev_node newNode's previous */
  newNode->prev = prev_node;

  /* make next_node's previous the newNode */
  if (newNode->next != NULL) {
    newNode->next->prev = newNode;
  }
}

void insertEnd(struct Node **head, int data) {
  /* allocate the memory for newNode */
  struct Node *newNode = malloc(sizeof(struct Node));
  if (newNode == NULL) {
    return;
  }

  /* assign the data to newNode */
  newNode->data = data;

  /* store the head temporarily for later user */
  struct Node *temp = *head;

  /* if the list is empty, just make newNode the head node */
  if (*head == NULL) {
    newNode->prev = NULL;
    *head = newNode;
    return;
  }

  /* if the list if NOT empty, traverse to the end of it */
  while (temp->next != NULL) {
    temp = temp->next;
  }

  /* point the next of the last node to newNode */
  temp->next = newNode;

  /* point the prev of the newNode to temp */
  newNode->prev = temp;
}

void deleteNode(struct Node **head, struct Node *del_node) {
  /* if the list is empty or the node to be deleted does not exists */
  if (*head == NULL || del_node == NULL) {
    return;
  }

  /* if the node to be deleted is the first node, make the next one the head */
  if (*head == del_node) {
    *head = del_node->next;
  }

  /* change the next node only if the del_node is not the last */
  if (del_node->next != NULL) {
    del_node->next->prev = del_node->prev;
  }

  /* change the prev node only if the del_node-is not the first */
  if (del_node->prev != NULL) {
    del_node->prev->next = del_node->next;
  }
}

struct Node *createList() {
  struct Node *one = malloc(sizeof(struct Node));
  struct Node *two = malloc(sizeof(struct Node));
  struct Node *three = malloc(sizeof(struct Node));

  one->data = 1;
  two->data = 2;
  three->data = 3;

  one->next = two;
  one->prev = NULL;

  two->next = three;
  two->prev = one;

  three->next = NULL;
  three->prev = two;

  return one;
}

int main(int argc, char *argv[]) {
  struct Node *head = createList();
  printf("creating list\n\n");
  printList(head);
  int data = 6;

  printf("inserting %d in the beginning\n\n", data);
  insertFront(&head, data);
  printList(head);

  printf("deleting the first node\n\n");
  deleteNode(&head, head);
  printList(head);

  printf("inserting %d in after the first node\n\n", data);
  insertAfter(head, data);
  printList(head);

  printf("deleting the second node\n\n");
  deleteNode(&head, head->next);
  printList(head);

  printf("inserting %d at the end\n\n", data);
  insertEnd(&head, data);
  printList(head);
}

dll.svg

out.txt

creating list

Head  --> | (nil) | 1 | 0x56116d2912c0 |  --> | 0x56116d2912a0 | 2 | 0x56116d2912e0 |  --> | 0x56116d2912c0 | 3 | (nil) |  -> NULL

inserting 6 in the beginning

Head  --> | (nil) | 6 | 0x56116d2912a0 |  --> | 0x56116d291710 | 1 | 0x56116d2912c0 |  --> | 0x56116d2912a0 | 2 | 0x56116d2912e0 |  --> | 0x56116d2912c0 | 3 | (nil) |  -> NULL

deleting the first node

Head  --> | (nil) | 1 | 0x56116d2912c0 |  --> | 0x56116d2912a0 | 2 | 0x56116d2912e0 |  --> | 0x56116d2912c0 | 3 | (nil) |  -> NULL

inserting 6 in after the first node

Head  --> | (nil) | 1 | 0x56116d291730 |  --> | 0x56116d2912a0 | 6 | 0x56116d2912c0 |  --> | 0x56116d291730 | 2 | 0x56116d2912e0 |  --> | 0x56116d2912c0 | 3 | (nil) |  -> NULL

deleting the second node

Head  --> | (nil) | 1 | 0x56116d2912c0 |  --> | 0x56116d2912a0 | 2 | 0x56116d2912e0 |  --> | 0x56116d2912c0 | 3 | (nil) |  -> NULL

inserting 6 at the end

Head  --> | (nil) | 1 | 0x56116d2912c0 |  --> | 0x56116d2912a0 | 2 | 0x56116d2912e0 |  --> | 0x56116d2912c0 | 3 | 0x56116d291750 |  --> | 0x56116d2912e0 | 6 | (nil) |  -> NULL