Linked List

Linked List

Linked List Definition

A linked list is a dynamic data structure where a node is made up of two items - the data and a reference (or pointer) which points to the next node. A linked list is a collection of nodes where each node is connected to the next node through a pointer. The first node is called a head and if the list is empty then the value of head is NULL.For a real-world analogy of linked list, you can think of conga line, a special kind of dance in which people line up behind each other with hands on shoulders of the person in front.

A Simple Linked List

Circular Single Linked list

In Circular Single Linked List, last node contains a pointer to the first node,We can have a circular singly linked list as well as a circular doubly linked list.There is no storing of NULL values in the list

Implementation

Insertion
A node can be added in three ways:

• Insertion in an empty list
• Insertion at the beginning of the list
• Insertion at the end of the list
• Insertion in between the nodes

Doubly Linked List

 A linked list data structure with two link, one that contain reference to the next data and one that contain reference to the previous data.

Example:

struct tnode {

  int value;

  struct tnode *next;

  struct tnode *prev;

  };

•

  struct tnode *head = 0;

  struct tnode *tail = 0;

Implementation:

Insert:

Insert new node behind the tail:

struct tnode *node =

  (struct tnode*) malloc(sizeof(struct tnode));

  node->value = x;

  node->next  = NULL;

  node->prev  = tail;

  tail->next  = node;

  tail = node;

Insert new node in any location between head and tail:

struct tnode *a = ??;

struct tnode *b = ??;

// the new node will be inserted between a and b

struct tnode *node =

    (struct tnode*) malloc(sizeof(struct tnode));

node->value  = x;

node->next  = b;

node->prev  = a;

a->next  = node;

b->prev  = node;

Delete:

There are 4 conditions we should pay attention when deleting:

The node to be deleted is the only node in linked list.

The node to be deleted is head.

The node to be deleted is tail.

The node to be deleted is not head or tail.

•If the node to be deleted is the only node:

  free(head);

  head = NULL;

  tail = NULL;

•If the node to be deleted is head:

  head = head->next;

  free(head->prev);

  head->prev = NULL;

•If the node to be deleted is tail:

tail = tail->prev;

free(tail->next);

tail->next = NULL;

         •If the node to be deleted is not in head or tail:

        struct tnode *curr = head;

        while ( curr->next->value != x ) curr = curr->next;

        struct tnode *a   = curr;

        struct tnode *del = curr->next;

        struct tnode *b   = curr->next->next;

        a->next = b;

        b->prev = a;

        free(del);

Circular Doubly Linked List

Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two consecutive elements are linked or connected by previous and next pointer and the last node points to first node by next pointer and also the first node points to last node by previous pointer.

Source:
https://study.com/academy/lesson/linked-lists-in-c-programming-definition-example.html
https://www.geeksforgeeks.org/circular-singly-linked-list-insertion/
https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/