Background: You have two implementations of a doubly linked list, SimpleList and
ID: 3628753 • Letter: B
Question
Background: You have two implementations of a doubly linked list, SimpleList and SentinelList. For purposes of discussion, let firstNode denote the Node holding the first element, and let lastNode denote the Node holding the last element.
• An instance of SimpleList has two fields: first = firstNode, and last = lastNode.
• An instance of SentinelList has two fields: header = new Node( ), and trailer = new Node( ). These are distinct, special nodes created by the SentinelList constructor, and they stand permanently at either end of the list. We have header.next = firstNode, and trailer.prev = lastNode.
A) If the list is empty, then firstNode and lastNode don't exist. Then what should go in SimpleList's first and last fields? How about SentinelList's header and trailer fields? How about header.next and trailer.prev?
SimpleList. first _______
SimpleList. last _____________
SentinelList.header ______________
SentinelList.trailer _______________
SentinelList.header->next _____________
SentinelList.trailer->prev _____________
Explanation / Answer
For a simple doubly linked list that's empty, head and tail should be null. Thus, SimpleList.first = NULL; // or 0 SimpleList.last = NULL; // or 0 Now, according to the definition of SentinelList, header and trailer stand permanently at either end of the list. Thus, SentinelList.header = header; SentinelList.trailer = trailer; Because of this, we know what to put in the last two variables asked for: SentinelList.header->next = trailer; SentinelList.trailer->prev = header;
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.