Data Structure Cheat Sheet

Basically, there’re two ways to store data strctures: array and linked list.
All other data strctures, such as queue, stack, graph, hashmap, tree, heap, etc, all can be implemented by array and linked list.

In python, list = array is implemented by dynamic array, when it used up the original assigned space, it will point to new sapce.

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;

    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     */
    Py_ssize_t allocated;
} PyListObject;

The array itself stores a list of of pointers. Therefore, while using list, need to cautious to some traps like: during initialization, all pointers are pointing to the same list

ls = [[]] * 5
ls[0].append(1)
print(ls)  #[[1], [1], [1], [1], [1]]

Also, time for popping the last element is O(1), but popping intermediate is O(n).

Tranverseal

Array

def traverse(arr):
    for x in arr:
    # do something

Linked List

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# iterative
def tranverse(head):
    while p:
        # do something
        p = p.next

# recursive
def tranverse(head):
    if not head:
        return
    # do something
    tranverse(head.next)

Binary Tree

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def tranverse(root):
    if not root:
        return
    # pre-order
    tranverse(root.left)
    # in-order
    tranverse(root.right)
    # post-order

Practice:

• 124.Binary Tree Maximum Path Sum
• 105.Construct Binary Tree from Preorder and Inorder Traversal
• 94.Binary Tree Inorder Traversal
• 106.Construct Binary Tree from Inorder and Postorder Traversal