Data Structure (2130702)

BE | Semester-3   Summer-2019 | 06/04/2019

Q1) (c)

Write algorithm for inserting an element in circular queue and deleting a node from a singly linked list.

Algorithm for inserting an element in circular queue

Procedure: CQINSERT (F, R, Q, N, Y)

  • This procedure inserts Y at Rear end of the Circular Queue.
  • Queue is represented by a vector Q containing N elements.
  • F is pointer to the Front element of a queue.
  • R is pointer to the Rear element of a queue.
1. [Reset Rear Pointer]
  If R = N
  Then R <-- 1
  Else R <-- R+1
2. [Overflow?]
  If F=R
  Then Write ('Overflow')
    Return
3. [Insert element]
  Q[R] <-- Y
4. [Is Front pointer properly set?]
  If F=0
  Then F<--1
  Return

Algorithm for deleting a node from a singly linked list

Procedure: DELETE( X, FIRST)

Given X, an address of node which we want to delete and FIRST is a pointer to the first element of a linked linear list. Typical node contains INFO and LINK fields. SAVE & PRED are temporary pointer variables.
1. [Is Empty list?]
  If FIRST = NULL
  Then write (‘Underflow’)
    Return
2. [Initialize search for X]
  SAVE <-- FIRST
3. [Find X]
  Repeat thru step-5 while SAVE ? X and LINK (SAVE) ? NULL
  Then F <-- R <-- 0
    Return(Y)
4. [Update predecessor marker]
  PRED <-- SAVE
5. [Move to next node]
  SAVE <-- LINK (SAVE)
6. [End of the list]
  If SAVE ? X
  Then write (‘Node not found’)
    Return
7. [Delete x]
  If X = FIRST (if X is first node?)
  Then FIRST <-- LINK (FIRST)
  Else LINK (PRED) <-- LINK (X)
8. [Free Deleted Node]
  Free (X)