Abstract Data Type - Unsorted List

and Sorted List (Array-based

Implementation]
CSE225: Data Structures and Algorithms
List Definitions
Linear relationship
Each element except the first has a unique predecessor, and
Each element except the last has a unique successor.
Length
The number of items in a list;
The length can vary over time.

2
List Definitions
Unsorted list
A list in which data items are placed in no particular order;
the only relationship between data elements is the list
predecessor and successor relationships.
Sorted list
A list that is sorted by the value in the key;
There is a semantic relationship among the keys of the
items in the list.
Key
The attributes that are used to determine the logical order
of the list.

3
Data vs. Information
Data Information
• 6.34 SIRIUS SATELLITE RADIO INC.

• 6.45 $7.20
• 6.39 $7.00
• 6.62 $6.80
• 6.57
Stock Price
$6.60
• 6.64 $6.40

• 6.71 $6.20

• 6.82 $6.00

• 7.12 $5.80
1 2 3 4 5 6 7 8 9 10
• 7.06
Last 10 Days
Unsorted List Sorted List
22 12
12 14
46 22
35 35
14 46
. .
. .
. .
. .
Sorted List

ID Name Address
22 Jack Black 120 S. Virginia Street
45 Simon Graham 6762 St Petersburg
59 Susan O'Neal 1807 Glenwood, Palm Bay
66 David peterson 1207 E. Georgetown

Key
Abstract Data Type (ADT)

• A data type whose properties (domain and

operations) are specified independently of any
particular implementation.

7
Data from 3 different levels

• Application (or user) level: Why

modeling real-life data in a specific context.

• Logical (or ADT) level: What

abstract view of the domain and operations.

How
• Implementation level:
specific representation of the structure to hold the data items, and the
coding for operations.

8
Specification of UnsortedType
Structure: The list has a special property called the current position - the
position of the last element accessed by GetNextItem during an
iteration through the list. Only ResetList and GetNextItem affect
the current position.
Operations (provided by Unsorted List ADT):
MakeEmpty
Function Initializes list to empty state.
Precondition
Postcondition List is empty.
Boolean IsFull
Function Determines whether list is full.
Precondition List has been initialized.
Postcondition Returns true if list is full and false otherwise.
Specification of UnsortedType
int LengthIs
Function Determines the number of elements in list.
Precondition List has been initialized.
Postcondition Returns the number of elements in list.
RetrieveItem (ItemType &item, Boolean &found)
Function Retrieves list element whose key matches item's key (if present).
Precondition List has been initialized. Key member of item is initialized.
Postcondition If there is an element someItem whose key matches item's key,
then found = true and item is a copy of someItem; otherwise
found = false and item is unchanged. List is unchanged.
InsertItem (ItemType item)
Function Adds item to list.
Precondition List has been initialized. List is not full. item is not in the list.
Postcondition item is in the list. List is changed.
Specification of Unsorted Type
DeleteItem (ItemType item)
Function Deletes the element whose key matches item's key.
Precondition List has been initialized. Key member of item is initialized. One
and only one element in list has a key matching item's key.
Post-condition No element in list has a key matching item's key.
ResetList
Function Initializes current position for an iteration through the list.
Precondition List has been initialized.
Post-condition Current position is prior to first element in list.
GetNextItem (ItemType &item)
Function Gets the next element in list.
Precondition List has been initialized. Current position is defined. Element at
current position is not last in list.
Post-condition Current position is updated to next position. item is a copy of
element at current position.
Specification of SortedType
Structure: The list has a special property called the current position - the
position of the last element accessed by GetNextItem during an
iteration through the list. Only ResetList and GetNextItem affect
the current position.
Operations (provided by Unsorted List ADT):
MakeEmpty
Function Initializes list to empty state.
Precondition
Post-condition List is empty.
Boolean IsFull
Function Determines whether list is full.
Precondition List has been initialized.
Post-condition Returns true if list is full and false otherwise.
Specification of SortedType
int LengthIs
Function Determines the number of elements in list.
Precondition List has been initialized.
Postcondition Returns the number of elements in list.
RetrieveItem (ItemType& item, Boolean& found)
Function Retrieves list element whose key matches item's key (if present).
Precondition List has been initialized. Key member of item is initialized.
Postcondition If there is an element someItem whose key matches item's key,
then found = true and item is a copy of someItem; otherwise
found = false and item is unchanged. List is unchanged.
InsertItem (ItemType item)
Function Adds item to list.
Precondition List has been initialized. List is not full. item is not in list.
Postcondition item is in list. List is still sorted.
Specification of SortedType
DeleteItem (ItemType item)
Function Deletes the element whose key matches item's key.
Precondition List has been initialized. Key member of item is initialized. One
and only one element in list has a key matching item's key.
Postcondition No element in list has a key matching item's key. List is still
sorted.
ResetList
Function Initializes current position for an iteration through the list.
Precondition List has been initialized.
Postcondition Current position is prior to first element in list.
GetNextItem (ItemType& item)
Function Gets the next element in list.
Precondition List has been initialized. Current position is defined. Element at
current position is not last in list.
Postcondition Current position is updated to next position. item is a copy of
element at current position.
unsortedtype.h
#ifndef UNSORTEDTYPE_H_INCLUDED
#define UNSORTEDTYPE_H_INCLUDED

