Skip to main content

Search an element in circular singly linked list

The Search an Element in Circular Singly Linked List problem involves searching for a specific element in a circular singly linked list. A circular singly linked list is a data structure where each node points to the next node, and the last node points back to the first node, creating a loop. The problem is to determine whether a given element exists in the circular singly linked list or not.

Problem Statement

Given a circular singly linked list and a value to search for, the problem is to determine whether the given value exists in the linked list or not.

Example

Consider the circular singly linked list:

Linked List: 15 -> 5 -> 7 -> 4 -> 63 -> 11 -> 17

  • Searching for element 4: Node value 4 exists.
  • Searching for element 34: Node value 34 does not exist.
  • Searching for element 11: Node value 11 exists.

Idea to Solve the Problem

To solve the problem of searching for an element in a circular singly linked list, follow these steps:

  1. Initialize a pointer temp to the head node of the circular linked list.
  2. Traverse the circular linked list and compare the value of each node with the target value.
  3. If a node with the target value is found, print that the value exists and return.
  4. If the traversal reaches the head node again without finding the target value, print that the value does not exist.

Pseudocode

function searchElement(value):
    if head is null:
        print "Empty Linked List"
    else:
        temp = head
        while temp is not null:
            if temp.data is equal to value:
                print "Node value", value, "exists"
                return
            temp = temp.next
            if temp is equal to head:
                print "Node value", value, "does not exist"
                return

Algorithm Explanation

  1. If the circular linked list is empty, print "Empty Linked List."
  2. Initialize a pointer temp to the head node of the circular linked list.
  3. Traverse the linked list by moving the temp pointer to the next node until the end of the list is reached.
  4. During traversal, if the value of the current node matches the target value, print that the value exists and return.
  5. If the traversal reaches the head node again without finding the target value, print that the value does not exist.

Code Solution

Time Complexity

The time complexity of searching for an element in a circular singly linked list is O(n), where n is the number of nodes in the linked list. In the worst case, the algorithm may need to traverse all nodes in the circular linked list to determine whether the target value exists or not.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment