Linked List Data Structure Questions

10. Using the circular doubly linked list shown here, give the expression corresponding to each of the following descriptions: see image.

(For example, the expression for the info member of Node1, referenced from pointer A, would be A->info.)

• The info member of Node 1, referenced from pointer C
• The info member of Node 2, referenced from pointer B
• The next member of Node 2, referenced from pointer A
• The next member of Node 4, referenced from pointer C
• Node 1, referenced from pointer B
• The back member of Node 4, referenced from pointer C
• The back member of Node 1, referenced from pointer A

11. The text edited by a line editor is represented by a doubly linked list of nodes, each of which contains an 80-column line of text (type LineType). There is one external pointer (type LineType*) to this list, which points to the current line in the text being edited, the list has a header node, which contains the string in the text being edited. The list has a header node, which contains the string in the text being edited. The list has a header node, which contains the string in the text being edited. The list has a header node, which contains the string "- - - Top of File - - -"and a trailer node, which contains the string "- - - Bottom of File - - -".

• Draw a sketch of this data structure.
• Write the type declarations to support this data structure.
• Write the class constructor, which sets up the header and trailer nodes.
• Code the following operations:

GoToTop(LineType *linePtr)
Function: Goes to the top of the list.
Postcondition: currentLine is set to access the first line of text.

GoToBottom(LineType *linePtr)
Function: Goes to the bottom of the list.
Postcondition: currentLine is set to access the last line of text.

• Describe the operations in part (d) in terms of Big-O notation. How could you change the list to make these operations O(1)?
• Code the InsertLine operation, using the following specification:

InsertLine(LinePtrType linePtr, LineType newLine)
Function: Inserts newLine at the current line.
Postconditions: newLine has been inserted after currentLine. currentLine points to newLine.

• What other member functions should be included?
• Of the three variations of linked lists (circular, with header and trailer nodes, and doubly linked), which would be most appropriate for each of the following applications?
  • You want to search a list for a key and return the keys of the two elements that come before it and the kays of the two elements that come after it.
  • A text file contains integer elements, one per line, sorted from smallest to largest. You must read the values from the file and create a sorted linked list containing the values.
  • A list is short and frequently becomes empty. You want a list that is optimal for inserting an element into the empty list and deleting the last element from the list.
• What is the Big-O measure for initializing the free list in the array-based linked implementation? For the GetNode and FreeNode functions?
• Use the linked lists contained in the array pictured in Figure 6.19 to answer the following questions: see image.
  • What elements are in the list pointed to by list1?
  • What elements are in the list pointed to by list2?
  • What array positions (indexes) are part of the free space list?
  • What would the array look like after the deletion of Nell from the first list?