const int MAX_ITEMS = 10;

template <class ItemType>

class UnsortedType
{
public :
UnsortedType();
void MakeEmpty();
bool IsFull();
int LengthIs();
void InsertItem(ItemType);
void DeleteItem(ItemType);
void RetrieveItem(ItemType&, bool&);
void ResetList();
void GetNextItem(ItemType&);
private:
int length;
ItemType info[MAX_ITEMS];
int currentPos;
};
#endif // UNSORTEDTYPE_H_INCLUDED
sortedtype.h
#ifndef SORTEDTYPE_H_INCLUDED
#define SORTEDTYPE_H_INCLUDED

const int MAX_ITEMS = 5;

template <class ItemType>

class SortedType
{
public :
SortedType();
void MakeEmpty();
bool IsFull();
int LengthIs();
void InsertItem(ItemType);
void DeleteItem(ItemType);
void RetrieveItem(ItemType&, bool&);
void ResetList();
void GetNextItem(ItemType&);
private:
int length;
ItemType info[MAX_ITEMS];
int currentPos;
};
#endif // SORTEDTYPE_H_INCLUDED
unsortedtype.cpp
#include “unsortedType.h" template <class ItemType>
template <class ItemType> int UnsortedType<ItemType>::LengthIs()
UnsortedType<ItemType>::UnsortedType() {
{ return length;
length = 0; }
currentPos = -1; template <class ItemType>
} void UnsortedType<ItemType>::ResetList()
template <class ItemType> {
void
currentPos = -1;
UnsortedType<ItemType>::MakeEmpty()
}
{
length = 0; template <class ItemType>

currentPos = -1; void UnsortedType<ItemType>::GetNextItem(ItemType&

item)
}
{
template <class ItemType>
currentPos++;
bool UnsortedType<ItemType>::IsFull()
item = info [currentPos] ;
{
}
return (length == MAX_ITEMS);
}
unsortedtype.cpp
#include “unsortedType.h" template <class ItemType>
template <class ItemType> int UnsortedType<ItemType>::LengthIs()
UnsortedType<ItemType>::UnsortedType() {
{ return length; O(1)
length = 0;
currentPos = -1;
O(1) }
template <class ItemType>
} void UnsortedType<ItemType>::ResetList()
template <class ItemType> {
void UnsortedType<ItemType>::MakeEmpty()
{
currentPos = -1; O(1)
O(1)
}
length = 0;
template <class ItemType>
}
void UnsortedType<ItemType>::GetNextItem(ItemType&
template <class ItemType> item)
bool UnsortedType<ItemType>::IsFull() {
{
return (length == MAX_ITEMS);
currentPos++;
item = info [currentPos] ;
O(1)
}
O(1) }
sortedtype.cpp
#include "sortedtype.h" template <class ItemType>
template <class ItemType> int SortedType<ItemType>::LengthIs()
SortedType<ItemType>::SortedType() {
{ return length;
length = 0; }
currentPos = -1; template <class ItemType>
} void SortedType<ItemType>::ResetList()
template <class ItemType> {
void SortedType<ItemType>::MakeEmpty()
currentPos = -1;
{
}
length = 0;
template <class ItemType>
}
void SortedType<ItemType>::GetNextItem(ItemType&
template <class ItemType> item)
bool SortedType<ItemType>::IsFull() {
{ currentPos++;
return (length == MAX_ITEMS); item = info [currentPos];
} }
sortedtype.cpp
#include "sortedtype.h" template <class ItemType>
template <class ItemType> int SortedType<ItemType>::LengthIs()
SortedType<ItemType>::SortedType() {
{ return length; O(1)
length = 0;
currentPos = -1;
O(1) }
template <class ItemType>
} void SortedType<ItemType>::ResetList()
template <class ItemType> {
void SortedType<ItemType>::MakeEmpty()
{
currentPos = -1; O(1)
O(1)
}
length = 0;
template <class ItemType>
}
void SortedType<ItemType>::GetNextItem(ItemType&
template <class ItemType> item)
bool SortedType<ItemType>::IsFull() {
{
return (length == MAX_ITEMS);
currentPos++;
item = info [currentPos];
O(1)
}
O(1) }
Inserting an Item into Unsorted List

