What is the time complexity to traverse the elements in the linked list

Introduction to Singly Linked List

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.

Table of Contents Show

Introduction to Singly Linked List
Binary Search on 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.

The main difference from an array is:

Elements are not stored in contiguous memory locations.
Size of Linked List need not be known in advance. It can increase at runtime depending on number of elements dynamically without any overhead.

In Singly Linked List, only the pointer to the first node is stored. The other nodes are accessed one by one.

To get the address of ith node, we need to traverse all nodes before it because the address of ith node is stored with i-1th node and so on.

Binary Search on Singly Linked List

Given a singly linked list and a key, find key using binary search approach.
To perform a Binary search based on Divide and Conquer Algorithm, determination of the middle element is important. Binary Search is usually fast and efficient for arrays because accessing the middle index between two given indices is easy and fast(Time Complexity O(1)). But memory allocation for the singly linked list is dynamic and non-contiguous, which makes finding the middle element difficult. One approach could be of using skip list, one could be traversing the linked list using one pointer.
Prerequisite: Finding middle of a linked list.
Note: The approach and implementation provided below are to show how Binary Search can be implemented on a linked list. The implementation takes O(n) time.
Approach :

Here, start node(set to Head of list), and the last node(set to NULL initially) are given.
Middle is calculated using two pointers approach.
If middle’s data matches the required value of search, return it.
Else if middle’s data < value, move to upper half(setting start to middle’s next).
Else go to lower half(setting last to middle).
The condition to come out is, either element found or entire list is traversed. When entire list is traversed, last points to start i.e. last -> next == start.

In main function, function InsertAtHead inserts value at the beginning of linked list. Inserting such values(for sake of simplicity) so that the list created is sorted.
Examples :

Input : Enter value to search : 7 Output : Found Input : Enter value to search : 12 Output : Not Found

C++

// CPP code to implement binary search
// on Singly Linked List
#include<stdio.h>
#include<stdlib.h>

struct Node
{

int data;

struct Node* next;
};

Node *newNode(int x)
{

struct Node* temp = new Node;

temp->data = x;

temp->next = NULL;

return temp;
}
// function to find out middle element

struct Node* middle(Node* start, Node* last)
{

if (start == NULL)

return NULL;

struct Node* slow = start;

struct Node* fast = start -> next;

while (fast != last)

{

fast = fast -> next;

if (fast != last)

{

slow = slow -> next;

fast = fast -> next;

}

}

return slow;
}
// Function for implementing the Binary
// Search on linked list

struct Node* binarySearch(Node *head, int value)
{

struct Node* start = head;

struct Node* last = NULL;

do

{

// Find middle

Node* mid = middle(start, last);

// If middle is empty

if (mid == NULL)

return NULL;

// If value is present at middle

if (mid -> data == value)

return mid;

// If value is more than mid

else if (mid -> data < value)

start = mid -> next;

// If the value is less than mid.

else

last = mid;

} while (last == NULL ||

last != start);

// value not present

return NULL;
}
// Driver Code

int main()
{

Node *head = newNode(1);

head->next = newNode(4);

head->next->next = newNode(7);

head->next->next->next = newNode(8);

head->next->next->next->next = newNode(9);

head->next->next->next->next->next = newNode(10);

int value = 7;

if (binarySearch(head, value) == NULL)

printf("Value not present\n");

else

printf("Present");

return 0;
}

Java

// Java code to implement binary search 
// on Singly Linked List 
// Node Class

class Node
{

int data;

Node next;

// Constructor to create a new node

Node(int d)

{

data = d;

next = null;

}
}

class BinarySearch
{

// function to insert a node at the beginning

// of the Singaly Linked List

static Node push(Node head, int data)

{

Node newNode = new Node(data);

newNode.next = head;

head = newNode;

return head;

}

// Function to find middle element

// using Fast and Slow pointers

static Node middleNode(Node start, Node last)

{

if (start == null)

return null;

Node slow = start;

Node fast = start.next;

while (fast != last)

{

fast = fast.next;

if (fast != last)

{

slow = slow.next;

fast = fast.next;

}

}

return slow;

}

// function to insert a node at the beginning

// of the Singly Linked List

static Node binarySearch(Node head, int value)

{

Node start = head;

Node last = null;

do

{

// Find Middle

Node mid = middleNode(start, last);

// If middle is empty

if (mid == null)

return null;

// If value is present at middle

if (mid.data == value)

return mid;

// If value is less than mid

else if (mid.data > value)

{

start = mid.next;

}

// If the value is more than mid.

else

last = mid;

} while (last == null || last != start);

// value not present

return null;

}

// Driver Code

public static void main(String[] args)

{

Node head = null;

// Using push() function to

// convert singly linked list

// 10 -> 9 -> 8 -> 7 -> 4 -> 1

head = push(head, 1);

head = push(head, 4);

head = push(head, 7);

head = push(head, 8);

head = push(head, 9);

head = push(head, 10);

int value = 7;

if (binarySearch(head, value) == null)

{

System.out.println("Value not present");

}

else

{

System.out.println("Present");

}

}
}
// This code is contributed by Vivekkumar Singh

