Linked list is an important data structure in computer science and programming. Interviewers may ask questions about linked list to assess a candidate’s understanding of the data structure, problem-solving skills, and coding ability.

Understanding linked list is important for software development roles that involve designing and implementing data structures and algorithms. It is worth spending time to understand the basics and practice coding exercises to strengthen one’s skills.

A circular linked list is a type of linked list where the last node of the list points back to the first node, creating a loop. In other words, the next pointer of the last node points to the head of the linked list. Here’s an example of a circular linked list:

1 -> 2 -> 3 -> 4 -> 1

Circular linked lists have a number of uses in computer science, such as implementing circular buffers, scheduling algorithms, and more.

Compared to other data structures, circular linked lists have some advantages and disadvantages:

Pros:

  • Can be used to implement circular data structures such as buffers and queues
  • Constant time insertion and deletion at the beginning and end of the list
  • Efficient memory usage compared to arrays

Cons:

  • Not as efficient for random access as arrays
  • More complex to implement and maintain than arrays
  • Can result in infinite loops if not properly implemented or handled

Here are some of the basic circular linked list operations you should know if you are preparing for an interview:

  1. Creation: Create a circular linked list with a given set of nodes.
  2. Insertion at the beginning: Insert a new node with a given data value at the beginning of the list.
  3. Deletion at the beginning: Delete the first node in the list.
  4. Deletion at the end: Delete the last node in the list.
  5. Traversal: Traverse the list and print the data in each node.
  6. Searching for a node: Search for a node with a given data value.
  7. Insertion at a specific position: Insert a new node with a given data value at a specific position in the list.
  8. Deletion at a specific position: Delete the node at a specific position in the list.
  9. Reversing a circular linked list: Reverse the order of nodes in the list.
  10. Splitting a circular linked list: Split the list into two separate lists at a specific node.
  11. Joining two circular linked lists: Join two lists into a single circular linked list.
  12. Finding the middle node: Find the middle node in the list.
  1. Insertion at the beginning:
function insertAtBeginning(data):
    newNode = Node(data)
    if head is None:
        head = newNode
        newNode.next = head
    else:
        current = head
        while current.next != head:
            current = current.next
        current.next = newNode
        newNode.next = head
        head = newNode

In this operation, we create a new node with the given data and insert it at the beginning of the list. If the list is empty, we set the head to the new node and make it circular by setting its next pointer to itself. Otherwise, we iterate through the list to find the last node and update its next pointer to the new node. Finally, we set the new node’s next pointer to the head and update the head to point to the new node.

  1. Insertion at the end:
function insertAtEnd(data):
    newNode = Node(data)
    if head is None:
        head = newNode
        newNode.next = head
    else:
        current = head
        while current.next != head:
            current = current.next
        current.next = newNode
        newNode.next = head

In this operation, we create a new node with the given data and insert it at the end of the list. If the list is empty, we set the head to the new node and make it circular by setting its next pointer to itself. Otherwise, we iterate through the list to find the last node and update its next pointer to the new node. Finally, we set the new node’s next pointer to the head.

  1. Deletion at the beginning:
function deleteAtBeginning():
    if head is None:
        return
    elif head.next == head:
        head = None
    else:
        current = head
        while current.next != head:
            current = current.next
        current.next = head.next
        head = head.next

In this operation, we delete the first node in the list. If the list is empty, we do nothing. If the list contains only one node, we set the head to None. Otherwise, we iterate through the list to find the last node and update its next pointer to point to the second node. Finally, we update the head to point to the second node.

  1. Deletion at the end:
function deleteAtEnd():
    if head is None:
        return
    elif head.next == head:
        head = None
    else:
        current = head
        prev = None
        while current.next != head:
            prev = current
            current = current.next            prev.next = head

In this operation, we delete the last node in the list. If the list is empty, we do nothing. If the list contains only one node, we set the head to None. Otherwise, we iterate through the list to find the second-to-last node and update its next pointer to point to the head. Finally, we update the previous node’s next pointer to point to the head.

  1. Traversal:
function traverse():
    if head is not null:
        set current to head
        while true:
            // process the current node
           // ...

            // move to the next node
            set current to current.next
            if current is head:
                // we have traversed the entire list, so we can exit the loop
                break

In this operation, we traverse the list and print the data in each node. If the list is empty, we do nothing. Otherwise, we iterate through the list starting from the head and print the data in each node until we reach the head again. These are just some of the basic operations that can be performed on a circular linked list. Here is one code example in Python.

  1. Searching for a node:
See also  Linked list implementation and operations in Ruby

To search for a node with a given data value in a circular linked list, we can modify the traversal operation to check each node’s data value and return the node if found. Here’s an example pseudocode for searching a circular linked list:

function search(data):
    if head is None:
        return None
    else:
        current = head
        while current.next != head:
            if current.data == data:
                return current
            current = current.next
        if current.data == data:
            return current
        else:
            return None

