The Linked List: a Chain of Links

Types of Linked List

• Singly Linked List: Each node contains data and a reference to the next node. It only allows traversal in one direction.
• Doubly Linked List: Each node contains data, a reference to the next node, and a reference to the previous node. This structure allows traversal in both directions.
• Circular Linked List: In this type of linked list, the last node points back to the first node, creating a circular structure. It can be singly or doubly linked.

Applications of Linked Lists

Dynamic Memory Allocation

Linked lists are widely used in applications where dynamic memory allocation is crucial. Unlike arrays, which require predefined memory space, linked lists can efficiently manage memory at runtime. This makes them ideal for scenarios where the size of the data structure is not known in advance or varies significantly during execution.

Singly-Linked Lists Implementing Stacks and Queues

Stacks and queues are fundamental data structures used in various applications. Linked lists are an efficient way to implement both structures, overcoming the limitations of array-based implementations, such as fixed size.

• Stack: Using a singly linked list, a stack can be implemented where elements are pushed or popped from the head of the list.
• Queue: A queue can be implemented using a singly linked list where elements are enqueued at the tail and dequeued from the head.

Polynomial Manipulation

In mathematics and computer science, linked lists can represent polynomial expressions efficiently. Each node in the linked list can store the coefficient and exponent of a term in the polynomial. Operations such as addition and multiplication of polynomials become easier to implement using a linked list. Such lists must be kept sorted by exponent.

Adjacency List in Graphs

Graphs are represented using an adjacency list, where each node corresponds to a vertex, and its adjacent vertices are stored in a linked list. This structure is efficient in terms of both time and space, especially for sparse graphs.

Undo and Redo Operations in Text Editors and other Applications

A doubly linked list stores user actions (add, change, delete, etc.).

Text editors, graphic design tools, and many other software applications use doubly linked lists to implement undo and redo functionalities. Every action (such as typing a letter or deleting content) is stored in a node. The undo action moves to the previous node, while the redo action moves to the next.

Also, browsers store browser history in a doubly linked list, which enables moving forward and backward to already visited pages.

Singly Linked List in Hashing

In hashing, singly linked lists are employed to handle collisions using chaining. When two or more elements hash to the same index, a linked list is created at that index to store the colliding elements. This ensures efficient management of collisions and helps maintain the overall performance of the hash table.

Everyday Software Development and Systems

• File Allocation in Operating Systems: Operating systems use linked lists to manage file storage on disk. For example, the File Allocation Table (FAT) system uses a linked list to keep track of the blocks of a file, ensuring that the file can be stored across non-contiguous blocks on the disk.
• Job Scheduling: In certain job scheduling algorithms, a linked list is used to maintain a list of jobs to be executed in a specific order. Each job can be dynamically added or removed as required by the system.