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

Basic Operations on a Linked List

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

  1. Define a Linked List
  2. Insert an Element at the beginning
  3. Insert an Element at the end
  4. Insert an Element after a given position
  5. Insert an Element before a given position
  6. Delete an Element at the beginning
  7. Delete an Element at the end
  8. Delete an Element after a given position
  9. Delete an Element before a given position
  10. Count the number of Elements/Nodes
  11. Traverse and Display the Elements/Nodes
  12. Reverse the Linked List

Define a Linked List

Insert an Element at the beginning

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

Insert an Element at the End

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

Insert an Element after a given position/element

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

Insert an Element before a given position/element

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

Delete an Element at the Beginning

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

Delete an Element at the End

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

Delete an Element after a given position

  • ALGORTIHM
Step 1: if start = NULL
            Write Underflow
            Go to step 10
        [END OF if]
Step 2: SET ptr = start
Step 3: SET prePtr = ptr
Step 4: Repeat steps 5 to 6 while prePtr->data != val
Step 5:         SET prePtr = ptr
Step 6:         SET ptr = ptr->next
        [END OF LOOP]
Step 7: SET temp = ptr
Step 8: SET prePtr-> next = ptr->next
Step 9: free temp
Step 10: EXIT
  • CODE

Delete an Element before a given position

  • CODE

Count the number of Elements/Nodes

  • ALGORTIHM
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:         SET ptr = ptr->next
                SET count = count + 1
        [END OF LOOP]
Step 5: EXIT
  • CODE

Traverse and Display the Elements/Nodes

  • ALGORTIHM
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

Reverse a Linked List

  • ALGORITHM
Step 1: SET current = start
Step 2: SET prev = NULL
Step 3: SET nextPtr = NULL
Step 4: Repeat steps 5 to 7 while current is not NULL
Step 5:     SET nextPtr = current->next
Step 6:     SET current->next = prev
Step 7:     SET prev = current
            SET current = nextPtr
        [END OF LOOP]
Step 8: SET start = prev
Step 9: EXIT
  • CODE
IntroductionCircular Linked List