Linked List

Introduction

Linked List is a type of Dynamic Data Structure that can used to store data without declaring data length. Each element is called ‘Node’, and it contains two parts one part is called node, and second part is called pointer, this pointer points to the next node. It is better than array because first it is contiguous memory, and we have to declare the memory size and you cannot change the memory size.

Definition of Linked List

Linked List’s Node is made up of two parts:

Linked List has two-part Head which point to the first Node, and Tail which points to the last node.

Data: It contains the data.

Next: It has the pointer that referenced to the next node.

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

Types of Linked Lists

Singly Linked List: Every node points to the next node and the last node point to the null.
Doubly Linked List: Every node has two pointers, one pointer points to the previous node, and second pointer points to the next node.

Circular Linked List: In this, the last node does points to the next node but not to the null.

Time Complexity

In computer science world, time complexity is a very necessary which defines how much time a particular algorithm takes, sounds very small but the software and projects in big scale makes a big impact.

Every program takes time to execute and that is used to quantify this time, and by decreasing and result to good productivity

Linked List Complexity is O(1) while the complexity of array is O(n).

Different operations have different complexity and as you can see Linked list has less complexity.

Real-World Applications

Linked List is also used in real world applications like in operating system for memory management, Implementing in Data Structures like Stacks and Queues, use in file system.

Usage in Operating Systems

Memory management: OS use linked list to allocate free memory and when program request from memory it allocates it from the free space in memory and when he does not need any more it deallocates the memory again.

Implementation in Data Structures like Stacks and Queues

Stack:
One segment follows the Last-In-First-Out (LIFO) principle. Linked lists can using stacks because elements can be added or deleted at a constant interval, initially with O(1).
Example: A backtracking algorithm uses stacks to track the status of a calculation, and often uses a linked list.
Queue:
One segment follows the Last-In-First-Out (LIFO) principle. Linked lists can using stacks because elements can be added or deleted at a constant interval, initially with O(1).
Example: A backtracking algorithm uses stacks to track the status of a calculation, and often uses a linked list