In this operation, we start from the head of the list and iterate through each node until we find the node with the given data value or reach the head again. If we find the node, we return it. Otherwise, we return None.

  1. Insertion at a specific position:

To insert a new node with a given data value at a specific position in a circular linked list, we can modify the pseudocode for insertion at the beginning and end to insert the new node between two existing nodes. Here’s an example pseudocode for insertion at a specific position:

function insertAtPosition(data, position):
    newNode = Node(data)
    if position == 1:
        insertAtBeginning(data)
    else:
        current = head
        for i in range(1, position - 1):
            current = current.next
        newNode.next = current.next
        current.next = newNode

In this operation, we first create a new node with the given data value. If the position is 1, we simply call the insertAtBeginning operation. Otherwise, we iterate through the list to find the node at the previous position, and insert the new node between the previous node and the current node.

  1. Deletion at a specific position:

To delete a node at a specific position in a circular linked list, we can modify the pseudocode for deletion at the beginning and end to delete the node at the specified position. Here’s an example pseudocode for deletion at a specific position:

function deleteAtPosition(position):
    if head is None:
        return
    elif position == 1:
        deleteAtBeginning()
    else:
        current = head
        prev = None
        for i in range(1, position):
            prev = current
            current = current.next
        prev.next = current.next

In this operation, we first check if the list is empty. If so, we do nothing. If the position is 1, we simply call the deleteAtBeginning operation. Otherwise, we iterate through the list to find the node at the specified position and update the previous node’s next pointer to point to the next node, effectively deleting the current node.

  1. Reversing a circular linked list:
See also  Implement doubly linked list using shared ptr

To reverse a circular linked list, we can modify the pseudocode for reversing a singly linked list. Here’s an example pseudocode for reversing a circular linked list:

function reverse():
    if head is None:
        return
    else:
        prev = None
        current = head
        while current.next != head:
            next = current.next
            current.next = prev
            prev = current
            current = next
        current.next = prev
        head.next = current
        head = current

In this operation, we first check if the list is empty. If so, we do nothing. Otherwise, we initialize two pointers called prev and current to None and head, respectively. We then traverse the list, updating the next pointer of each node to point to the previous node, and updating the prev and current pointers accordingly. Finally, we update the next pointer of the last node to point to the head, and update the head pointer to point to the last node.

  1. Splitting a circular linked list:

To split a circular linked list into two separate lists at a specific node, we can modify the pseudocode for traversing a circular linked list to stop at the specified node, and update the next pointers of the nodes before and after the specified node accordingly. Here’s an example pseudocode for splitting a circular linked list:

function splitAtNode(node):
    if head is None:
        return None, None
    else:
        current = head
        while current.next != head and current != node:
            current = current.next
        if current != node:
            return None, None
        else:
            newHead = node.next
            node.next = head
            current = newHead
            while current.next != head:
                current = current.next
            current.next = newHead
            return head, newHead

In this operation, we first check if the list is empty. If so, we return None, None. Otherwise, we traverse the list until we find the specified node, and update its next pointer to point to the head of the list. We then set the new head of the second list to the node’s next pointer, and iterate through the second list to find the last node and update its next pointer to point to the new head.

See also  Java LinkedList Class Implementation Guide and Examples

Finally, we return the head of the first list and the head of the second list as separate lists.

  1. Joining two circular linked lists:

To join two circular linked lists into a single circular linked list, we can simply update the next pointer of the last node in the first list to point to the head of the second list, and update the next pointer of the last node in the second list to point to the head of the first list. Here’s an example pseudocode for joining two circular linked lists:

function join(list1, list2):
    if list1 is None:
        return list2
    elif list2 is None:
        return list1
    else:
        current1 = list1
        while current1.next != list1:
            current1 = current1.next
        current1.next = list2
        current2 = list2
        while current2.next != list2:
            current2 = current2.next
        current2.next = list1
        return list1

In this operation, we first check if either list is empty. If so, we return the other list as the joined list. Otherwise, we iterate through the first list to find the last node and update its next pointer to point to the head of the second list. We then iterate through the second list to find the last node and update its next pointer to point to the head of the first list.

  1. Finding the middle node:

To find the middle node in a circular linked list, we can use the slow and fast pointer technique, where the slow pointer moves one node at a time and the fast pointer moves two nodes at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node. Here’s an example pseudocode for finding the middle node:

function findMiddle():
    if head is None:
        return None
    else:
        slow = head
        fast = head
        while fast.next != head and fast.next.next != head:
            slow = slow.next
            fast = fast.next.next
        return slow

In this operation, we first check if the list is empty. If so, we return None. Otherwise, we initialize two pointers called slow and fast to the head of the list. We then traverse the list using the slow and fast pointers, where the slow pointer moves one node at a time and the fast pointer moves two nodes at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

Written by

With 10+ years in software engineering, I specialize in blogging and web development. My skills span front-end, back-end, database design, web security, and SEO. Passionate about crafting helpful digital experiences.