Linked List Data Structure

Linked list is a linear data structure that contains sequence of elements such that each element links to its next element in the sequence and each element in a linked list is called as "Node".

Linked List is a very commonly used linear data structure which consists of set of nodes in a sequence.

Each node has two fields known as data and link. Data field stores actual data and link contains address of next node to point to the next node.

Linked Lists are used to create trees and graphs.

Linked List is a sequence of links which contains items and link contains a connection to another link. It is also the second most used data structure after array.

A linked list has the following Properties.

• Successive elements are connected by pointers
• The last element points to NULL
• Can grow or shrink in size during execution of a program
• Can be made just as long as required
• Does not waste memory space (but takes some extra memory for pointers) and allocates memory as list grows.

Types of Linked Lists

There are 3 different implementations of Linked List available, they are:

1. Singly Linked List
2. Doubly Linked List
3. Circular Singly Linked List
4. Circular Doubly Linked List

Let's know more about them and how they are different from each other.

Basic Operations on Linked Lists

Following are the basic operations supported by a list.

• Insertion − add an element at the beginning of the list.
• Deletion − delete an element at the beginning of the list.
• Display − displaying complete list.
• Search − search an element using given key.
• Delete − delete an element using given key.

Key Terminology in Linked Lists

Node

A node is the fundamental unit of a linked list. Each node consists of:

• Data (stores information).
• Pointer (points to the next node).

Example:

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

Head (First Node)

The head is a pointer that stores the address of the first node in the linked list. If the list is empty, head = NULL.

Example:

Head → [10 | *] → [20 | *] → [30 | NULL]

Here, the head points to 10, which is the first element in the linked list.

Tail (Last Node)

The tail is the last node in the linked list, which has a NULL pointer (i.e., it does not point to any next node).

Example:

[10 | *] → [20 | *] → [30 | NULL]  (Tail is 30)

Pointer (Link)

The pointer in each node stores the memory address of the next node in the list.

Example:

Node1.next = &Node2;  // Node1 points to Node2

Null Reference

If a node’s pointer is NULL, it means it is the last node in the list.

Example:

Head → [10 | *] → [20 | NULL]  (Last node 20 has NULL pointer)

Advantages of Linked List

Dynamic Size: A linked list does not require a predefined size. It can grow or shrink at runtime depending on the requirements, which helps in better memory utilization.

Efficient Insertions and Deletions: Inserting or deleting elements in a linked list is more efficient compared to arrays, especially when the operations are performed at the beginning or in the middle of the list. There is no need to shift elements after insertion or deletion.

No Wasted Memory: Memory is allocated only when needed for each node. Unlike arrays, which may reserve unused space, linked lists make better use of memory by allocating it dynamically.

Implementation of Advanced Data Structures: Linked lists serve as the foundation for various other data structures such as stacks, queues, graphs, hash tables, and trees.

Insertion in Sorted Order: It is easier to insert elements into a sorted linked list at the correct position without shifting other elements, unlike arrays.

Disadvantages of Linked List

More Memory Usage: Each node in a linked list requires additional memory for the pointer or reference to the next node. This makes linked lists less memory efficient than arrays.

Sequential Access Only: Linked lists do not allow direct access to elements. To reach a particular node, traversal from the head node is required, which increases access time.

Complex Implementation: Writing code for insertion, deletion, and traversal in linked lists is more complex compared to arrays. Proper handling of pointers is necessary to avoid errors like memory leaks.

Reverse Traversal is Difficult: In singly linked lists, moving backwards is not straightforward. To enable backward traversal, a doubly linked list must be used.

Extra CPU Time: Accessing data in linked lists takes more processing time because the elements are stored at non-contiguous memory locations. This results in slower access and more cache misses compared to arrays.

Applications of Linked Lists

Dynamic Memory Allocation

Linked lists are ideal for applications that require memory to be allocated or deallocated during runtime, as they can grow or shrink dynamically.

Implementing Other Data Structures

Linked lists are commonly used to implement stacks, queues, graphs (through adjacency lists), hash tables (using chaining), and trees.

Real-Time Application Examples

• In music or video players, playlists are maintained using linked lists to support next and previous navigation.
• In browsers, the history of visited pages is maintained using a doubly linked list to support backward and forward navigation.
• In word processors and graphic editors, undo and redo operations are supported using linked lists.

Operating Systems

• Process scheduling in operating systems, especially round-robin scheduling, uses circular linked lists.
• Memory management also uses linked lists to track free and used memory blocks.

Image Viewing Applications

Allows moving forward and backward through a sequence of images.

Polynomial Arithmetic

Polynomials can be stored as linked lists where each node represents a term with a coefficient and exponent, making addition and multiplication efficient.

Sparse Matrices

Sparse matrices, which contain mostly zeros, use linked lists to store only the non-zero elements, saving memory.

Navigation Systems

Routes and paths that require frequent updates (insertion or removal of locations) can be implemented using linked lists.

File System Management

File allocation systems like the FAT (File Allocation Table) use linked list structures to manage file block chains.

Simulation Models

Linked lists are used in simulations that involve a dynamic number of events or objects, such as queueing systems or packet routing in networks.

Comparison between Array and Linked List

Here is a detailed comparison between Array and Linked List.

Memory Allocation

Array: Uses static memory allocation. The size must be declared in advance, and it cannot grow or shrink during runtime.

Linked List: Uses dynamic memory allocation. Nodes are created as needed, allowing the list to grow or shrink at runtime.

Access Time

Array: Supports random access. Any element can be accessed directly using the index in constant time O(1).

Linked List: Supports sequential access only. To access an element, you must traverse from the head node, which takes linear time O(n).

Insertion and Deletion

Array: Insertion or deletion (especially in the middle) is expensive and requires shifting elements. Worst-case time is O(n).

Linked List: Insertion and deletion are efficient, especially at the beginning or in the middle. Time complexity is O(1) if the pointer to the node is known.

Memory Usage

Array: Requires contiguous memory locations. If large memory blocks are unavailable, allocation may fail.

Linked List: Does not require contiguous memory. Each node is allocated separately and can be scattered in memory.

Wasted Space

Array: May have unused space if the allocated size is larger than needed.

Linked List: No pre-allocated space, but extra memory is used for storing pointers (next and optionally previous).

Ease of Implementation

Array: Easier to implement and use with indexing.

Linked List: More complex to implement due to pointer management and dynamic memory handling.

Performance in Searching

Array: Binary search can be used if the array is sorted, resulting in O(log n) time.

Linked List: Only linear search is possible, even in a sorted list, resulting in O(n) time.

Use Cases

Array: Best when the number of elements is fixed and frequent direct access is needed (e.g., storing scores, tables).

Linked List: Best when frequent insertion/deletion is required, and the number of elements is not known in advance (e.g., dynamic data, stacks, queues).