Chapter 3 | Lists, Stacks, and Queues

1 Abstract Data Types (ADT)

Data type: Objects and operations

[example] int = {0,+-1,+-2,...,INT_MAX,INT_MIN} and

2 The List ADT

Objects: (item_0, item_1, ..., item_(n-1))

Operations:

• length
• print
• making an empty list
• finding the k-th
• inserting an item at k-th
• deleting
• finding next
• finding previous

Two Applications:

• The Polynomial ADT