# Algorithmic data structures - common data structures

Object comparator

```public static boolean isEqual(Integer o1, Integer o2) {
if (o1 == null && o2 != null) {
return false;
}
if (o1 != null && o2 == null) {
return false;
}
if (o1 == null && o2 == null) {
return true;
}
return o1.equals(o2);
}```

```//One way linked list node structure (can be implemented as a template)

public class Node {
public int value;
public Node next;
public Node(int data) {
value = data;
}
}
```

```//Bidirectional linked list node structure

public class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;

public DoubleNode(int data) {
value = data;
}
}
```

```public static class Node {
public int value;
public Node next;

public Node(int data) {
value = data;
}
}

//   a    ->   b    ->  c  ->  null
//   c    ->   b    ->  a  ->  null
Node pre = null;
Node next = null;
}
return pre;
}

======================================================================================
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;

public DoubleNode(int data) {
value = data;
}
}

public static DoubleNode reverseDoubleList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
}
return pre;
}```

2) Delete all given values

```public static class Node {
public int value;
public Node next;

public Node(int data) {
this.value = data;
}
}

public static Node removeValue(Node head, int num) {
// head comes to the first position that does not need to be deleted
break;
}
}
// 1 ) head == null
// 2 ) head != null
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
}```

Stack and queue

Stack: data in and out, like a magazine

Queue: data first in first out, like queuing

Practical implementation of stack and queue

```public static class Node<T> {
public T value;
public Node<T> last;
public Node<T> next;

public Node(T data) {
value = data;
}
}

public static class DoubleEndsQueue<T> {
public Node<T> tail;

Node<T> cur = new Node<T>(value);
tail = cur;
} else {
}
}

Node<T> cur = new Node<T>(value);
tail = cur;
} else {
cur.last = tail;
tail.next = cur;
tail = cur;
}
}

return null;
}
tail = null;
} else {
cur.next = null;
}
return cur.value;
}

public T popFromBottom() {
return null;
}
Node<T> cur = tail;
tail = null;
} else {
tail = tail.last;
tail.next = null;
cur.last = null;
}
return cur.value;
}

public boolean isEmpty() {
}

}```

Array implementation stack

Array + index

Double ended linked list implementation stack

Press in and take out in the same direction

```public static class MyStack<T> {
private DoubleEndsQueue<T> queue;

public MyStack() {
queue = new DoubleEndsQueue<T>();
}

public void push(T value) {
}

public T pop() {
}

public boolean isEmpty() {
return queue.isEmpty();
}

}```

Double ended linked list implementation queue

Press in and out in different directions

```public static class MyQueue<T> {
private DoubleEndsQueue<T> queue;

public MyQueue() {
queue = new DoubleEndsQueue<T>();
}

public void push(T value) {
}

public T poll() {
return queue.popFromBottom();
}

public boolean isEmpty() {
return queue.isEmpty();
}

}```

Array implementation queue

Circular array + two pointers + size

```public static class MyQueue {
private int[] arr;
private int pushi;// end
private int polli;// begin
private int size;
private final int limit;

public MyQueue(int limit) {
arr = new int[limit];
pushi = 0;
polli = 0;
size = 0;
this.limit = limit;
}

public void push(int value) {
if (size == limit) {
throw new RuntimeException("The queue is full and can't be added");
}
size++;
arr[pushi] = value;
pushi = nextIndex(pushi);
}

public int pop() {
if (size == 0) {
throw new RuntimeException("The queue is empty. You can't take any more");
}
size--;
int ans = arr[polli];
polli = nextIndex(polli);
return ans;
}

public boolean isEmpty() {
return size == 0;
}

// If the current subscript is i, return to the next position
private int nextIndex(int i) {
return i < limit - 1 ? i + 1 : 0;
}

}```

Since languages have these structures and APIs, why do you need to practice by hand?

1) Algorithmic problem independent language

2) The api provided by the language is limited. When there are new functions that the api does not provide, they need to be rewritten

3) The bottom layer of any software tool is the most basic algorithm and data structure, which can not be bypassed

Realize a special stack, and then realize the function of returning the smallest element in the stack on the basis of the basic functions

Memory data stack + minimum stack (compare the pressing data with the minimum stack top data size, press it into the minimum stack if it is small, and press the minimum stack top data again if it is large)