[0] 6 [0] 6
[1] 3 [1] 3
[2] 4 [2] 4
[3] 1 [3] 1
[4] 2 [4] 2
. [5] 5
. .
. Logical .
garbage Logical
. . garbage
[MAX_ITEMS - 1] [MAX_ITEMS - 1]

length = 5 length = 6

Insert 5
unsortedtype.cpp
template <class ItemType>
void UnsortedType<ItemType>::InsertItem(ItemType item)
{
info[length] = item;
length++;
}
unsortedtype.cpp
template <class ItemType>
void UnsortedType<ItemType>::InsertItem(ItemType item)
{
info[length] = item;
}
length++;
O(1)
Inserting an Item into Sorted List

[0] 1 [0] 1
[1] 2 [1] 2
[2] 4 [2] 4
[3] 6 [3] 5
[4] 8 [4] 6
. [5] 8
. .
. Logical .
garbage Logical
. . garbage
[MAX_ITEMS - 1] [MAX_ITEMS - 1]

length = 5 length = 6

Insert 5
sortedtype.cpp
template <class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
int location = 0;
bool moreToSearch = (location < length);

while (moreToSearch)
// This will identify the location where the item will be stored
{
if(item > info[location])
{
location++;
moreToSearch = (location < length);
}
else if(item < info[location])
moreToSearch = false;
}
for (int index = length+1; index > location; index--)
info[index] = info[index - 1];
info[location] = item;
length++;
}
sortedtype.cpp
template <class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
int location = 0;
bool moreToSearch = (location < length);

while (moreToSearch)
{
O(N)
if(item > info[location])
{
location++;
moreToSearch = (location < length);
}
else if(item < info[location])
O(N)
moreToSearch = false;
}
for (int index = length; index > location; index--)
info[index] = info[index - 1];
info[location] = item;
length++;
O(N)
}
Deleting an Item from Unsorted List

[0] 6 [0] 6
[1] 3 [1] 3
[2] 4 [2] 4
[3] 1 [3] 5
[4] 2 [4] 2
[5] 5 .
. .
. Logical
. Logical garbage
. garbage .
[MAX_ITEMS - 1] [MAX_ITEMS - 1]

length = 6 length = 5

Delete 1
unsortedtype.cpp
template <class ItemType>
void UnsortedType<ItemType>::DeleteItem(ItemType item)
{
int location = 0;

while (item != info[location])

location++;

info[location] = info[length - 1];

length--;
}
unsortedtype.cpp
template <class ItemType>
void UnsortedType<ItemType>::DeleteItem(ItemType item)
{
int location = 0;
while (item != info[location]) O(N)
location++;
info[location] = info[length - 1]; O(N)
}
length--;
O(1)
Deleting an Item from Sorted List

[0] 1 [0] 1
[1] 2 [1] 2
[2] 4 [2] 4
[3] 5 [3] 6
[4] 6 [4] 8
[5] 8 .
. .
. . Logical
Logical garbage
. garbage .
[MAX_ITEMS - 1] [MAX_ITEMS - 1]

length = 6 length = 5

