🎉 Yay! DSA-30 is now live!
Day 3 - Linked Lists
Doubly Linked List

Basic Operations on a Doubly Linked List

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

  1. Define a Doubly Linked List
  2. Insert a node at the beginning
  3. Insert a node at the end
  4. Insert a node after a given node
  5. Insert a node before a given node
  6. Delete the first node
  7. Delete the last node
  8. Delete a node after a given node
  9. Delete a node before a given node
  10. Traverse and Display all the nodes
  11. Reverse the Doubly Linked List

Define a Doubly Linked List

  • CODE

Insert a node at the beginning

  • ALGORITHM
Step 1: if AVAIL = NULL
            Write Overflow
            Go to step 9
        [END OF if]
Step 2: SET newNode = AVAIL
Step 3: AVAIL = AVAIL->next
Step 4: SET newNode->prev = NULL
Step 5: SET newNode->data = val
Step 6: SET newNode->next = start
Step 7: SET start->prev = newNode
Step 8: SET start = newNode
Step 9: EXIT
  • CODE

Insert a node at the end

  • ALGORITHM
Step 1: if AVAIL = NULL
            Write Overflow
            Go to step 11
        [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->data = val
Step 8: SET newNode->prev = ptr
Step 9: SET newNode->next = NULL
Step 10: ptr->next = newNode
Step 11: EXIT
  • CODE

Insert a node after a given node

  • 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 newNode->data = val
Step 5: SET ptr = start
Step 6: Repeat step 7 while ptr->data != val
Step 7:     SET ptr = ptr->next
        [END OF LOOP]
Step 8: SET ptr->next->prev = newNode
Step 9: SET newNode->next = ptr->next
Step 10: SET newNode->prev = ptr
Step 11: SET ptr->next = newNode
Step 12: EXIT
  • CODE

Insert a new node before a given node

  • 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 newNode->data = val
Step 5: SET ptr = start
Step 6: Repeat step 7 while ptr->data != val
Step 7:     SET ptr = ptr->next
        [END OF LOOP]
Step 8: SET newNode->prev = ptr->prev
Step 9: SET newNode->next = ptr
Step 10: SET ptr->prev->next = newNode
Step 11: SET ptr->prev = newNode
Step 12: EXIT
  • CODE

Delete the first node

  • ALGORITHM
Step 1: if start = NULL
            Write Underflow
            Go to step 6
        [END OF if]
Step 2: SET ptr = start
Step 3: SET start = start->next
Step 4: SET start->prev = NULL
Step 5: free ptr
Step 6: EXIT
  • CODE

Delete the last node

  • ALGORITHM
Step 1: if start = NULL
                Write Underflow
                Go to step 7
        [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->prev->next = NULL
Step 6: free ptr
Step 7: EXIT
  • CODE

Delete a node after a given node

  • 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->data != val
Step 4:         SET ptr = ptr->next
        [END OF LOOP]
Step 5: SET temp = ptr->next
Step 6: SET ptr->next = temp->next
Step 7: SET temp->next->prev = ptr
Step 8: free temp
Step 9: EXIT
  • CODE

Delete a node before a given node

  • 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->data != val
Step 4:         SET ptr = ptr->next
        [END OF LOOP]
Step 5: SET temp = ptr->prev
Step 6: SET ptr->prev = temp->prev
Step 7: SET temp->prev->next = ptr
Step 8: free temp
Step 9: EXIT
  • CODE

Traverse and Display all the nodes

  • ALGORITHM
Step 1: if start = NULL
            Write "List is empty!"
            Go to Step 4
        [END OF if]
Step 2: SET ptr = start
Step 3: Repeat Step 4 while ptr is not NULL
    Step 4: Write ptr.data
            SET ptr = ptr.next
        [END OF LOOP]
Step 5: EXIT
  • CODE

Reverse the list

  • ALGORITHM
Step 1: if start = NULL
            Write Underflow
            Go to Step 8
        [END OF if]
Step 2: SET ptr = start
Step 3: SET new_head = NULL
Step 4: Repeat Steps 5 to 7 while ptr is not NULL
    Step 5: SET temp = ptr.prev
    Step 6: SET ptr.prev = ptr.next
    Step 7: SET ptr.next = temp
    Step 8: SET new_head = ptr
    Step 9: SET ptr = ptr.prev
        [END OF LOOP]
Step 10: SET start = new_head
Step 11: EXIT
  • CODE
Circular Linked ListCircular Doubly Linked List