Dynamic Implementation

The concept of a linked list in data structures addresses the limitations of fixed-size arrays by providing a dynamic and flexible way to allocate memory. 

Introduction

In traditional programming, memory allocated for variables, like arrays, is fixed during compile time. For example, if an array A of size 100 is declared, it occupies memory for 100 elements, and this memory cannot be changed dynamically during program execution.

Linked List:

Linked List is a dynamic data structure, it is collection of special types of data structure called as nodes. Nodes are dynamically created during the run time as required, thus solving the problem of memory shortage or wastage. The node in the linked list generally consists of two parts: data part and address part. 

Data/Information: This part stores the actual value or information associated with the node.

Pointer/Address: This part contains the address of the next node in the sequence. This pointer links one node to the next, forming a chain-like structure.

In linked list the chain of nodes as shown above forms a linked list as shown below:

As shown in the figure above, each node in the linked list holds the address of the next node in the linked list. The address in the last node is NULL, as no other node exists after that. Every linked list maintains a separate pointer called HEAD, the head pointer holds the address of the first node in the linked list, so the first node is also called a head node. The address in the head node is essential to traverse the linked list.

In C programming, we can use structure to represent a node as given below:

ADVANTAGES AND DISADVANTAGES 

Linked list have many advantages and some of them are: 

1. Linked lists are dynamic data structures. That is, they can grow or shrink during the execution of a program. 
2. Efficient memory utilization: In linked list (or dynamic) representation, memory is not pre-allocated. Memory is allocated whenever it is required. And it is deallocated (or removed) when it is not needed.
3. Insertion and deletion are easier and more efficient. Linked list provides flexibility in inserting a data item at a specified position and deletion of a data item from the given position. 
4. Many complex applications can be easily carried out with a linked list. 

Linked list has following disadvantages 

• More memory: to store an integer number, a node with integer data and address field is allocated. That is, more memory space is needed. 
• Access to an arbitrary data item is a little bit cumbersome and also time consuming.