DOC PREVIEW
UNI CS 1520 - Lecture Notes

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Objective: Gain experience implementing a linked data structure by using a doubly-linked list to implementa positional list ADT. Background: There are three broad categories of list operations defined in the textbook: index-based operations - the list is manipulated by specifying an index location, e.g.,myList.insert(3, item) # insert item at index 3 in myList content-based operations - the list is manipulated by specifying some content (i.e., item) in the list, e.g.,myList.index(item) # search for the item in the list and return its index if found; otherwise return -1 positional-base operations - a cursor (current position in the list) can be moved around the list, and it isused to identify list items to be manipulated, e.g.,myList.first() # sets the cursor to the head of the listmyList.remove() # deletes the first item in the list because that’s where the cursor is locatedThe following table summarizes the operations from the three basic categories on a list, L:L.hasNext()L.next()L.hasPrevious()L.previous()L.first()L.last()L.insert(item)L.replace(item)L.remove()L.append(item)L.index(item)L.insert(index, item)item = L[index] L[index] = newValueL.remove(index)Positional-based operationsContent-based operationsIndex-based operationsTo start the lab: Download and unzip the file lab7.zipPart A: The positionalList.py file contains a LinkedPositionalList class, which uses acircular, doubly-linked list with a sentinel (or header) node to reduce the number of “special cases” (e.g.,inserting first item in an empty list). An empty list looks like:previous data next_head_cursor_lastItemPos_size0Empty LinkedPositionalListobjecta) Why would a singly-linked list be bad choice for implementing a positional-based list ADT?b) Why would a circular, doubly-linked list with a sentinel (or header) node eliminate the “special cases” of "inserting first item in an empty list" or "removing the last item from a list."After answering the above questions, raise you hand and explain your answers.Data Structures (810:052) Lab 7 Name:_________________Lab 7 - 1Part B: The position-base operations described in Tables 16.4 and 16.5 of the Lambert textbook treat thecursor poorly. For example, the remove operation is described as:“Precondition: There have been no intervening insert or remove operations since the most recent nextor previous operation. Removes the item returned by the most recent next or previous.”Typically, if a method has a precondition, then there is another method to check the precondition. Forexample, the next operation has a precondition: “hasNext returns True.” However, the removeoperation’s precondition cannot be checked without the user application maintaining a list of preceedingoperations -- a bad design! The problem occurs because the insert and remove operations leave thecursor in an undefined state.Part B: Instead of thinking of a cursor between to list items, let's have a current item which is alwaysdefined as long as the list is not empty. We will insert and delete relative to the curent item.Removes and returns the current item. Making the next item the currentitem if one exists; otherwise the tail item in the list is the current item. Precondition: the list is not empty.L.remove()Replaces the current item by the newValue. Precondition: the list is notempty.L.replace(newValue)Inserts item before the current item, or as the only item if the list is empty.The new item is the current item.L.insertBefore(item)Inserts item after the current item, or as the only item if the list is empty.The new item is the current item.L.insertAfter(item)Makes the last item the current item. Precondition: the list is not empty.L.last()Makes the first item the current item. Precondition: the list is not empty.L.first()Precondition: hasPrevious returns True. Postcondition: The current itemis has moved left one itemL.previous()Returns True if the current item has a previous item; otherwise returnFalse. Precondition: the list is not empty.L.hasPrevious()Precondition: hasNext returns True. Postcondition: The current item ishas moved right one itemL.next()Returns True if the current item has a next item; otherwise return False.Precondition: the list is not empty.L.hasNext()Returns the current item without removing it or changing the currentposition. Precondition: the list is not empty.L.getItem()Description of operationPositional-based operationsThe mypositionalList.py file contains a LinkedPositionalList class, which uses adoubly-linked list with a header node and trailer node to reduce the number of “special cases” (e.g., insertingfirst item in an empty list). An empty list looks like:previous data next previous data next_header_current_trailer_size0After implementing and testing your LinkedPositionalList class, raise you hand and demonstrate yourcode.Data Structures (810:052) Lab 7 Name:_________________Lab 7 -


View Full Document

UNI CS 1520 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?