Data Structure - 5 Circular & Doubly Linked List

Data Structure - 5 Circular & Doubly Linked List

• 1.
  Department of Informatics Facultyof Industrial Engineering Universitas Pembangunan Nasional “Veteran” Yogyakarta Data Structure Andi Nurkholis, S.Kom., M.Kom. Doubly & Circular Linked List September 15, 2025
• 2.
  Definition of DoublyLinked List Doubly Linked List is a type of linked list in which each node has two pointers: one pointing to the next node and one pointing to the previous node. This allows bidirectional traversal within the list. Node Structure in Doubly Linked List: struct Node { int data; // Stores the data struct Node* next; // Pointer to the next node struct Node* prev; // Pointer to the previous node };
• 3.
  Advantage of DoublyLinked List ü Bidirectional Traversal: Allows traversal from both the front and the back, which is very useful in certain applications. ü Flexibility in Insertion and Deletion: Node deletion can be performed more easily with direct access to the previous node. ü Reduced Complexity in Operations: Operations such as deletion from both ends can be carried out more efficiently.
• 4.
  Basic Operation of DoublyLinked List 1. Adding a Node at the Beginning (Head) 2. Adding a Node at the End (Tail) 3. Deleting a Node 4. Traversing a Doubly Linked List
• 5.
  Adding Head Node 1.Create a new node using memory allocation. 2. Store the data to be inserted into the new node. 3. Set next pointer of the new node to point to the old head, and assign NULL to prev pointer of the new node. 4. If the old head is not NULL, update prev pointer of the old head to point to the new node. 5. Update the head to point to the new node as the first element.
• 6.
  Adding Tail Node 1.Create a new node through memory allocation. 2. Store the desired data into the new node. 3. Set the next pointer of the new node to NULL, since it will be placed at the end. 4. Link the prev pointer of the new node to the old tail node, and update the next pointer of the old tail to point to the new node. 5. Update the tail to point to the new node as the last element.
• 7.
  Deleting Node 1. Identifythe node to be deleted (for example, by searching based on value or position). 2. If the node has prev ≠ NULL, set the next of the previous node to point to the next node. 3. If the node has next ≠ NULL, set the prev of the next node to point to the previous node. 4. If the node is the head, update the head to the next node. If the node is the tail, update the tail to the previous node. 5. Delete the node from memory (deallocate).
• 8.
  Traversing Doubly LinkedList 1. Initialize a pointer current to point to the head. 2. While current ≠ NULL, perform a visit process (for example, display the data). 3. Move the current pointer to current.next to traverse forward. 4. To traverse backward, start from the tail and move current to current.prev. 5. Traversal is complete when all nodes have been visited, either in the forward or backward direction.
• 9.
  Definition of CircularLinked List Circular Linked List is a type of linked list in which the last node points back to the first node, thereby forming a circle. It can be either singly circular or doubly circular. Node Structure in a Circular Linked List: struct Node { int data; // Stores the data struct Node* next; // Pointer to the next node };
• 10.
  Advantage of CircularLinked List ü Support for Repeated Processing: Allows traversal of the list to be repeated without needing to return to the head, making it suitable for iterative applications. ü Efficient Memory Usage: Eliminates the need to manage a null pointer at the end, thereby reducing memory overhead. ü Easy Data Exchange: Suitable for applications such as music players, where tracks can be repeated.
• 11.
  Basic Operation of CircularLinked List 1. Adding a Node at the Beginning (Head) 2. Adding a Node at the End (Tail) 3. Deleting a Node 4. Traversing a Circular Linked List
• 12.
  Adding Head Node 1.Create a new node using memory allocation, then fill it with data. 2. If the list is empty, set the next of the new node to point to itself, and update the head to the new node. 3. If the list is not empty, link the next of the new node to the old head. 4. Find the last node (tail) and update its next to point to the new node. 5. Update the head so that it points to the new node as the first element.
• 13.
  Adding Tail Node 1.Create a new node using memory allocation and fill it with data. 2. If the list is empty, set the next of the new node to point to itself, then set both the head and the tail to point to the new node. 3. If the list is not empty, link the next of the new node to the head. 4. Update the next of the old tail to point to the new node. 5. Update the tail to the new node as the last element.
• 14.
  Deleting Node 1. Identifythe node to be deleted (based on value or position) by traversing from the head. 2. Store a prev pointer for the node preceding the target. 3. If the target node is the head, find the last node (tail) and update its next to point to the new head (head.next). 4. If the target node is not the head, set the next of prev to point to the node after the target. 5. Deallocate the target node from memory.
• 15.
  Traversing Circular LinkedList 1. Initialize a pointer current to point to the head. 2. If the list is empty (head = NULL), the traversal is complete. 3. Visit the node pointed to by current (for example, print the data). 4. Move the current pointer to current.next. 5. Repeat steps 3–4 until current returns to the head, then stop the traversal because all nodes have been visited.
• 16.
  Department of Informatics Facultyof Industrial Engineering Universitas Pembangunan Nasional “Veteran” Yogyakarta Andi Nurkholis, S.Kom., M.Kom. September 15, 2025 Done Thank You