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:
- Creation: Create a circular linked list with a given set of nodes.
- Insertion at the beginning: Insert a new node with a given data value at the beginning of the list.
- Deletion at the beginning: Delete the first node in the list.
- Deletion at the end: Delete the last node in the list.
- Traversal: Traverse the list and print the data in each node.
- Searching for a node: Search for a node with a given data value.
- Insertion at a specific position: Insert a new node with a given data value at a specific position in the list.
- Deletion at a specific position: Delete the node at a specific position in the list.
- Reversing a circular linked list: Reverse the order of nodes in the list.
- Splitting a circular linked list: Split the list into two separate lists at a specific node.
- Joining two circular linked lists: Join two lists into a single circular linked list.
- Finding the middle node: Find the middle node in the list.
- 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.
- 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.
- 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.
- 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.
- 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
breakIn 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.
- Searching for a node:
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.
- 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.
- 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.
- Reversing a circular linked list:
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.
- 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.
Finally, we return the head of the first list and the head of the second list as separate lists.
- 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.
- 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.
