Class Notes (1,016,864)
CA (584,416)
U of S (3,517)
CMPT (50)
Lecture 8

# CMPT 115 Lecture 8: lists-notes

30 pages79 viewsWinter 2016

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

This preview shows pages 1-3. to view the full 30 pages of the document.
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 diﬀerence between lists and arrays.
2. Describe the typical list operations informally.
3. Deﬁne 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 diﬀerent 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 TheOperations............................................ 3
1.4 TheListInterface .......................................... 4
2 A Naive Array Implementation 7
2.1 DataStructure ............................................ 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 DataStructure ............................................ 12
3.2 The List Operation Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Time Complexity of List Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Linked List Extensions 22
4.1 CircularLinkedList ......................................... 22
4.2 DoublyLinkedLists ......................................... 23
1
###### You're Reading a Preview

Unlock to view full version

Only half of the first page are available for preview. Some parts have been intentionally blurred.

1 Overview of Lists
1.1 Introduction
Alist 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, modiﬁed.
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).A B 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 ﬁeld of the element is usually chosen as the key. E.g. if the
elements of a list are the structure:
Name
refToChar ﬁrstName
refToChar lastName
end Name
the lastName ﬁeld 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 ﬁxed size; we may have unlimited amount of data.
2. Arrays can be used in unconstrained ways; an unneeded intellectual burden.
1.2 Applications
2
###### You're Reading a Preview

Unlock to view full version

Only half of the first page are available for preview. Some parts have been intentionally blurred.

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 ﬁles.
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 ﬁle 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 ﬁnds the smallest block
of available memory that can fulﬁll 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
###### You're Reading a Preview

Unlock to view full version

#### Loved by over 2.2 million students

Over 90% improved by at least one letter grade.