An Executable Data Structures Cheat Sheet for Interviews
This cheat sheet uses Big O notation to express time complexity.
- For a reminder on Big O, see Understanding Big O Notation and Algorithmic Complexity.
- For a quick summary of complexity for common data structure operations, see the Big-O Algorithm Complexity Cheat Sheet.
Array
- Quick summary: a collection that stores elements in order and looks them up by index.
- Also known as: fixed array, static array.
- Important facts:
- Stores elements sequentially, one after another.
- Each array element has an index. Zero-based indexing is used most often: the first index is 0, the second is 1, and so on.
- Is created with a fixed size. Increasing or decreasing the size of an array is impossible.
- Can be one-dimensional (linear) or multi-dimensional.
- Allocates contiguous memory space for all its elements.
- Pros:
- Ensures constant time access by index.
- Constant time append (insertion at the end of an array).
- Cons:
- Fixed size that can't be changed.
- Search, insertion and deletion are
O(n). After insertion or deletion, all subsequent elements are moved one index further. - Can be memory intensive when capacity is underused.
- Notable uses:
- The String data type that represents text is implemented in programming languages as an array that consists of a sequence of characters plus a terminating character.
- Time complexity (worst case):
- Access:
O(1) - Search:
O(n) - Insertion:
O(n)(append:O(1)) - Deletion:
O(n)
- Access:
- See also:
Arrays are a primitive building block in most languages, here's how to initialize them:
1arr = [1, 2, 3]xxxxxxxxxx49
print(a)# Python does not have a native support for arrays, but has a List data structure# which mimicks the behavior of an array. The Python array module requires all# array elements to be of the same type. We implement our own below.class Array(object): """ sizeOfArray: denotes the total size of the array to be initialized arrayType: denotes the data type of the array arrayItems: values at each position of array """ def __init__(self, sizeOfArray, arrayType=int): self.sizeOfArray = len(list(map(arrayType, range(sizeOfArray)))) self.arrayItems = [arrayType(0)] * sizeOfArray # initialize array with zeroes def __str__(self): return " ".join([str(i) for i in self.arrayItems]) # function for search def search(self, keyToSearch): for i in range(self.sizeOfArray): if self.arrayItems[i] == keyToSearch: # brute-forcing return i # index at which element/key was found return -1 # if key not found, return -1 # function for inserting an elementOUTPUT
Results will appear here.