Linked List in Data Structure and Algorithm, Types, Operations

A linked list is a data structure that simulates a dynamic list of data items without knowing the size at compile time. During the runtime, the linked list may grow or shrink.

We are all familiar with the idea of an array, which is represented in memory using sequential mapping. It has a fixed size. The fundamental drawback of the array idea is that inserting or removing components from a specific point in the array is a time-consuming process.

Key points of Linked List in Data Structure

• We should use Linked List when the number of data elements is unknown before execution.
• The data from the linked list is accessed using an start pointer.
• Linked list stores data in the form of nodes. And linked list allocates memory at runtime to create nodes.
• Because memory allocation and deallocation are done at runtime, the speed is lower.

Linked List Representation in Data Structure

If we use a particular size array to represent the data item, yet we may unable to fill the entire array during runtime. There will be wastage or storage in this instance.

Inserting components at certain locations may need a lot of array shifting.

Linked lists can solve many of the difficulties that arrays have. The element can be placed at any point in the linked list. However, in order to create such an element, we must link the element to the one before it.

The three elements that make up a linked list are as follows:

1. item– An element is a type of data that may be stored in each link in a linked list.
2. link–  next that points to the next link.

We use a struct to wrap both the data item and the next node reference:

 struct node {
       int item;
       struct node * link;
 };

Linked List Program in C

The program below is for adding a node to an existing list. For this reason, we designed the insertItem function.

The number of nodes in the list is read by the main function. The list elements are shown using the displayList function.

#include <stdio.h>
#include <stdlib.h>
struct node {
   int item;
   struct node * link;
};
void displayList(struct node * start) {
  struct node * temp;
  temp = start;
  printf("The item values in the list are\n");
  if (start != NULL) {
    do {
      printf("%d\t", temp -> item);
      temp = temp -> link;
    } while (temp != start);
  } else
    printf("The list is empty\n");
}
struct node* insertItem(struct node * start, int data) {
  struct node * temp;
  if (start == NULL) {
    start = (struct node * ) malloc(sizeof(struct node));
    if (start == NULL) {
      printf("Error\n");
      exit(0);
    }
    start -> item = data;
    start -> link = start;
  } else {
    temp = start;
    while (temp -> link != start)
      temp = temp -> link;
    temp -> link = (struct node * ) malloc(sizeof(struct node));
    if (temp -> link == NULL) {
      printf("Error\n");
      exit(0);
    }
    temp = temp -> link;
    temp -> item = data;
    temp -> link = start;
  }
  return (start);
}
int main() {
  int numberOfNodes;
  int data;
  struct node * start = NULL;
  printf("Enter the number of nodes to be created \n");
  scanf("%d", & numberOfNodes);
  while (numberOfNodes > 0) {
    printf("Enter the item value for node\n");
    scanf("%d", & data);
    start = insertItem(start, data);
    numberOfNodes--;
  }
  printf("The list is\n");
  displayList(start);
  return 0;
}

Output:
Enter the number of nodes to be created 
3
Enter the item value for node
10
Enter the item value for node
20
Enter the item value for node
30
The list is
The item values in the list are
10      20      30

Types of Linked List in Data Structure

The many forms of linked lists are shown below.

• Simple Linked List
• Doubly Linked List
• Circular Linked List

Basic Operations of Linked List in Data Structure

The fundamental operations enabled by a list are as follows.

• Insertion : For adding an data at the beginning.
• Deletion : For removing an data at the beginning.
• Show : Shows the list items.
• Search : Search specified key element from list.
• Delete : Delete the specified key element.