Delete 5
sortedtype.cpp
template <class ItemType>
void SortedType<ItemType>::DeleteItem(ItemType item)
{
int location = 0;

while (item != info[location])

location++;

for (int index = location + 1; index < length; index++)

info[index - 1] = info[index];
length--;
}
sortedtype.cpp
template <class ItemType>
void SortedType<ItemType>::DeleteItem(ItemType item)
{
int location = 0;

while (item != info[location])

location++;
O(N)
for (int index = location + 1; index < length; index++)
O(N)
info[index - 1] = info[index];
length--; O(N)
}
Retrieving an Item from Unsorted List
• Visit each element in the list, one by one, until the item is
found.
unsortedtype.cpp
template <class ItemType>
void UnsortedType<ItemType>::RetrieveItem(ItemType& item, bool &found)
{
int location = 0;
bool moreToSearch = (location < length);
found = false;
while (moreToSearch && !found)
{
if(item == info[location])
{
found = true;
item = info[location];
}
else
{
location++;
moreToSearch = (location < length);
}
}
}
unsortedtype.cpp
template <class ItemType>
void UnsortedType<ItemType>::RetrieveItem(ItemType& item, bool &found)
{
int location = 0;
bool moreToSearch = (location < length);
found = false;
while (moreToSearch && !found)
{
O(N)
if(item == info[location])
{
found = true;
item = info[location];
}
else
{
location++;
moreToSearch = (location < length);
}
}
}
Retrieving an Item from Sorted List
• Find 84

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Retrieving an Item from Sorted List
• Find 84

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

• Step 1
Retrieving an Item from Sorted List
• Find 84

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first mid last

=(0+14)/2

• Step 1
Retrieving an Item from Sorted List
• Find 84

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first mid last

=(0+14)/2

• Step 1
Retrieving an Item from Sorted List
• Find 84

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

• Step 2
Retrieving an Item from Sorted List
• Find 84

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first mid last

=(8+14)/2

• Step 2
Retrieving an Item from Sorted List
• Find 84

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first mid last

=(8+14)/2

• Step 2
Retrieving an Item from Sorted List
• Find 84

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

• Step 3
Retrieving an Item from Sorted List
• Find 84

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

mid
=(8+10)/2
• Step 3
Retrieving an Item from Sorted List
• Find 84

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

mid
=(8+10)/2
• Step 3
Retrieving an Item from Sorted List
• Find 84

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

• Step 4
Retrieving an Item from Sorted List

• Find 84

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

mid
=(10+10)/2

• Step 4
• 84 found at the midpoint
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

• Step 1
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first mid last

=(0+14)/2

• Step 1
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first mid last

=(0+14)/2

• Step 1
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

• Step 2
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first mid last

=(8+14)/2

• Step 2
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first mid last

=(8+14)/2

• Step 2
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

• Step 3
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

mid
=(8+10)/2
• Step 3
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

mid
=(8+10)/2
• Step 3
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

• Step 4
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

first last

mid
=(10+10)/2
• Step 4
Retrieving an Item from Sorted List
• Find 73

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

last first

• Step 5
• last < first (indicates the absence of the item)
Retrieving an Item from Sorted List
• What is the number of steps required?

Array size expressed as 2a

N 2(x)
N/2 2(x-1)
N/4 2(x-2)
N/8 2(x-3)
. .
. .
. .
. .
4 22
2 21
1 20
Retrieving an Item from Sorted List
• What is the number of steps required?

Array size expressed as 2a

N 2(x)
N/2 2(x-1)
N/4 2(x-2)
N/8 2(x-3) Or,
. .
. . Or simply,
. .
. .
4 22
2 21
1 20
sortedtype.cpp
template <class ItemType>
void SortedType<ItemType>::RetrieveItem(ItemType& item, bool& found)
{
int midPoint, first = 0, last = length - 1;
bool moreToSearch = (first <= last);
found = false;
while (moreToSearch && !found)
{
midPoint = (first + last) / 2;
if(item < info[midPoint])
{
last = midPoint - 1;
moreToSearch = (first <= last);
}
else if(item > info[midPoint])
{
first = midPoint + 1;
moreToSearch = (first <= last);
}
else
{
found = true;
item = info[midPoint];
}
}
}
sortedtype.cpp
template <class ItemType>
void SortedType<ItemType>::RetrieveItem(ItemType& item, bool& found)
{
int midPoint, first = 0, last = length - 1;
bool moreToSearch = (first <= last);
found = false;
while (moreToSearch && !found)
{
midPoint = (first + last) / 2;
if(item < info[midPoint])
O(logN)
{
last = midPoint - 1;
moreToSearch = (first <= last);
}
else if(item > info[midPoint])
{
first = midPoint + 1;
moreToSearch = (first <= last);
}
else
{
found = true;
item = info[midPoint];
}
}
}