Array-Based Lists
• List
– Collection of elements of same type
• Length of a list
– Number of elements in the list
• Many operations may be performed on a list
– Create the list. The list is initialized to an empty state
– Determine whether the list is empty.
– Determine whether the list is full.
– Find the size of the list.
– Destroy, or clear, the list.
– Insert an item in the list at the specified location.
– Remove an item from the list at the specified location.
– Replace an item at the specified location with another item.
– Retrieve an item from the list from the specified location.
– Search the list for a given item.
• Store a list in the computer’s memory
– Using an array
Data Structures Using C++ 2E 1
Array-Based Lists (cont’d.)
• Three variables needed to maintain and
process a list in an array
– The array holding the list elements
– A variable to store the length of the list
• Number of list elements currently in the array
– A variable to store array size
• Maximum number of elements that can be stored in
the array
• Desirable to develop generic code
– Used to implement any type of list in a program
– Make use of templates
Data Structures Using C++ 2E 2
Array-Based Lists (cont’d.)
• Define class implementing list as an abstract
data type (ADT)
Data Structures Using C++ 2E 4
arrayList Example:
length = 5
maxSize = 7
Array-Based Lists (cont’d.)
• Definitions of functions isEmpty and
isFull
Data Structures Using C++ 2E 6
Array-Based Lists (cont’d.)
• Definitions of functions listSize and
maxListSize
Data Structures Using C++ 2E 7
Array-Based Lists (cont’d.)
• Template print (outputs the elements of the
list) and template isItemAtEqual
length = 5
maxSize = 7
Data Structures Using C++ 2E 8
Array-Based Lists (cont’d.)
• Template insertAt
Data Structures Using C++ 2E 9
Template insertAt cont..
Array-Based Lists (cont’d.)
• Template insertEnd and template
removeAt
Data Structures Using C++ 2E 11
Array-Based Lists (cont’d.)
• Template replaceAt and template clearList
Data Structures Using C++ 2E 12
Array-Based Lists (cont’d.)
• Definition of the constructor and the destructor
Data Structures Using C++
13
2E
Array-Based Lists (cont’d.)
• Copy constructor
– Called when object passed as a (value) parameter
to a function
– Called when object declared and initialized using
the value of another object of the same type
– Copies the data members of the actual object into
the corresponding data members of the formal
parameter and the object being created
Data Structures Using C++
14
2E
Array-Based Lists (cont’d.)
• Copy constructor (cont’d.)
– Definition
Data Structures Using C++ 2E 15
Array-Based Lists (cont’d.)
• Overloading the assignment operator
– Definition of the function template
Data Structures Using C++ 2E 16
Array-Based Lists (cont’d.)
• Searching for an element
– Linear search example: determining if 27 is in the list
– Definition of the function template
FIGURE 3-32 List of seven elements
Data Structures Using C++ 2E 17
Array-Based Lists (cont’d.)
• Inserting an element
Data Structures Using C++
18
2E
Array-Based Lists (cont’d.)
• Removing an element
Data Structures Using C++
19
2E
Array-Based Lists (cont’d.)
TABLE 3-1 Time complexity of list operations
Data Structures Using C++ 2E 20
