Abstract Data Types

Main abstract data types:

• Lists
• Maps/Dictionaries
• Sets
• Stacks
• Queues
• Trees

These are basic types of data structures (although some of the data types above may utilize other data types in their implementation, e.g., a linked list structure used to store a dictionary).

Lists

Array list data type

Main article: ArrayLists

Dynamically expanding array list type. The best way to implement a dynamically expanding array is to have it double in size when the array of capacity n reaches n+1 items. Increasing by a fixed amount incurs an O(n^2) cost.

We also want to dynamically shrink the array, but at a different multiple than 1/2 (otherwise we have a single size change that can toggle the size of the array, incurring O(n) cost with each operation.)

Array list interface

The array list type should implement the following methods:

• size
• is empty
• search
• append/insert
• remove/pop
• get
• set
• minimum
• maximum

Array list computational complexity

Operation	Array list	Array list, sorted
Search(L,k)	O(n)	O(log n)
Insert(D,x)	O(1)	O(n)
Delete(L,x)	O(1)*	O(n)
Successor(L,x)	O(n)	O(1)
Predecessor(L,x)	O(n)	O(1)
Minimum(L)	O(n)	O(1)
Maximum(L)	O(n)	O(1)

Linked list data type

Main: Linked Lists

Linked data structures: much/most of the data in a linked list data type is dedicated to links/addresses

Main differences in implementation of linked list types are in the links themselves. Doubly linked lists have simpler algorithms and are easier to implement, but come with the extra overhead of additional pointers.

Linked list interface

The linked list type should implement the following methods:

• size
• isEmpty
• addFirst
• addLast
• removeFirst
• removeLast
• get(i)

Linked list computational complexity

Speed of operations on sorted and unsorted linked lists:

Operation	Singly Linked List	Doubly Linked List	Singly Linked List, Sorted	Doubly Linked List, Sorted
Search(L,k)	O(n)	O(n)	O(n)	O(n)
Insert(D,x)	O(1)	O(1)	O(n)	O(n)
Delete(L,x)	O(n)*	O(1)	O(n)*	O(1)
Successor(L,x)	O(n)	O(n)	O(1)	O(1)
Predecessor(L,x)	O(n)	O(n)	O(n)*	O(1)
Minimum(L)	O(n)	O(n)	O(1)	O(1)
Maximum(L)	O(n)	O(n)	O(1)*	O(1)

Stacks and Queues

Main article: StacksQueues

Stacks

Stacks are LIFO (last in, first out) data structures. They have fast O(1) access to add to and remove from the top of the stack. No random access to the inner elements of the stack is provided. Stacks can be implemented using arrays (bottom of stack is beginning of array, top of stack is last element in array) or a using linked list structure.

Stack interface

Any standard Stack data structure should implement the following methods:

• size() - get the number of elements currently in the stack
• isEmpty() - returns true if stack is empty
• push() - add the given item to the top of the stack
• pop() - remove the top item in the stack and return it
• peek() - return reference to top item in stack, but do not remove it

Queues

Queues are FIFO (first in, first out) data structures. They have fast O(1) access to add to the back and remove from the front. No random access to the inner elements of the queue is provided. Queues are sometimes referred to as "priority queues". They can be implemented using arrays (with floating pointers to the beginning and end of the queue that rotate through the array), or using linked lists. Circular linked lists may prove useful here as well.

Queue interface

Like stacks, queues don't need to implement a lot of methods. Here's what the queue interface looks like:

• size() - get the number of elements in the queue
• isEmpty() - returns true if queue is empty
• enqueue()/add() - add the element to the back of the queue
• dequeue()/remove() - remove and return the element at the front of the queue
• peek() - return a reference to the first item in the queue, but do not remove it

Optional:

• rotate

Stack and queue computational complexity

Operation	Stack	Queue
Add/Push/Enqueue	O(1)	O(1)
Remove/Pop/Dequeue	O(1)	O(n) if singly linked list, since have to move backwards from tail. O(1) if circular linked list. O(1) if array.
Peek	O(1)	O(1)
Size	O(1)	O(1)

Deques

Deques are double-ended queues. Like queues, they are a FIFO data structure, but they provide access at both ends.

The deque offers addFront() and addBack() methods (or, as in Python, the push() and push_left() method.)

The deque also offers removeFront() and removeBack() methods.

first()/last() offer a peek() method for either end of the deque.

Dictionary/Map

The basic idea behind the dictionary or map concept is that it enables looking up data by value. Thus, you can pass it a value and have the corresponding location in the data container returned, removed, etc.

Dictionary data type

Dictionary data type is covered by Skiena in Chapter 3 Section 3. Dictionaries provide a means of storing values, and accessing them by their content. You put an item into a dictionary so that you can find it later when you need it.

Dictionary interface

A dictionary should support the following operations:

• search
• insert
• delete
• max or min
• predecessor or successor