This approach reserves the List's first node (Index Position # zero) as a Sentinel called the 'NIL node' it does not hold valid key data, it is used for keeping track of the Head pointer value in the Next attribute and the Tail pointer value in the Prev attribute.

For the steps below us a Circular DLL with sentinel node architecture. Upload your work.

1. Illustrate an empty list. Show result.
2. Insert "M" Show result.
3. Insert "E" Show result.
4.  

Transcribed Image Text:

Sentinel Node IP # Zero Key data Prev - IP # Next IP# Node Index Position # Prev Key IP# data Next IP# Node Index Position # Prev Key Next IP# data IP# L.nil.next (attribute pointer to first element in list, the head.) L.nil.prev (attribute pointer to last element in list, the tail.) Node Index Position # Prev Key Next data IP# IP# A sentinel is a dummy object that allows us to simplify boundary conditions, head and tail. Presume the pseudo code 'NIL node' index position # = zero is reserved for the sentinel. The list L has an object L.nil that represents node zero and has all the attributes of the other objects in the list (i.e. prev key next). Wherever we have a reference to NIL in a LIST algorithms, we replace it by a reference to the sentinel L.nil node index position # = zero. An empty list consists of just the sentinel, and both L.mil.next and L.nil.prev point to L.nil. The attribute L.nil.next points to the head of the list, and L.nil.prev points to the tail. Similarly, both the next attribute of the tail and the prev attribute of the head point to L.nil. Eliminate Variables Head, and Tail. Since L.nil.next points to the head, we can eliminate the variable attribute L.head altogether, replacing references to it by references to L.nil.next. Likewise eliminate the variable attribute L.tail replacing references to it by references to L.nil.prev. LIST-SEARCH(L, k) 1) x = L.nil.next 2) while (x != L.nil and x.key != k) 3) x = x.next 4) return x LIST-INSERT(L, x) 1) x.next = L.nil.next 2) L.nil.next.prev = x 3) L.nil.next = x 4) x.prev - L.nil LIST-DELETE(L, X) 1) if x.prev != NIL 2) x.prev:next = x.next 3) x.next:prev = x.prev 3) else 4) L.nil.next = x.next 5) if x.next != NIL 6) x.next.prev=x.prev 7) L.remove(x) //attributes = null 8) L. list.trimToSize() // reduces windows LIST-GET_NEXT_AVAIL_NODE(L) Go To Settings to activate 1) return x Sentinel Node IP # Zero Key data Prev - IP # Next IP# Node Index Position # Prev Key IP# data Next IP# Node Index Position # Prev Key Next IP# data IP# L.nil.next (attribute pointer to first element in list, the head.) L.nil.prev (attribute pointer to last element in list, the tail.) Node Index Position # Prev Key Next data IP# IP# A sentinel is a dummy object that allows us to simplify boundary conditions, head and tail. Presume the pseudo code 'NIL node' index position # = zero is reserved for the sentinel. The list L has an object L.nil that represents node zero and has all the attributes of the other objects in the list (i.e. prev key next). Wherever we have a reference to NIL in a LIST algorithms, we replace it by a reference to the sentinel L.nil node index position # = zero. An empty list consists of just the sentinel, and both L.mil.next and L.nil.prev point to L.nil. The attribute L.nil.next points to the head of the list, and L.nil.prev points to the tail. Similarly, both the next attribute of the tail and the prev attribute of the head point to L.nil. Eliminate Variables Head, and Tail. Since L.nil.next points to the head, we can eliminate the variable attribute L.head altogether, replacing references to it by references to L.nil.next. Likewise eliminate the variable attribute L.tail replacing references to it by references to L.nil.prev. LIST-SEARCH(L, k) 1) x = L.nil.next 2) while (x != L.nil and x.key != k) 3) x = x.next 4) return x LIST-INSERT(L, x) 1) x.next = L.nil.next 2) L.nil.next.prev = x 3) L.nil.next = x 4) x.prev - L.nil LIST-DELETE(L, X) 1) if x.prev != NIL 2) x.prev:next = x.next 3) x.next:prev = x.prev 3) else 4) L.nil.next = x.next 5) if x.next != NIL 6) x.next.prev=x.prev 7) L.remove(x) //attributes = null 8) L. list.trimToSize() // reduces windows LIST-GET_NEXT_AVAIL_NODE(L) Go To Settings to activate 1) return x

Answer rating: 100% (QA)

a circular doubly linked list CDLL with a sentinel node architecture A sentinel node is a dummy node that simplifies code by handling edge cases specifically those related to the head and tail of the ... View the full answer