Java 数据结构总结 (未完成)

Array

A data structure to store elements of same type in a contiguous locations. The size of an array must be provided before storing data.
Operation time complexity:

  • Accessing time: O(1). Because data are stored in contiguous locations. So accessing an element at i in memory, we can just go to start + i * element size.
  • Search time: O(n) for sequential search; O(logn) for binary search in sorted array.
  • Insertion time: Worst case is O(n) if we want to insert the element at the beginning of the element beacuse it requires shifting all the elements to the right.
  • Deletion time: Worst case is O(n) if deletion happens at the beginning of the array because it requires all elements after it shifting left.
  • Good performance for retrieval operations and bad in manipulation.

Stack

An abstract data type that serves as a collection of elements, with two principal operations: push and pop.
"First in last out" - implemented by array or linked list.

  • Accessing time: O(n) to access a node in the middle of the stack.
  • Search time: O(n) for sequential search;
  • Insertion time: O(1) at top of stack.
  • Deletion time: O(1) at top of stack.

Queue

An abstract datatype taht serves as a collection of elements, with two principal operations, enqueue and dequeue.
"First in first out" - implemented by array or linked list.

  • Accessing time: O(n) to access a node in the middle of the stack.
  • Search time: O(n) for sequential search;
  • Insertion time: O(1) at end of queue.
  • Deletion time: O(1) at start of queue.

Linked List

Linear data structure where each element is a seperate object. The Linked List is a list consists of nodes. Each node contains data and a reference indicates its next node in the list.

Singly Linked List

Each element has data and a refernce to next node and the last node has address reference as null.

Doubly Linked List

Each element has two address refernces, one points to the next node while the other points to the previous node.

We can traverse in both directions and for deletion; the delete operation in DLL is more efficient if pointer to the node to be deleted is given; We can easily access previous node.

Circular Linked List

All nodes in the list are conneted to form a circle. No null at the end of CLL and any node can be made as start of the CLL.

  • Accessing time: O(n). Because every time we have to start from the head of the linked list, and access the next node using the reference till we find the desired element.

  • Search time: O(n). The process is the same as that of accessing data.

  • Insertion time: O(1). If we are at the position where we will insert an element.

  • Deletion time: Also O(1).

  • Array vs Linked List

    • array must has a size when initialzie, while linked list keeps increasing size when adding nodes into the list; Linked list is space saving / dynamic size.
    • get an element from the array costs constant time, while it takes O(n) in a linked list; Random access is not allowed in linekd list
    • insertion or deletion cost O(n) in array, while only constant time in linked list.

Tree

Tree has hierarchical data structures. It is represented by the pointer to the topmost node in the tree.

Binary Tree

A binary tree node contains the data, a pointer to the left child and a pointer to the right child.

Ways of traversal:

  • BFS: Level-order traversal; - using queue

  • DFS: Pre-order: Root-Left-Right; In-order: Left-Root-Right; Post-order: Left-Right-Root - recursion or stack

  • Time Complexity: O(n)

  • Properties:

    • Maximum number of nodes in level i: 2^(i - 1);
    • Maimum number of nodes 2^(h - 1), h is the height of tree. Height - maximum number of edges from root to leaf;
    • Minimum possible height: ceil(log2(n+1)) - 1.
    • Number of leaf nodes is always one more than the nodes with two children ???
Binary Search Tree
  • Any parent node must have at most two children

  • For a root node, all nodes in its left subtree must be smaller than it, and all nodes in its right subtree must be larger than it.

  • Left subtree and right subtree must also be binary search tree

  • Searching time: O(h)

  • Inserting time: O(h). Worst case, if insert to the leaf node. ???

  • Deletion time: O(h).

    • When deleting a leaf node, set left or right pointer of its parent to be null
    • When deleting a node with either left subtree or right subtree, set left or right pointer of its parents to either its left subtree or right node.
    • When deleting a node having both left and right subtree, replace the node with its predecessor node, and delete the predecessor node.
  • Self-Balancing tree must make sure the height of the BST tree is O(logn).

  • Moderate retrival and moderate manipulation.

  • To judge if a binary tree is a BST, we can just do a in-order traversal for the tree. It should be sorted. L<D<R.

