Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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.
Singly linked list
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.
Advantages of Linked List over arrays
- Dynamic size
- Ease of insertion and deletion in constant time
Drawbacks of Linked List:
- 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.
- 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:
- data
- 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.*;
class LinkedList<E> implements java.io.Serializable
{
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
public LinkedList() {}
// 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;
}
}
private void LinkFirst(E e)
{
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;
}
private void LinkLast(E e)
{
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;
}
E unlinkFirst(Node<E> f)
{
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;
}
E unlinkLast(Node<E> l)
{
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;
}
E unlink(Node<E> n)
{
final E element = n.item;
final Node<E> before = n.prev;
final Node<E> next = n.next;
if( before == null )
return unlinkFirst(n);
else if(next == null)
return unlinkLast(n);
else
{
n.item = null;
n.next = null;
n.prev = null;
before.next = next;
next.prev = before;
-- size;
}
return element;
}
void add(E e)
{
LinkLast(e);
}
void addAtEnd(E e)
{
LinkLast(e);
}
void addAtFront(E e)
{
LinkFirst(e);
}
}
public class Test_LinkedList
{
public static void main()
{
LinkedList<Integer> ll = new LinkedList<Integer>();
ll.add(10);
ll.add(9);
ll.add(10);
ll.add(100);
Node<Integer> nn = ll.node(3);
ll.unlink(nn);
ll.add(11);
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.
