The List ADT - Western University

[Pages:42]Topic 12

The List ADT

Objectives

? Examine list processing and various ordering techniques

? Define a list abstract data type ? Examine various list implementations ? Compare list implementations

9-2

Lists

? A list is a linear collection, like a stack and queue, but more flexible: adding and removing elements from a list does not have to happen at one end or the other

? We will examine three types of list collections:

? ordered lists ? unordered lists ? indexed lists

9-3

Ordered Lists

? Ordered list: Its elements are ordered by some inherent characteristic of the elements

? Examples:

? Names in alphabetical order ? Numeric scores in ascending order

? So, the elements themselves determine where they are stored in the list

9-4

Conceptual View of an Ordered List

front

rear

16 23 29 40 51 67 88

New values must be inserted

so that the ordering of the list

58

is maintained

9-5

Unordered Lists

? Unordered list : the order of the elements in the list is not based on a characteristic of the elements, but is determined by the user of the list

? A new element can be put ? on the front of the list ? or on the rear of the list ? or after a particular element already in the list

? Examples: shopping list, to-do list, ...

9-6

Conceptual View of an Unordered List

front

rear

New values can be inserted anywhere in the list

9-7

Indexed Lists

? Indexed list: elements are referenced by their numeric position in the list, called its index

? It's the position in the list that is important, and the user can determine the order that the items go in the list

? Every time the list changes, the position (index) of an element may change

? Example: current first-place holder in the bobsled race

9-8

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download