Circular Doubly Linked List

Basic Operations on a Circular Doubly Linked List

We can perform the following basic operations on a Circular Doubly Linked List:

Define a Circular Doubly Linked List
Insert a node at the beginning
Insert a node at the end
Delete a node at the beginning
Delete a node at the end
Traverse and Display all the nodes

Define a Circular Doubly Linked List

CODE

Insert a node at the beginning

ALGORITHM

Step 1: if AVAIL = NULL
            Write Overflow
            Go to step 13
        [END OF if]
Step 2: newNode = AVAIL
Step 3: AVAIL = AVAIL->next
Step 4: SET ptr = start
Step 5: Repeat step 6 while ptr->next != null
Step 6:     SET ptr = ptr->next
        [END OF LOOP]
Step 7: SET newNode->prev = ptr
Step 8: SET newNode->data = val
Step 9: SET newNode->next = start
Step 10: SET ptr->next = newNode
Step 11: start->prev = newNode
Step 12: start = newNode
Step 13: EXIT

CODE

Insert a node at the end

ALGORITHM

Step 1: if AVAIL = NULL
            Write Overflow
            Go to step 12
        [END OF if]
Step 2: newNode = AVAIL
Step 3: AVAIL = AVAIL->next
Step 4: SET ptr = start
Step 5: Repeat step 6 while ptr->next != NULL
Step 6:     SET ptr = ptr->next
        [END OF LOOP]
Step 7: SET newNode->prev = ptr
Step 8: SET newNode->data = val
Step 9: SET newNode->next = start
Step 10: SET ptr->next = newNode
Step 11: SET start->prev = newNode
Step 12: EXIT

CODE

Delete a node at the beginning

ALGORITHM

Step 1: if start = NULL
            Write Underflow
            Go to step 9
        [END OF if]
Step 2: SET ptr = start
Step 3: Repeat step 4 while ptr->next != NULL
Step 4:     SET ptr = ptr->next
        [END OF LOOP]
Step 5: SET ptr->next = start->next
Step 6: SET start->next->prev = ptr
Step 7: free start
Step 8: start = ptr->next
Step 9: EXIT

CODE

Delete a node at the end

ALGORITHM

Step 1: if start = NULL
            write underflow
            Go to step 9
        [END OF if]
Step 2: SET ptr = start
Step 3: Repeat step 4 while ptr->next != NULL
Step 4:     SET ptr = ptr->next
        [END OF LOOP]
Step 5: start->prev = ptr->prev
Step 6: ptr->prev = start
Step 7: free ptr
Step 8: EXIT

CODE

Traverse and Display all the nodes

ALGORITHM

Step 1: [Initialize] SET ptr = start, count = 0
Step 2: Repeat Steps 3 to 4 while ptr != NULL
Step 3:         Apply process to ptr->data
Step 4:         PRINT ptr->data
                SET ptr = ptr->next
        [END OF LOOP]
Step 5: EXIT

CODE

Doubly Linked List Problem List