Introduction to a Linked List

Linked List Data Structure

 A linked list is a linear data structure.
It is a dynamic data structure
          A node contains two fields i.e. data stored at that particular address
and the pointer which contains the address of the next node in the memory.
      The
     last node of the list contains a pointer to the null


Why use a
linked list over an array?

So far, we have been using the array data structure
to organize groups of elements stored individually in memory. However, arrays
come with certain advantages and limitations that should be understood before
selecting a data structure for a program.

Arrays have the following
limitations:


 
The
     array size must be defined in advance, before using it in the program.
 
Expanding
     an array’s size is time-consuming and nearly impossible to do at runtime.
 
All
     elements in an array must be stored contiguously in memory. Inserting a
     new element requires shifting all subsequent elements.


A linked list is a data structure that can overcome
these limitations. Linked lists offer several advantages:


 
Memory
     is allocated dynamically for each node. Nodes in a linked list are stored
     non-contiguously and are linked with pointers.
 
There
     is no need to define the size of the list upfront; it can grow or shrink
     as required by the program, limited only by available memory.


 

Node Creation using C programming

struct node   

{  

    int data;   

    struct node *next;  

};  

struct node *head, *ptr;   

ptr = (struct node *)malloc(sizeof(struct node *));  

Here you need to use the malloc function to allocate memory
for the nodes dynamically.

Essential
Operation on Linked Lists

·        
Traversing: To
traverse all nodes one by one.

·        
Insertion: To
insert new nodes at specific positions.

·        
Deletion: To
delete nodes from specific positions.

·        
Searching: To
search for an element from the linked list.

What Are
the Types of Linked Lists?



 

Applications of Linked List:


 
Dynamic memory allocation
 
Polynomial implementation for mathematical
     operations
 
Circular linked list is used to implement OS
 
Application functions that require round robin
     execution of tasks.
 
Doubly linked list
     is used in the implementation of forward and backward buttons
 
Prevent collision in a hash map
 
Used to represent various states of a game
 
UNDO or REDO function