Python

# Python code to implement binary search 
# on Singly Linked List 
# Link list node 

class Node:

def __init__(self, data):

self.data = data

self.next = None

self.prev = None

def newNode(x):

temp = Node(0)

temp.data = x

temp.next = None

return temp
# function to find out middle element

def middle(start, last):

if (start == None):

return None

slow = start

fast = start . next

while (fast != last):

fast = fast . next

if (fast != last):

slow = slow . next

fast = fast . next

return slow
# Function for implementing the Binary
# Search on linked list

def binarySearch(head,value):

start = head

last = None

while True :

# Find middle

mid = middle(start, last)

# If middle is empty

if (mid == None):

return None

# If value is present at middle

if (mid . data == value):

return mid

# If value is more than mid

elif (mid . data < value):

start = mid . next

# If the value is less than mid.

else:

last = mid

if not (last == None or last != start):

break

# value not present

return None
# Driver Code

head = newNode(1)

head.next = newNode(4)

head.next.next = newNode(7)

head.next.next.next = newNode(8)

head.next.next.next.next = newNode(9)

head.next.next.next.next.next = newNode(10)

value = 7

if (binarySearch(head, value) == None):

print("Value not present\n")

else:

print("Present")

# This code is contributed by Arnab Kundu

// C# code to implement binary search 
// on Singly Linked List 

using System;
// Node Class

public class Node
{

public int data;

public Node next;

// Constructor to create a new node

public Node(int d)

{

data = d;

next = null;

}
}

class BinarySearch
{

// function to insert a node at the beginning

// of the Singaly Linked List

static Node push(Node head, int data)

{

Node newNode = new Node(data);

newNode.next = head;

head = newNode;

return head;

}

// Function to find middle element

// using Fast and Slow pointers

static Node middleNode(Node start, Node last)

{

if (start == null)

return null;

Node slow = start;

Node fast = start.next;

while (fast != last)

{

fast = fast.next;

if (fast != last)

{

slow = slow.next;

fast = fast.next;

}

}

return slow;

}

// function to insert a node at the beginning

// of the Singly Linked List

static Node binarySearch(Node head, int value)

{

Node start = head;

Node last = null;

do

{

// Find Middle

Node mid = middleNode(start, last);

// If middle is empty

if (mid == null)

return null;

// If value is present at middle

if (mid.data == value)

return mid;

// If value is less than mid

else if (mid.data > value)

{

start = mid.next;

}

// If the value is more than mid.

else

last = mid;

} while (last == null || last != start);

// value not present

return null;

}

// Driver Code

public static void Main(String []args)

{

Node head = null;

// Using push() function to

// convert singly linked list

// 10 -> 9 -> 8 -> 7 -> 4 -> 1

head = push(head, 1);

head = push(head, 4);

head = push(head, 7);

head = push(head, 8);

head = push(head, 9);

head = push(head, 10);

int value = 7;

if (binarySearch(head, value) == null)

{

Console.WriteLine("Value not present");

}

else

{

Console.WriteLine("Present");

}

}
}
// This code is contributed by Arnab Kundu

Javascript

<script>
// JavaScript code to implement binary search 
// on Singly Linked List 
// Node Class
class Node
{

constructor(data)

{

this.data = data;

this.next = null;

}
}
// function to insert a node at the beginning
// of the Singaly Linked List

function push(head, data)
{

var newNode = new Node(data);

newNode.next = head;

head = newNode;

return head;
}
// Function to find middle element
// using Fast and Slow pointers

function middleNode(start, last)
{

if (start == null)

return null;

var slow = start;

var fast = start.next;

while (fast != last)

{

fast = fast.next;

if (fast != last)

{

slow = slow.next;

fast = fast.next;

}

}

return slow;
}
// function to insert a node at the beginning
// of the Singly Linked List

function binarySearch(head, value)
{

var start = head;

var last = null;

do

{

// Find Middle

var mid = middleNode(start, last);

// If middle is empty

if (mid == null)

return null;

// If value is present at middle

if (mid.data == value)

return mid;

// If value is less than mid

else if (mid.data > value)

{

start = mid.next;

}

// If the value is more than mid.

else

last = mid;

} while (last == null || last != start);

// value not present

return null;
}
// Driver Code

var head = null;
// Using push() function to
// convert singly linked list
// 10 -> 9 -> 8 -> 7 -> 4 -> 1
head = push(head, 1);
head = push(head, 4);
head = push(head, 7);
head = push(head, 8);
head = push(head, 9);
head = push(head, 10);

var value = 7;

if (binarySearch(head, value) == null)
{

document.write("Value not present");
} 
else
{

document.write("Present");
}
</script>