Reading time: 35 minutes | Coding time: 20 minutes

Singly Linked List is a variant of Linked List which allows only forward traversal of linked lists. This is a simple form yet it is effective for several problems such as Big Integer calculations. We will look into how various operations are performed and the advantages and disadvantages along with a sample code.

### Introduction

List is a collection of similar type of elements. There are two ways of maintaining a list in memory. The first way is to store the elements of the list in an array,but arrays have some restrictions and disadvantages. The second way of maintaining a list in memory is through linked list. Let us study what a linked list is and after that we will come to know how it overcomes the limitations of array.

In this article, we will explore the simplest form of Linked List which is known as Singly Linked List. There are several modifications of Linked List which finds use in various basic and advance applications. We will explore each one subsequently.

A singly linked list is made up of nodes where each node has two parts:

• The first part contains the actual data of the node
• The second part contains a link that points to the next node of the list that is the address of the next node. The beginning of the node marked by a special pointer named START. The pointer points to the fist node of the list but the link part of the last node has no next node to point to. 1. Dynamic size
2. Ease of insertion and deletion in constant time

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

Representation of Linked List in C:

A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then value of head is NULL.
Each node in a list consists of at least two parts:

1. data
2. pointer to the next node

In C, we can represent a node using structures. Below is an example of a linked list node with an integer data.
In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

### Implementations

Implementation of Linked List class with all operations:

• Java

### Java


import java.util.*;
{
private static class Node<E>
{
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next)
{
this.item = element;
this.prev = prev;
this.next = next;
}
}
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
// Creates an empty list
// Return Node at index "index" O(N) time
public Node<E> node( int index)
{
if(index < (size >> 1))
{
Node<E> x = first;
for(int i=0;i<index; ++i)
x = x.next;
return x;
}
else
{
Node<E> x = last;
for(int i=size-1; i>index; --i)
x = x.prev;
return x;
}
}
// Print all elements in the LinkedList
public void printList()
{
Node<E> x = first;
for(int i=0;i<size; ++i)
{
System.out.println(x.item);
x = x.next;
}
}
{
final Node<E> front = first;
final Node<E> newNode = new Node<>(null, e, front);
first = newNode;
if( front == null)
last = newNode;
else
front.prev = newNode;
++ size;
}
{
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if(l == null)
first = newNode;
else
l.next = newNode;
++ size;
}
// Inserts a node before a non null node succ
private void LinkBefore(E e, Node<E> succ)
{
Node<E> before = succ.prev;
Node<E> newNode = new Node<E>(before, e, succ);
succ.prev = newNode;
if(before == null)
{
first = newNode;
}
else
{
before.next = newNode;
}
++ size;
}
{
final Node<E> next = f.next;
first = next;
final E element = f.item;
f.item = null;
f.next = null;
if(next == null)
last = null;
else
next.prev = null;
-- size;
return element;
}
{
final E element = l.item;
final Node<E> newLast = l.prev;
l.prev = null;
l.item = null;
last = newLast;
if(newLast == null)
first = null;
else
newLast.next = null;
-- size;
return element;
}
{
final E element = n.item;
final Node<E> before = n.prev;
final Node<E> next = n.next;
if( before == null )
else if(next == null)
else
{
n.item = null;
n.next = null;
n.prev = null;
before.next = next;
next.prev = before;
-- size;
}
return element;
}
{
}
{
}
{
}
}
{
public static void main()
{
Node<Integer> nn = ll.node(3);
ll.printList();
}
}


### Complexity

Complexity of Insertion operation in a Linked List:

• Worst case time complexity: Θ(1)
• Average case time complexity: Θ(1)
• Best case time complexity: Θ(1)
• Space complexity: Θ(1)

Complexity of Deletion operation in a Linked List:

• Worst case time complexity: Θ(1)
• Average case time complexity: Θ(1)
• Best case time complexity: Θ(1)
• Space complexity: Θ(1)

Complexity of Search operation in a Linked List:

• Worst case time complexity: Θ(N)
• Average case time complexity: Θ(N)
• Best case time complexity: Θ(1)
• Space complexity: Θ(1)

### Applications

Real life applications of a Linked List is as follows:

• Linked Lists can also be used to represent Graphs as adjacent matrices which is a much space efficient representation than an array. Memory consumption with an array for a graph with N nodes is of the order of O(N^2) and with a linked list is of the order of O(N).
• Implementing Hash Tables :- Each Bucket of the hash table can itself be a linked list.
• Undo functionality in Photoshop or Microsoft Word uses Linked List
• Accessing next element in a Linked List takes less time compared to an Array. This is because Linked List takes the natural advantage of locality of reference and hence, works well with caches. #### Rahul Kumar

B. Tech (2019) in Computer Science at National Institute of Science and Technology (NIST), Berhampur