[Data Structure & Algorithm in Java 6th] Ch.3 Fundamental Data Structure

---

Github 코드

 

3.1 Using Arrays

There are other structures more general than array structure, (Ex. ArrayList; eliminates errors occur when copying the objects into larger array when necessary)but as a starting point to understand other structure array is a great model.

3.1.2 Sorting an Array

Insertion-sort(삽입정렬) : Swap elements in loop(inner & outer)

Insertion-sort(출처 : Data Structures and Algorithms in Java, 6th Edition 6th Edition - Michael T. Goodrich,  Wiley)

    public static void insertionSort(char[] data) {
        int l = data.length;
        for (int i = 1; i < l; i++) {
            char target = data[i];
            int j = i;
            while (j > 0 && data[j-1] > target) {
                data[j] = data[j-1];
                j--;
            }
            data[j] = target;
        }
    }

 

3.1.3 java.util Methods for Arrays and Random Numbers

Methods are given to Array because of its importance. 

PseudoRandom Number Generation

Useful when testing programs dealing with arrays. Uses java.util.Random

    public static void main(String[] args) {
        int[] data = new int[10];
        Random random = new Random();
        for (int i = 0; i < data.length; i++) {
            data[i] = random.nextInt(100);
        }
        int[] ori = Arrays.copyOf(data, data.length);
        Arrays.sort(data);
        System.out.println("ori: " + Arrays.toString(ori));
        System.out.println("sort: " + Arrays.toString(data));
    }

 

3.1.4 Simple Cryptography with Character Arrays

Convert String to charArray then re-convert : A = String.toCharArray() → new String(A). Caesar cipher : Generate encode, decode array then turn message into char array. Adjusting encode or decode will return encrypted or decrypted String. The key is shift alphabet in certain numbers.

public class CaesarCipher {
    protected char[] encoder = new char[26];
    protected char[] decoder = new char[26];
    /** Constructor that initializes the encryption and decryption arrays*/
    public CaesarCipher(int rotation) {
        for (int k = 0; k < 26; k++) {
            encoder[k] = (char) ('A' + (k + rotation) % 26);
            decoder[k] = (char) ('A' + (k - rotation + 26) % 26); //add 26 to avoid negative value
        }
    }
    /** Returns String representing encrypted message*/
    public String encrypt(String message) {
        return transform(message, encoder);
    }
 
    public String decrypt(String secret) {
        return transform(secret, decoder);
    }
 
    private String transform(String original, char[] code) {
        char[] msg = original.toCharArray();
        for (int k = 0; k < msg.length; k++) {
            if (Character.isUpperCase(msg[k])) {
                int j = msg[k] - 'A';
                msg[k] = code[j];
            }
        }
        return new String(msg);
    }
 
    public static void main(String[] args) {
        CaesarCipher cipher = new CaesarCipher(3);
        System.out.println("Encryption code = " + new String(cipher.encoder));
        System.out.println("Decryption code = " + new String(cipher.decoder));
        String message = "THE EAGLE IS IN PLAY; MEET AT JOE'S.";
        String coded = cipher.encrypt(message);
        System.out.println("Secret: " + coded);
        String answer = cipher.decrypt(coded);
        System.out.println("Message: " + answer);
    }
 
}

 

3.1.5 Two-Dimensional Arrays and Positional Games

In two-dimensional, first index refers to rows and second refers to columns. Tic-tac-toe : X as 1, O as -1, empty as 0. If row, column or diagonal add up to 3 or -3, game is over.

---

3.2 Singly Linked Lists

Drawbacks in array are must be fixed when created. Not easy to remove or insert because many elements should be shifted. Singly Linked Lists node stores sequence of elements, the reference of next element.

Singly LinkedList(출처 : Data Structures and Algorithms in Java, 6th Edition 6th Edition - Michael T. Goodrich,  Wiley)

instance head must be contained to locate other elements, tail is node stores null for next element.

One important property of Linked List is they do not predetermine size. Inserting new head, designate next element first then reassign variable to it. Removing head is just reverse of insert. However removing tail takes much time consuming cuz there's no direct link to element right before tail, it needs to check from the beginning. To overcome this inefficiency, we make Doubly Linked Lists.

---

3.3 Circularly Linked Lists

No fixed beginning or end. Based on cyclic order. Used in turn-based multiplayer games, city buses and subways stop order. Which has no designated first or last stop.

3.3.1 Round-Robin scheduling

Managing processes on running CPU. Process is given a short turn to execute, interrupted when slice ends regardless of job complete.

Circularly LinkedList(출처 : Data Structures and Algorithms in Java, 6th Edition 6th Edition - Michael T. Goodrich,  Wiley)

Removing head, replacing to tail.getnext(). Maintaining only tail(no need of head) saves bit memory usage and makes the code simpler. AddFirst is simply implemented by set new element's next reference to first(tail's getNext(), and set tail's tail.getnext() to new element. AddLast is implemented by invoke AddFirst to new element. Serve tail.getnext() as new element's next reference.

public void addFirst(E e) {
        if (size == 0) {
            tail = new Node<>(e, null);
            tail.setNext(tail); //link to itself circularly
        } else {
            Node<E> firstNode = new Node<>(e, tail.getNext());
            tail.setNext(firstNode);
        }
        size++;
    }

Tip : Node<E> represents Element's generic in node class.

---

3.4 Doubly Linked Lists

Node has prev and next elements' reference, efficiently remove node from a tail. Has dummy nodes(sentinels) which are header and tail that do not store elements of the primary sequence.

Doubly LinkedList(출처 : Data Structures and Algorithms in Java, 6th Edition 6th Edition - Michael T. Goodrich,  Wiley)

Advantages of sentinels are there are always existing nodes.

---

3.5 Equivalence Testing

Equivalencing test for both arrays and linked lists. There are chances of equal of two references that have different instance.(String) The superclass of all reference, Object class serves equal method.

Equivalence relation

• Treatment of null : nonnull equals(null) must return false.
• Reflexivity : must return true from nonnull x equals(x).
• Symmetry : should return same value x equals(y) and y equals(x).
• Transitivity : if x, y are equal and y, z are equal, x, y are equal.

3.5.1 Equivalence Testing with Arrays

Arrays class is not technically a class but extends Object class.

 * Tip : primitive type == int, char and reference type == Integer, Character.

Testing multidimensional arrays, use Arrays.deepEquals(a,b) since normal equals() method will return false or a[0] and b[0] which both are arrays.

---

3.6 Cloning Data Structures

We use clone() method

---

출처 : Data Structures and Algorithms in Java, 6th Edition 6th Edition (Michael T. Goodrich, Wiley)