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: ArrayList

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

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

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.

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.

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.