Data Structure - 5 Circular & Doubly Linked List

The Circular & Doubly Linked List slide the Data Structures course include:
1. Definition of doubly linked list
2. Advantage of doubly linked list
3. Basic operation of doubly linked list
4. Definition of circular linked list
5. Advantage of circular linked list
6. Basic operation of circular linked list

1. Department of Informatics
Faculty of 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 Doubly Linked 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 Doubly Linked 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 ofDoubly Linked 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.Identify the 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 Linked List
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 Circular Linked 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 Circular Linked 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 ofCircular Linked 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.Identify the 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 Linked List
1.Initialize a pointer current to point to the head.
2.If the list is empty (head = NULL), the traversal is complete.
3.V 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
Faculty of Industrial Engineering
Universitas Pembangunan Nasional “Veteran” Yogyakarta
Andi Nurkholis, S.Kom., M.Kom.
September 15, 2025
Done
Thank
You