Fundamentals of Python: From First Programs Through Data StructuresObjectivesObjectives (continued)Overview of ListsOverview of Lists (continued)Slide 6Using ListsIndex-Based OperationsContent-Based OperationsPosition-Based OperationsPosition-Based Operations (continued)Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Interfaces for ListsInterfaces for Lists (continued)Applications of ListsHeap-Storage ManagementHeap-Storage Management (continued)Organization of Files on a DiskSlide 24Organization of Files on a Disk (continued)Implementation of Other ADTsIndexed List ImplementationsAn Array-Based Implementation of an Indexed ListA Linked Implementation of an Indexed ListTime and Space Analysis for the Two ImplementationsTime and Space Analysis for the Two Implementations (continued)Slide 32Implementing Positional ListsThe Data Structures for a Linked Positional ListThe Data Structures for a Linked Positional List (continued)Slide 36Methods Used to Navigate from Beginning to EndSlide 38Methods Used to Navigate from Beginning to End (continued)Slide 40Methods Used to Navigate from End to BeginningInsertions into a Positional ListRemovals from a Positional ListTime and Space Analysis of Positional List ImplementationsIteratorsIterators (continued)Using an Iterator in PythonUsing an Iterator in Python (continued)Implementing an IteratorCase Study: Developing a Sorted ListCase Study: Developing a Sorted List (continued)Slide 52Slide 53SummarySummary (continued)Fundamentals of Python:From First Programs Through Data Structures Chapter 16Linear Collections: ListsFundamentals of Python: From First Programs Through Data Structures 2ObjectivesAfter completing this chapter, you will be able to:•Explain the difference between index-based operations on lists and position-based operations on lists•Analyze the performance trade-offs between an array-based implementation and a linked implementation of index-based listsFundamentals of Python: From First Programs Through Data Structures 3Objectives (continued)•Analyze the performance trade-offs between an array-based implementation and a linked implementation of positional lists•Create and use an iterator for a linear collection•Develop an implementation of a sorted listFundamentals of Python: From First Programs Through Data Structures 4Overview of Lists•A list supports manipulation of items at any point within a linear collection•Some common examples of lists:–Recipe, which is a list of instructions–String, which is a list of characters–Document, which is a list of words–File, which is a list of data blocks on a disk•Items in a list are not necessarily sorted•Items in a list are logically contiguous, but need not be physically contiguous in memoryFundamentals of Python: From First Programs Through Data Structures 5Overview of Lists (continued)•Head: First item in a list•Tail: Last item in a list•Index: Each numeric position (from 0 to length – 1)Fundamentals of Python: From First Programs Through Data Structures 6Overview of Lists (continued)Fundamentals of Python: From First Programs Through Data Structures 7Using Lists•Universal agreement on the names of the fundamental operations for stacks and queues but for lists, there are no such standards–The operation of putting a new item in a list is sometimes called “add” and sometimes “insert”•Broad categories of operations on lists:–Index-based operations–Content-based operations–Position-based operationsFundamentals of Python: From First Programs Through Data Structures 8Index-Based Operations•Index-based operations manipulate items at designated indices within a list–In array-based lists, these provide random access•From this perspective, lists are called vectors or sequencesFundamentals of Python: From First Programs Through Data Structures 9Content-Based Operations•Content-based operations are based not on an index, but on the content of a list–Usually expect an item as an argument and do something with it and the listFundamentals of Python: From First Programs Through Data Structures 10Position-Based Operations•Position-based operations: Performed relative to currently established position or cursor within a list–Allow user to navigate the list by moving this cursor•In some programming languages, a separate object called an iterator provides these operations•Places in which a positional list’s cursor can be:–Just before the first item–Between two adjacent items–Just after the last itemFundamentals of Python: From First Programs Through Data Structures 11Position-Based Operations (continued)Fundamentals of Python: From First Programs Through Data Structures 12Position-Based Operations (continued)•When a positional list is first instantiated or when it becomes empty, its cursor is undefinedFundamentals of Python: From First Programs Through Data Structures 13Position-Based Operations (continued)Fundamentals of Python: From First Programs Through Data Structures 14Position-Based Operations (continued)Fundamentals of Python: From First Programs Through Data Structures 15Position-Based Operations (continued)Fundamentals of Python: From First Programs Through Data Structures 16Position-Based Operations (continued)Fundamentals of Python: From First Programs Through Data Structures 17Position-Based Operations (continued)Fundamentals of Python: From First Programs Through Data Structures 18Interfaces for ListsFundamentals of Python: From First Programs Through Data Structures 19Interfaces for Lists (continued)Fundamentals of Python: From First Programs Through Data Structures 20Applications of Lists•Lists are probably the most widely used collections in computer science•In this section, we examine two important applications:–Heap-storage management–Disk file managementFundamentals of Python: From First Programs Through Data Structures 21Heap-Storage Management•Object heap: Area of memory from which PVM allocates segments for new data objects•When an object no longer can be referenced from a program, PVM can return that object’s memory segment to the heap for use by other objects•Heap-management schemes can have a significant impact on an application’s overall performance–Especially if the application creates and abandons many objects during the course of its executionFundamentals of Python: From First Programs Through Data Structures 22Heap-Storage Management (continued)•Contiguous blocks of free