What is a Linked List? How to implement it? What are the types of lists used in C?

Linked List definition

List or linked list is a collection of nodes/recodes linked with each other using pointer. A node data structure has at least a member to hold the current element value and a pointer to point to the next node.

Linked List data-structure

typedef struct _slist_node
{
  int node_value;            /* value/data of this node */
  struct _slist_node * next; /* point to next node */
}slist_node;

In this example nodes will be object of structure slist_node. Node_value member will be used to hold a user value. Member “next” will be used to point the next member in the list.

The first node of the linked list is called head and last node is the tail. When there is no element both head = tail = null. A new node object is created from heap using malloc/new and added to the list by setting proper value of the next/previous pointer. When we need to delete a particular node, we modify the next/previous pointer of the neighboring node and delete the node from heap using free/delete. This is a vital advantage list over array. We can add or remove any node at any location and memory is allocated or de-allocated at the run time.

Allocate New node

new_node() function allocates new node for the given input value. It also takes care memory allocation error.

slist_node * new_node(int value)
{
  slist_node * new_n = NULL;
  new_n = (slist_node *) malloc(sizeof(slist_node));
  if(new_n == NULL) {
    return NULL;
  }
  memset(new_n, 0, sizeof(slist_node));
  new_n->next = NULL;
  new_n->node_value = value;
  return new_n;
}

Add at head

add_head() function allocates and adds a node before the existing head. New allocated node becomes the new head for the list.

slist_node * add_head(slist_node * head, int value)
{
  slist_node * new_n = NULL;
  new_n = new_node(value);
  if(new_n == NULL) {
    return NULL;
  }
  new_n->next = head;
  return new_n;
}

Add at end/tail

add_tail() function allocates and adds a node after the tail. New allocated node becomes the new head for the list.

void add_tail(slist_node * head, int value)
{
  slist_node * new_n = NULL;
  slist_node * tmp_n;
  if(!head){
    return;
  }
  new_n = new_node(value);
  if(new_n == NULL) {
    return NULL;
  }
  tmp_n = head;
  while (tmp_n && tmp_n->next) {
    tmp_n = tmp_n->next;
  }
  /* Reached the tail, now add this after tail */
  tmp_n->next = new_n;
  return;
}

Delete head

delete_head() function deletes head and returns the new head which is the node next to the head.

slist_node * delete_head(slist_node * head)
{
  slist_node *tmp_n;
  tmp_n = head;
  if (!head) {
    return NULL;
  }
  tmp_n = head->next;
  free(head);
  return tmp_n;
}

Delete tail

delete_tail() function deletes tail and makes the previous node as tail. If head is the only node in the list then list becomes empty.

void delete_tail(slist_node ** head)
{
  slist_node *tmp_n, *tmp_prev;
  /* Head is NULL or head pointer is NULL or empty */
  if (!head || !*head) {
    return;
  }
  /* Head is the only one node */
  if(!*head->next) {
   free(*head);
   *head = NULL;
  }
  /* when list has more than one node */
  tmp_n = *head;
  while (tmp_n && tmp_n->next) {
    tmp_prev = tmp_n; /* point to previous node */
    tmp_n = tmp_n->next; /* point to next node */
  }
  tmp_prev->next = NULL; /* make it tail */
  free(tmp_n); /* delete the original tail */
  return;
}

Advantages

  1. Best utilization of memory at run time.
  2. Addition and removal of any element is at any position is possible. Thus it eliminates constrain of the array where we cannot add or remove elements after the whole array has been allocated once.

Disadvantages

  1. It uses some few bytes(pointer 4 byte for 32 bit) extra for each element.
  2. Finding any element is not straight forward as array. It needs iteration and more CPU cycle.

Types of Linked lists

There are four types of list used in common programming practices. They are -

  1. Single Linked List: Each node has only next pointer to point the next node in the list.
  2. Doubly Linked List: Each node has both next and previous pointer to point next and previous node in the list.
  3. Circular Linked List: Next pointer of tail node points to again head node.
  4. Doubly Circular Linked List: This list has both the properties of doubly linked list and circular linked list.
Single/Doubly Linked list can be used to construct some other useful data structures like queues, stack etc.

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›

Questions index C Questions C++ Questions Win32 MFC COM/DCOM DLL Questions