Linked List Implementation 1

Linked List Implementation 1

I. Single Linked List

To create a list, we first need to define a node structure for the list.

Supposed we want to create a list of integers.

struct tnode {

  int value;

  struct tnode *next;

};

struct tnode *head = 0;

II. Single Linked List : Insert

To insert a new value, first we should dynamically allocate a new node and assign the value to it

and then connect it with the existing linked list.

Supposed we want to append the new node in front of the head.

struct tnode *node =

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

node->value = x;

node->next  = head;

head = node;

III. Single Linked List : Delete

To delete a value, first we should find the location of node which store the value we want to 

delete, remove it, and connect the remaining linked list.

struct tnode *curr = head;

// if x is in head node

if ( head->value == x ) {

  head = head->next;

  free(curr);
}

// if x is in tail node

else if(tail->value == x){

  while(curr->next!=tail) curr = curr->next;

  free(tail); tail = curr;

  tail->next = NULL;

}

// if x is not in head node, find the location

else {

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

  struct tnode *del = curr->next;

  curr->next = del->next;

  free(del);

}

III. Polynomial Representation

•Polynomial is given as 6x3 + 9x2 + 1

•Every individual term in a polynomial consists of two parts, a coefficient and a power

•Here, 6, 9, 7, and 1 are the coefficients of the terms that have 3, 2, 1, and 0 as their

 power respectively.

•Every term of a polynomial can be represented as a node of the linked list.

\

IV. Circular Single Linked List

In circular, 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.

V. Doubly Linked List

Doubly linked list or two-way linked list is 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.

          struct tnode {

  int value;

  struct tnode *next;

  struct tnode *prev;

};

struct tnode *head = 0;

struct tnode *tail = 0;

VI. Doubly Linked List : Insert

Just like in a single linked list, first we should allocate the new node and assign the value

 to it, and then we connect the node with the existing linked list.

Supposed we want to append the 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;

VII. Doubly Linked List : 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.

1.  If the node to be deleted is the only node:

      free(head);

      head = NULL;

      tail = NULL;

2.If the node to be deleted is head:

      head = head->next;

      free(head->prev);

      head->prev = NULL;

3.If the node to be deleted is tail:

      tail = tail->prev;

      free(tail->next);

      tail->next = NULL;

4.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);

VIII. Circular Doubly Linked List

It is similar with circular single linked list, but total pointer in each node here is 

2 (two) pointers.

IX. Header Linked List

A header linked list is a special type of linked list which contains a header node at 

the beginning of the list. So, in a header linked list, START (L) will not point to the first 

node of the list but START (L) will contain the address of the header node.