Class Notes (1,053,358)
CA (602,308)
U of S (3,567)
CMPT (50)
Lecture 8

CMPT 115 Lecture 8: lists-notes

30 pages84 viewsWinter 2016

Department
Computer Science
Course Code
CMPT 115
Professor
Jason Bowie
Lecture
8

Page:
of 30
Lists: An ADT for Sequential Data Organization
CMPT 115 lecture notes
Notes written by Michael Horsch, Mark Eramian, Ian McQuillan, Lingling Jin, and Dmytro Dyachuk
Objectives
After this topic, students are expected to
1. Describe the difference between lists and arrays.
2. Describe the typical list operations informally.
3. Define formal algorithm headers for list operations.
4. Draw the diagrams of the data structure of array-based lists as well as linked lists.
5. Describe the implementation of typical list operations in pseudocode.
6. Analyze the time complexities of typical list operations for array-based implementations and linked
implementations.
7. Critically assess the decision to apply either of the two list implementations in different applications
based on their properties of the data structures and the complexities of their operations.
Contents
1 Overview of Lists 2
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 The Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 The List Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 A Naive Array Implementation 7
2.1 Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 The List Operation Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Time Complexity of Array-based List Operations . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 A Linked Implementation 12
3.1 Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 The List Operation Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Time Complexity of List Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Linked List Extensions 22
4.1 Circular Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 Doubly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1
find more resources at oneclass.com
find more resources at oneclass.com
1 Overview of Lists
1.1 Introduction
A list is a sequentially organized collection of data.
Examples: A list of dates, a list of student records, a list of webpages, a list of songs, any real data.
The list contains data elements, e.g., student records, webpages, songs.
A list allows elements to be inserted, removed, searched-for, modified.
A list is an abstract design that can be implemented several ways.
A list is a sequence with a beginning (the head) and an end (the tail).
Unordered lists: no sequence relationship between elements.
Ordered lists: some attribute of the elements, called a key, determines the ordering.
Example 1 (A unordered list of integers).32 987 42 77 135
Example 2 (An ordered list of characters).AB D K Q R Y Z
In ordered lists, each element has a key that determines the proper order.
For atomic data elements, the key of an element is simply the element itself, e.g. integers, characters.
For compound data elements, one data field of the element is usually chosen as the key. E.g. if the
elements of a list are the structure:
Name
refToChar firstName
refToChar lastName
end Name
the lastName field might be used as the key; the list will be ordered by last name.
We will sometimes call the rest of the data element, other than the key, the satellite data.
1. Arrays have a fixed size; we may have unlimited amount of data.
2. Arrays can be used in unconstrained ways; an unneeded intellectual burden.
1.2 Applications
2
find more resources at oneclass.com
find more resources at oneclass.com
Each tab stores a URL to be displayed (among other data).
Need arbitrary number of tabs.
User can delete any tab at any time.
User can create a new tab at any time.
When the browser window is closed, the list is destroyed (its memory recycled).
In early computer systems, we used line editors to edit text files.
Let’s see the Linux line editor, ed in action!
A line editor can be implemented using a list of strings (character arrays) by storing one string per
line of the text file in the list.
Line editor commands:
insert line
delete line
edit line
etc
Each line editor operation can be implemented using list operations.
Some operating systems use lists to manage and organize the free memory blocks available on the heap.
Memory managers use a free list, where each element consists of:
The starting address of a memory block.
The size of the memory block.
Elements are ordered by starting address.
When programmer calls new, the memory system traverses the free list, and finds the smallest block
of available memory that can fulfill the request.
Elements can be split into two nodes to make smaller blocks, or adjacent elements can be combined to
make larger blocks, etc.
Details of other exciting operating system mechanics such as this can be learned in CMPT 332 and
432.
1.3 The Operations
Insert a new element into a list.
Delete an element from a list.
Retrieve (search for and return) an element in the list.
Create a new empty list.
Destroy the list, and any elements in it.
Check if a list is empty or not.
Find out how many elements are in the list.
3
find more resources at oneclass.com
find more resources at oneclass.com

Loved by over 2.2 million students

Over 90% improved by at least one letter grade.