Singly Linked List

A linked list is a dynamic data structure comprised of nodes, each containing data and a pointer to the next node. Unlike arrays, linked lists don't require contiguous memory, making them ideal for dynamic resizing.

The initial node, known as the HEAD, serves as the starting point for traversal. Comparatively, while arrays have fixed sizes, linked lists allow real-time size modifications. Their non-contiguous memory allocation maximizes storage efficiency, especially when continuous memory isn't available. Notably, linked lists excel in insertion and deletion operations, executing them in constant time, contrasting with arrays that perform these tasks in linear time.

What is a Singly Linked List?

A Singly Linked List is a specialized case of a generic linked list. In a singly linked list, each node links to only the next node in the sequence, i.e. if we start traversing from the first node of the list, we can only move in one direction(pun intended).

The Node of the singly linked list, apart from the data, stores the address of only the next element, as shown below. The following is the JAVA representation of a node.

For a linked list we maintain a special pointer known s HEAD. This pointer stores the address of the first node of the list. Also, the last node can no longer have the next element. Hence we indicate the end of the linked list by assigning NULL to its next.

Operations on Singly Linked List

1. Insertion

Insertion in a singly linked list can be performed in the following ways,

• Insertion at the start Insertion of a new node at the start of a singly linked list is carried out in the following manner.
  • Make the new node point to HEAD.
  • Make the HEAD point to the new node.

Inserting a new node at the start is an O(1) operation.

• Insertion after some Node Insertion of a new node after some node in a singly linked list is carried out in the following manner,
  • Reach the desired node after which the new node is to be inserted.
  • Make the new node point to the next element of the current node.
  • Make the current node point to the new node. Inserting a new node after some node is an O(N) operation.

• Insertion at the end Insertion of a new node at the end of a singly linked list isperformed in te followin way,
  • Taverse the list from start and reach the last node.
  • Make the last node point to the new node.
  • Make the new node point to null, marking the end of the list. Inserting a new node at the end is an O(N) operation.

2. Deletion

Deletion in a singly linked list can be performed in the following ways,

• Deletion at the start
  The first node of the singly linked list can be deleted as follows,

  • Make the HEAD point to its next element.

Deleting the first node of a singly linked list is an O(1) operation.

• Deletion at the middle

The deletion after a specific node can be formed in the following way,

• Reach the desired node after which the node is to be deleted.
• Make the current node point to the next of next element.

Deleting a node after a specific node is an O(N) operation.

• Deletion at last

The deletion of the last node is performed in the following manner,

• Reach the second last node of th singly linke list.
• Make the second last node point null.

Deleting the last node is an O(N) operation.

3. Display

To display the entire singly linked list, we need to traverse it from first to last.

In contrast to arrays, linked list nodes cannot be accessed randomly. Hence to reach the n-th element, we are bound to traverse through all (n-1) elements.

Since the entire linked list is traversed, the operation costs us O(N) time complexity. The following JAVA snippet shows how the entire singly linked list can be displayed.

4. Search

To search an element in the singly linked list, we need to traverse the linked list right from the start.

At each node, we perform a lookup to determine if the target has been found, if yes, then we return the target node else we move to the next element.

In the worst case, we could end up visiting all the nodes in the list and hence searching an element in the singly linked list cost us O(N) operational time.

Can we do better?

Assume that the entire singly linked list is already sorted in ascending manner. Can we apply the binary search on Linked List and complete our searching operation in O(log N) time?

It turns out we can’t, even if the linked list is already sorted we cannot perform the binary search over it. One of the important things for the binary search to work on a collection is, any location of the collection must be randomly accessible in constant time. Arrays obey this property as we can access specifically any array element in constant time.

However, with Linked List such random access is prohibited. Any element of a singly linked list can only be accessed in a sequential manner making binary search completely ineffective.

Uses of Linked List

Some of the real-life applications of the linked list are as follows:

• Used to store single or bivariable polynomials.
• Act as a base for certain data structures like Queue, Stack, Graph.
• Strategy for file allocation schemes by Operating System.
• Keep track of free space in the secondary disk. All the free spaces can be linked together.
• Turn-based games can use a circular linked list to decide which player is about to be played. Once the player finishes its turn we move to the next player.
• To keep records of items such as music, videos, images, web pages, etc which link to one another and allows to traverse between them sequentially.