0%

Algorithm - 0x01 - The way of thinking

Posted on Edited on In

Data storage structure

Two basic structures of data strage are Array and LinkedList.
All other structures are developed from these two structures.

Action on Data structure

traversal

Array traversal:

1
2
3
4
5
void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // iteration arr[i]
    }
}

Single node linkedlist traversal:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* Single Node */
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // iteration p.val
    }
}

void traverse(ListNode head) {
    // recursion head.val
    traverse(head.next)
}

Binary tree:

1
2
3
4
5
6
7
8
9
10
11
12
13
/* Binary Tree */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    // pre order
    traverse(root.left)
    // in order
    traverse(root.right)
    // post order
}

Tree:

1
2
3
4
5
6
7
8
9
10
/* N branch tree */
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child)
}