Circular Linked List Lecture Notes

Introduction to Circular Linked Lists

• A circular linked list is a variation of a linked list where the last node points back to the first node, forming a circle.
• In a standard singly linked list:
  • Each node has two parts: data part and address part.
  • The address part points to the next node.
• In a circular linked list:
  • The last node's address part points back to the first node instead of being null.

Structure of Nodes

• Each node is represented as: struct node { int data; // Data part struct node *next; // Pointer to the next node };
• The head pointer holds the address of the first node.

Creating a Circular Linked List

1. Initializing the List
   • Start with head as NULL if the list is empty.
2. Dynamic Memory Allocation
   • Use malloc to allocate memory for new nodes: struct node *new_node; new_node = (struct node*)malloc(sizeof(struct node));
3. Inserting Nodes
   • If the list is empty (head is NULL):
     • Set head to point to new_node.
   • If the list is not empty:
     • Use a temporary pointer to traverse and find the last node.
     • Link the new node to the last node.
4. Making it Circular
   • After inserting nodes, link the last node back to the head: temp->next = head;

Functions to Implement

Create Circular Linked List Function

• Pseudocode:
  • Check if head is NULL (list empty):
    • Assign head to new_node.
  • Use a temporary pointer to traverse and insert nodes.
  • After inserting nodes, make the last node's next point to head.

Displaying Circular Linked List

1. Traversing the List
   • Use a temporary pointer initialized to head.
   • Check if the list is empty first.
2. Loop through Nodes
   • Use a loop that continues until back to head:
     • Print each node's data.
     • Move to the next node: temp = temp->next;
   • Ensure the loop condition checks against head instead of NULL.

Example Code for Creation and Display

• Example function to create and display: void createCircularList() { // Implementation } void displayCircularList() { // Implementation }

Conclusion

• The circular linked list allows continuous traversal of nodes without null termination.
• Understanding circular linked lists is crucial for implementing data structures that require circular traversal.
• Next lecture will cover inserting data into circular linked lists.