What is the time complexity to search an element in a singly linked list?

The concept has been explained above by Anders for the 8th element from the beginning.

For the 8th element from the end of the list we can use two pointers. Both of them start from the beginning of the list and then we move one of the two by following 7 nodes so that the two pointers have a difference of 8 nodes (including the nodes where they are pointing to).

From that point and on you iterate so that in every step we move each pointer by one position; first we are moving the pointer that is further ahead of the two. When we can not move that pointer further (say because the next pointer is null), then we stop. At that point, the other pointer is pointing to the 8th element of the list counting from the end.

So, total complexity is the number of assignments that we have performed to the pointers by following the `next' links of the list which is $n + (n-8) = 2n - 8$, which is $O(n)$.

Side note: It is assumed that you have a proper linked list; i.e. not a cycle, but I guess you consider this as a given.

Also note that if you had a doubly-linked list and you also had a pointer for the last node of the list, then you could start from there and start counting backwards. In that case, finding the 8th element from the end of the list, the complexity would be $O(1)$.

The fact is that, unlike an array, we don’t need to shift the elements of a singly-linked list while doing an insertion. Therefore, the insertion time complexity of a singly-linked list is O(1).

Imagine that you have a Python list filled with integer numbers...

my_list = [9, 8, 4, 5, 6]

... and you want to insert the number 3 right after the element 8.

my_list.insert(2, 3)

The printed result will be:

[9, 8, 3, 4, 5, 6]

When you do an insertion to my_list, the other elements after the element 3 are all shifted towards the right, so their indexes are changed. As a result, the time complexity to insert an element at a given index is O(n).

However, in singly-linked lists, there are no array elements, but chained nodes and node values.

Image source: LeetCode

As the above image shows, the prev node holds the reference of the next node. As @πάντα ῥεῖ stated, "function signatures already take the predecessor node as argument". You can find the previous node in O(n) time, but while inserting a new node, you just need to change the addresses of connected nodes and that is O(1) time complexity.

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

Let’s simplified the code

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.

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.

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.

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

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!

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

    struct Node* temp = new Node;

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

    struct Node* slow = start;

    struct Node* fast = start -> next;

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

    struct Node* start = head;

    struct Node* last = NULL;

        Node* mid = middle(start, last);

        if (mid -> data == value)

        else if (mid -> data < value)

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

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

        printf("Value not present\n");

    static Node push(Node head, int data)

        Node newNode = new Node(data);

    static Node middleNode(Node start, Node last) 

    static Node binarySearch(Node head, int value) 

            Node mid = middleNode(start, last);

            else if (mid.data > value) 

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

    public static void main(String[] args) 

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

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

            System.out.println("Present");

    def __init__(self, data): 

def binarySearch(head,value):

        mid = middle(start, last)

        if (mid . data == value):

        elif (mid . data < value):

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

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)

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

    print("Value not present\n")

    static Node push(Node head, int data)

        Node newNode = new Node(data);

    static Node middleNode(Node start, Node last) 

    static Node binarySearch(Node head, int value) 

            Node mid = middleNode(start, last);

            else if (mid.data > value) 

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

    public static void Main(String []args) 

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

            Console.WriteLine("Value not present");

            Console.WriteLine("Present");

function push(head, data)

    var newNode = new Node(data);

function middleNode(start, last) 

function binarySearch(head, value) 

        var mid = middleNode(start, last);

        else if (mid.data > value) 

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

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

    document.write("Value not present");

    document.write("Present");

Time Complexity: O(N) 
Auxiliary Space: O(1)
 


Article Tags :

Practice Tags :