What is the time complexity of searching an element in a linked list

A linked list is a sequential data structure where data is stored in a sequential manner just like an array but what makes linked list more efficient is the way it stores data so let’s see the implementation of linked list using java.

Why linked list but not an array?
Well the simplest answer for this is memory allocation. We know that the size of an array has to be known beforehand so that restrict the further expansion of list to accommodate more elements. Now if you try out with dynamic memory allocation to an array to increase it’s size than in that case what happens is that first an empty block of memory gets allocated than all the elements from previous array gets copied to new array sequentially and this happens every time you try to expand your array size. Well this is certainly a costly operation so data structure that suit this kind of situation where the size of element is not known beforehand is linked list.

When not to use linked list?
When you have to perform more search operation than that of insert or delete operation than it’s best to go ahead with an array list but in reverse case it’s always better to go ahead with linked list. One more point is that the traditional indexed for loop operation for linked list traversal is very slow as in order to retrieve any element the search has to start form the beginning unlike in an array where indexed searching can be done so it’s always good to use iterator for traversing linked list.

Operation performed on linked list
All the operation that can be performed on an array can be performed on a linked list also but there are few scenarios where array list is better than linked list like searching, value modification whereas in few scenarios linked list perform better like insertion in between including beginning and end of the list, value deletion. In terms of time complexity searching in both of them takes O[n] if index of element is not known whereas if it’s known than it’s just O[1] for array list whereas O[n] for linked list. In case of element deletion the time complexity for an array list is O[n] whereas for linked list it’s just O[1].

What are those O[n] or O[1]?
Well those are as Asymptotic Notations which helps to analyse the algorithm runtime complexity where Big O is used to denote the worst case time complexity which means how much time your algorithm will take to run in the worst case scenarios. About worst case scenarios so for that you can think like you are searching an element in an array of size 10 and the element is at the index 9 that is the last element of an array so that will be called as worst case scenario, now if the element is at 1st position itself than that will be called as best case scenario where this type of scenario is denoted by Big-Omega. For each algorithm there will be it’s best case and worst case scenarios but what matters most of the time is worst case scenario so least the value for this the more optimum your solution is.

Implementation of linked list in java

public class LinkedList {

private Node startNode = null;

private Node endNode = null;
private int nodeCounter; //A node for the linked list.

private class Node {

private int value;
private Node next;

Node[int value] {

this.value = value;
this.next = null; } }

private Node createNode[int value] {

nodeCounter++;
return new Node[value]; }

private void insertNodeAtEnd[int value] {

if [startNode == null] {
startNode = createNode[value];
endNode = startNode;
} else { Node node = createNode[value];

endNode.next = node;

endNode = node; } }

private void insertNodeAtBeginning[int value] {

Node node = createNode[value];

node.next = startNode;

startNode = node; }

private void insertAtMid[int insertAfter, int newValue] {

Node node = startNode;
while [node != null] {
if [node.value == insertAfter] { Node newNode = createNode[newValue];

newNode.next = node.next;

node.next = newNode;
break; }

node = node.next;

} }

private void deleteStartingNode[] {

if [startNode != null] {
nodeCounter--;
startNode = startNode.next; } }

private void deleteAtEnd[] {

if [startNode == null] {

return; }

if [startNode == endNode] {

nodeCounter--;
startNode = endNode = null;
return; }

Node node = startNode;

while [node.next.next != null] {
node = node.next; }

node.next = null;

endNode = node;
nodeCounter--; }

private void displayNode[] {

Node node = startNode;
while [node != null] {
System.out.println["-->"+node.value];
node = node.next; } }

private void deleteParticularNode[int deleteValue] {

if [startNode == null] {
return; }

if [startNode == endNode] {

if [startNode.value == deleteValue] {
startNode = endNode = null;
nodeCounter--;
} else {
System.out.print["Value not found"]; }

return;

}

if [startNode.value == deleteValue] {

deleteStartingNode[];

return;

}

Node node = startNode;

while [node.next != null] {
if [node.next.value == deleteValue] {
node.next = node.next.next;
nodeCounter--;
break; }

node = node.next;

} }

public static void main[String args[]] {

LinkedList linkedList = new LinkedList[]; linkedList.insertNodeAtEnd[10]; linkedList.insertNodeAtEnd[20]; linkedList.insertNodeAtEnd[30]; linkedList.insertNodeAtEnd[40]; linkedList.insertNodeAtEnd[45]; linkedList.insertNodeAtEnd[50]; linkedList.insertNodeAtEnd[55]; linkedList.insertNodeAtBeginning[1]; linkedList.insertNodeAtBeginning[5]; linkedList.insertAtMid[40,45]; linkedList.displayNode[];

System.out.print["Total number of node:"+linkedList.nodeCounter];

}

Let’s simplified the code

//A node for the linked list.
private class Node {
private int value;
private Node next;

Node[int value] {

this.value = value;
this.next = null; }

}

Node will be treated as user defined data type where the type of data that it can store is what you defined inside Node class. This node class should also have self referential object so that it can connect with other nodes.

private void insertNodeAtEnd[int value] {
if [startNode == null] {
startNode = createNode[value];
endNode = startNode;
} else { Node node = createNode[value];

endNode.next = node;

endNode = node; }

}

Here startNode and endNode is instance of class Node where startNode always point to the starting of the list and endNode points to the end of the list. Initially startNode will be null so create a node and that node will be treated as startNode from the next time onward attach the node at the end than mark the newly attached node as endNode.

private void insertAtMid[int insertAfter, int newValue] {
Node node = startNode;
while [node != null] {
if [node.value == insertAfter] { Node newNode = createNode[newValue];

newNode.next = node.next;
node.next = newNode;

break; }

node = node.next;

}

To insert the node in between first create a node and than attach the newly created node with the existing node.next than assign your node to node.next this will add the node in between.

private void deleteStartingNode[] {
if [startNode != null] {
nodeCounter--;
startNode = startNode.next; }

}

To delete the node from the starting of the list just move the startNode one node ahead by startNode.next that’s it.

private void deleteAtEnd[] {

if [startNode == null] {

return; }

if [startNode == endNode] {

nodeCounter--;
startNode = endNode = null;
return; }

Node node = startNode;

while [node.next.next != null] {
node = node.next; }

node.next = null;

endNode = node;
nodeCounter--;
}

To delete the node form the end of the list first check whether the startNode is null or not if it’s null than just exit if not than check if startNode is equal to endNode if they are equal than just mark both to null and return. In case both the above conditions are not matched than check for one node before the last node and make that node.next to null as well as make it as your endNode.

Linked list is widely used in most the data structures so it’s quite important to know how to perform operations on linked list that’s it for linked list keep experimenting and happy coding!

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.

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.

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;

{

// 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;

{

// 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;

{

// 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

// 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;

{

// 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>

Output: Present

Time Complexity: O[N]
Auxiliary Space: O[1]

Article Tags :

Divide and Conquer

Linked List

Searching

Binary Search

Practice Tags :

Linked List

Searching

Divide and Conquer

Binary Search

Read Full Article

Hi there! This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them. Over the last few years, I've interviewed at several Silicon Valley startups, and also some bigger companies, like Google, Facebook, Yahoo, LinkedIn, and Uber, and each time that I prepared for an interview, I thought to myself "Why hasn't someone created a nice Big-O cheat sheet?". So, to save all of you fine folks a ton of time, I went ahead and created one. Enjoy! - Eric

Check out El Grapho, a graph data visualization library that supports millions of nodes and edges