3 Fundamental Data Structures

3.1 Using Arrays

3.1.1 Storing in an Array

add:插入指定index，index数据与index之后数据整体右移
remove:移除指定index，index之后所有数据整体左移

3.1.2 Sorting an Array

Insert-Sort

3.1.3 java.util Methods for Arrays and Random Numbers

1 Most commonly used methods:
built-in class: java.util.Arrays.
equals(A, B): return true if and only if array A and array B are equal. A and B have the same element values in the same order.
fill(A, x): Stores value x in every cell of array A.
copyOf(A, n): return an array of size n
copyOfRange(A, s, t): returns an array of size t-s. copy array from index s to t-1.
toString(A): returns a String representation of the array A
sort(A): sorts the array A
binarySearch(A, x): searches the Sorted array A for value x, returning the index where it is found.

2 PseudoRandom Number Generation
built-in class: java.util.Random.
Methods of the java.util.Random class:
nextBoolean(): returns the next pseudorandom boolean value
nextDouble(): returns the next pseudorandom double value, between 0.0 to 1.0
nextInt(): returns the next pseudorandom int value
nextInt(n): returns the next pseudorandom int value n the range from 0 up to but not including n
setSeed(s): sets the seed of this pseudorandom number generator to the long s

3.1.4 Simple Cryptography with Character Arrays

1 Converting Between Strings and Character Arrays

1
2
3

String s = "bird";
A = s.toCharArray();  // A = {'b','i','r','d'}
B = new String(A);  // B = "bird"

2 Using Character Arrays as Replacement Codes

3.1.5 2-D Arrays and Positional Games

first index refers as a row number;
second index refers as a column number.

1	int[][] data = new int[8][10];

TicTacToe Game:


public class TicTacToe {
    private static final int X = 1, O = -1;
    private static final int EMPTY = 0;
    private int board[ ][ ] = new int[3][3];
    private int player;

    public TicTacToe( ) { clearBoard( ); }

    public void clearBoard( ) {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                board[i][j] = EMPTY;
        player = X;
    }

    public void putMark(int i, int j) throws IllegalArgumentException {
        if ((i < 0) || (i > 2) || (j < 0) || (j > 2))
            throw new IllegalArgumentException("Invalid board position");
        if (board[i][j] != EMPTY)
            throw new IllegalArgumentException("Board position occupied");
        board[i][j] = player;
        player = -player;
    }

    public boolean isWin(int mark) {
            return ((board[0][0] + board[0][1] + board[0][2] == mark*3)
                    || (board[1][0] + board[1][1] + board[1][2] == mark*3)
                    || (board[2][0] + board[2][1] + board[2][2] == mark*3)
                    || (board[0][0] + board[1][0] + board[2][0] == mark*3)
                    || (board[0][1] + board[1][1] + board[2][1] == mark*3)
                    || (board[0][2] + board[1][2] + board[2][2] == mark*3)
                    || (board[0][0] + board[1][1] + board[2][2] == mark*3)
                    || (board[2][0] + board[1][1] + board[0][2] == mark*3));
    }

    public int winner( ) {
        if (isWin(X)) return(X);
        else if (isWin(O)) return(O);
        else return(0);
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                switch (board[i][j]) {
                    case X: sb.append("X"); break;
                        case O: sb.append("O"); break;
                        case EMPTY: sb.append(" "); break;
                }
                if (j < 2) sb.append("|");
            }
            if (i < 2) sb.append("\n-----\n");
        }
        return sb.toString();
    }

    public static void main(String[ ] args) {
        TicTacToe game = new TicTacToe();
        game.putMark(1,1);  game.putMark(0,2);
        game.putMark(2,2);  game.putMark(0,0);
        game.putMark(0,1);  game.putMark(2,1);
        game.putMark(1,2);  game.putMark(1,0);
        game.putMark(2,0);

        System.out.println(game);
        int winningPlayer = game.winner();
        String[]outcome={"Owins","Tie","Xwins"};
        System.out.println(outcome[1 + winningPlayer]);
    }
}

3.2 Singly Linked Lists

Array:
Cons:fixed capacity;
time-consuming for insertions and deletions
head
tail

Inserting an element
Removing an element

Commonly used methods:

size();
isEmpty();
first();
last();
addFirst(e);
addLast(e);
removeFirst();

3.3 Circularly Linked Lists

Linked lists are traditionally viewed as storing a sequence of items in a linear order, from first to last.

3.3.1 Round-Robin Scheduling

To support the responsiveness of an arbitrary number of concurrent processes, most operating systems allow processes to effectively share use of the CPUs, using some form of an algorithm known as Round-Robin Scheduling. A process is given a short turn to execute, known as a time slice, but it is interrupted when the slice ends, even if its job is not yet complete. New Processes can be added to the system, and processes that complete their work can be removed.

3.3.2 Designing and Implementing a Circularly Linked List

3.4 Doubly Linked Lists

Singly Linked List:
Cons:
efficiently add/delete first node but not for last node

size();
isEmpty();
first();
last();
addFirst(e);
addLast(e);
removeFirst();
removeLast();

3.5 Equivalence Testing

3.5.1 Equivalence Testing with Arrays

a==b: tests if a and b refer to the same underlying array instance
a.equals(b): this is identical to a==b.
Arrays.equals(a, b): return True if the arrays have the same length and all pairs of corresponding elements are “equal” to each other.
Arrays.deepEquals(a, b): for multidimensional arrays

3.5.2 Equivalence Testing with Linked Lists

3.6 Cloning Data Structures

3.6.1 Cloning Arrays

Imgur
This is not copy. Just have different referred name.

1
2
3

int[] data = {2,3,4,5,6};
int[] backup;
backup = data.clone();

3.6.2 Cloning Linked Lists

5 Recursion

5.1 Illustrative Examples

5.1.1 The Factorial Function

edge case;
base case;
recursive case;

5.1.2 Drawing an English Ruler

5.1.3 Binary Search

5.1.4 File Systems

report disk usage of a file system

public static long diskUsage(File root) {
  long total = root.length();
  if (root.isDirectory()) {
    for (String childname : root.list()) {
        File child = new File(root, childname);
        total += diskUsage(child);
    }
  }
  System.out.println(total + "\t" + root);
  return total;
}

5.3 Further Examples of Recursion

5.3.1 Linear Recursion

5.3.2 Binary Recursion

5.3.3 Multiple Recursion

5.4 Designing Recursive Algorithms

6 Stacks, Queues, and Deques

6.1 Stacks

LIFO

6.1.1 The Stack Abstract Data Type

import java.util.Stack;

push();
pop();
top();
size();
isEmpty();

6.1.2 A Simple Array-Based Stack Implementation

6.1.3 Implementing a Stack with a Singly Linked List

Adapter Pattern

6.1.4 Reversing an Array Using a Stack

6.1.5 Matching Parentheses and HTML Tags

An algorithm for Matching Delimiters;
Matching Tags in a Markup Language;

6.2 Queues

FIFO

6.2.1 The Queue Abstract Data Type

import java.util.Queue

enqueue(e);
dequeue();
first();
size();
isEmpty();

6.2.2 Array-Based Queue Implementation

6.2.3 Implementing a Queue with a Singly Linked List

6.2.4 A Circular Queue

6.3 Double-Ended Queues

6.3.1 The Deque Abstract Data Type

import java.util.Queue;

addFirst();
addLast();
removeFirst();
removeLast();

first();
last();
size();
isEmpty();