AVL Tree

A self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

??? Manupilation

Heap

Tree-based data structure in which the tree is a complete binary tree. Key present in the root node is the maximum or minimum among keys in all its children. And the rule also follows in it subtrees.

  • Complete binary tree - All levels are filled with nodes except the leaf level. And the leaf level fills nodes has keys as left as possible.

  • Get MinHeap or MaxHeap: O(1)

  • Insert and Delete: O(logn)

  • Extract Minimum in MinHeap O(logn) ???

  • Decrease key in MinHeap O(logn) ???

    Set

Map

Sorting

Merge Sort
Divide the array into two halves;
Sort the two halves recursively;
Merge the two sorted halves;

In mergeSort(), we can just call the function recursively for each half; and in merge(), we can sort the two halves of the arr into two temp arrs, and then sort them iteratively, finally merge them into the original array. Here is the implementation:

class MergeSort() {
    // arr - the array to be sorted; left - start index of the current array; right - end index of the current array;
    public void mergeSort(int[] arr, int left, int right) {
            if (left < right) {
                int mid = (left + right) / 2; // Mid-point of the arr;
                mergeSort(arr, left, mid);
                mergeSort(arr, mid + 1, right);
                merge(arr, left, mid, right);
            }
    }

    private void merge(int[] arr, int left, int mid, int right) {
        // Get size of the two subarrays
        int n1 = mid - left + 1;
        int n2 = right - (mid + 1) + 1;

        // Create two temp arrays
        int[] L = new int[n1];
        int[] R = new int[n2];

        // Put values into the temp arrays
        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i]; // Left half of arr
        }

        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j]; // Right half of arr
        }

        // Sort the two subarrays and merge them into the original arr
        int i = 0, j = 0;
        int k = left; // The start index where we put the merged result in.
        while (i < n1 && j < n2) {
            if (L[i] < R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // Merge the remaining arr in
        while (i < n1) {
            arr[k++] = L[i++];
        }
        while (j < n2) {
            arr[k++] = R[j++];
        }
    }
}
  • Time Complexity Analysis
    • The divide cost O(1);
    • The conquer step recursively sort two subarrays with size n/2, which cost T(n/2);
    • The merge cost O(n)
    • The Overall time complexity will be T(n) = 2T(n/2) + O(n). Applying Mater's thereom, the time complexity is O(nlogn). Or use the Binary Tree analysis.
Quick Sort
Choose a pivot in the array, partition the array into two halfs
Recursively sort each half - Put all elements greater than it on its right and all smaller elements on the right
Merge two halves to make sorted whole

In partition() we sort the array according to the pivot we choose, and place the pivot into a right place eventually.

In quicksort(), we partition the array into two halves according to the pivot, do quick sort for both subarrays.

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

// return the new pivot for partition
private int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1; // The pointer for smaller element
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++
            swap(arr, i, j);
        }
    }
    // Put the pivot into right place
    swap(arr, i + 1, high);
    return i + 1;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
  • Time Complexity Analysis
    • The partition cost O(n);
    • The conquer step recursively sort two subarrays with size k and n - k - 1, which cost T(k) + T(n - k - 1);
    • The Overall time complexity will be T(n) = T(k) + T(n - k - 1) + O(n). Applying Mater's thereom, the time complexity is O(nlogn). Or use the Binary Tree analysis.
    • The worst case is when elements are sorted increasingly or decreasingly, then O(n^2);
    • Average and best(mid point as pivot) case are O(nlogn).
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 2

求翻译啊

3年前 评论
Borris (楼主) 3年前

哇塞,,边学data structure边学english.

3年前 评论
Borris (楼主) 3年前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!