```public static class MyStack1 {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;

public MyStack2() {
this.stackData = new Stack<Integer>();
this.stackMin = new Stack<Integer>();
}

public void push(int newNum) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if (newNum < this.getmin()) {
this.stackMin.push(newNum);
} else {
int newMin = this.stackMin.peek();
this.stackMin.push(newMin);
}
this.stackData.push(newNum);
}

public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
this.stackMin.pop();
return this.stackData.pop();
}

public int getmin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}```

How to implement queue structure with stack structure

push stack + pop stack: 1 push stack data is poured to the pop stack at one time. 2. Only when the pop stack is empty can data be poured in

```public static class TwoStacksQueue {
public Stack<Integer> stackPush;
public Stack<Integer> stackPop;

public TwoStacksQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}

// push stack pours data into pop stack
private void pushToPop() {
if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
}

stackPush.push(pushInt);
pushToPop();
}

public int poll() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.pop();
}

public int peek() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.peek();
}
}```

How to implement stack structure with queue structure

queue+help two queues. The data is stored in the queue. When taking the data, move the queue data into the help queue until only the last data is returned, and exchange the queue and help queue

```public static class TwoQueueStack<T> {
public Queue<T> queue;
public Queue<T> help;

public TwoQueueStack() {
}

public void push(T value) {
queue.offer(value);
}

public T poll() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}

public T peek() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
help.offer(ans);
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}

public boolean isEmpty() {
return queue.isEmpty();
}

}```

Recursion? What is this?

1. Method call

2. Method end condition

For novices, it is necessary to draw the structure diagram of the calling process (tree diagram), which is conducive to the analysis of recursion

Recursion is not metaphysics. The bottom layer of recursion is realized by system stack

Any recursive function can be changed to non recursive

example

How to find the maximum value in array arr[L..R] by recursive method.

1) Divide the [L..R] range into left and right halves. Left: [L..Mid] right [Mid+1..R]

2) The left part maximizes and the right part maximizes

3) The maximum value in the [L..R] range is max {left part maximum value, right part maximum value}

Note: 2) is a recursive process. When there is only one number in the range, you can no longer recurse

```// Find the maximum value L on the range of arr[L..R] R   N
public static int process(int[] arr, int L, int R) {
// There is only one number in the arr[L..R] range. It returns directly, base case
if (L == R) {
return arr[L];
}
// L...R is more than one number
// mid = (L + R) / 2
int mid = L + ((R - L) >> 1); // Midpoint 	 one
int leftMax = process(arr, L, mid);
int rightMax = process(arr, mid + 1, R);
return Math.max(leftMax, rightMax);
}```

Master formula

Shape such as

T (n) = a * t (n / b) + O (n ^ d) (where a, B and d are constants)

The time complexity can be determined directly through the Master formula

If log (B, a) < D, the complexity is O(N^d)

If log (B, a) > D, the complexity is O(N^log(b,a))

If log(b,a) == d, the complexity is O(N^d * logN)

Hashtable

1) Hash table can be understood as a collection structure at the use level

2) If there is only key and no accompanying data value, you can use the HashSet structure

3) If there are both key s and accompanying data value s, you can use the HashMap structure

4) Whether there is accompanying data or not is the only difference between HashMap and HashSet. The actual structure is the same thing

5) Using the operations of hash table put, remove, put and get, it can be considered that the time complexity is O(1), but the constant time is relatively large

6) If the hash table is a basic type, it is internally passed by value, and the memory occupation is the size of this thing

7) If the hash table is not the basic type, it is passed internally by reference, and the memory occupation is 8 bytes

Ordered table

1) an ordered table can be understood as a set structure at the use level

2) If there is only key and no accompanying data value, the TreeSet structure can be used

3) If there are both key s and accompanying data value s, the TreeMap structure can be used

4) Whether there is accompanying data or not is the only difference between TreeSet and TreeMap. The actual structure of the underlying is the same thing

5) The ordered table organizes key s in order, while the hash table is not organized at all

6) Red black tree, AVL tree, size balance tree and jump table all belong to ordered table structure, but the specific implementation of the bottom layer is different

7) The basic value to be passed is the size of the internal memory

8) If it is not a basic type, it is passed internally by reference, and the memory occupation is 8 bytes

9) No matter what the underlying implementation is, as long as it is an ordered table, it has the following fixed basic functions and fixed time complexity

Comparison between ordered table and hash table

When the hash table is used, the time complexity of addition, deletion, modification and query is O(1)

When used, the ordered table has more functions than the hash table, and the time complexity is O(logN)

The ordered table sorts the data, so if it is not a basic type, you need to implement the comparator

Keywords: Algorithm

Added by test on Sat, 15 Jan 2022 07:21:28 +0200