Linked list

Definition

A linked list is a linear collection of data elements, referred to as nodes, where each node points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its simplest form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence.

Overview

The principal benefit of a linked list over a conventional array is that the list elements can be easily inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk, while restructuring an array at run-time is a much more expensive operation. Linked lists allow insertion and removal of nodes at any point in the list, and allow doing so with a constant number of operations by keeping the link previous to the link being added or removed in memory during list traversal.

Types of Linked Lists

There are three common types of Linked Lists:

Singly Linked List

A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail).

Doubly Linked List

A doubly linked list is a type of linked list in which each node contains a reference to the next node as well as the previous node in the sequence. This allows more flexibility in navigating the list as you can easily navigate backwards.

Circular Linked List

A circular linked list is a type of linked list in which the last node points back to the first node (head), making the chain of nodes form a circle.

Operations on Linked List

There are various operations that can be performed on a linked list such as:

Insertion

The node can be added in three ways: 1. At the front of the linked list. 2. After a given node. 3. At the end of the linked list.

Deletion

The node can be deleted in three ways: 1. Delete the first node. 2. Delete the last node. 3. Delete a node given the key.

Traversal

Traversing a linked list simply means to visit each node in the list. This can be done for various purposes such as finding a node in the list, printing the contents of the list, etc.

Applications of Linked Lists

Linked lists are used in many different types of applications. Some of the main uses of linked lists are: 1. Implementation of stacks and queues. 2. Implementation of graphs: Adjacency list representation of graphs is most popular which is uses linked list. 3. Dynamic memory allocation: We use linked list of free blocks. 4. Performing arithmetic operations on long integers. 5. Manipulation of polynomials by storing coefficients of different powers of variables in different nodes. 6. Representing sparse matrices.

Advantages and Disadvantages

Like any other data structure, linked lists have their advantages and disadvantages.

Advantages

1. Dynamic Size: The size of linked lists is not fixed and can grow and shrink during runtime by allocating and deallocating memory. Therefore, it provides flexibility and saves memory. 2. Ease of insertion/deletion: Insertion and deletion of nodes are really easier as compared to array.

Disadvantages

1. Random access is not allowed: We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists. 2. Extra memory space for a pointer is required with each element of the list.