# Summary of Data Structure and Algorithm-Part One

1. Array
3. Stack
4. queue
5. Hash table
6. Binary tree
7. heap
8. Skip table
9. Figure
10. Trie tree

### 2. The 10 most commonly used algorithms

1. Recursion
2. Sort
3. Binary search
4. search for
5. Hash algorithm
6. how are you
7. Divide and conquer algorithm
8. Backtracking algorithm
9. Dynamic programming
10. String matching algorithm

### 3. The relationship between data structure and algorithm

1. Data structure is how data is organized and serves algorithms.
2. Algorithms are to perform operations on specific data structures.

### 4. Common time complexity

1. O(1)
2. O(logn)
3. O(n)
4. O(nlogn)
5. O to the k power
6. Exponential order O (2 to the nth power)
7. Factorial order O(n!)

### 7. Linear table

1. The linear table is the structure of the data row like a line.
2. The data on each linear table can only have forward and backward directions at most.
3. Arrays, linked lists, queues, and stacks are all linear lists.

### 8. Nonlinear table

1. In a non-linear table, the data is not a simple context
2. Binary trees, heaps, and graphs are all non-linear tables

### 9. Array

1. An array is a linear table data structure that uses a set of continuous memory space to store a set of data of the same type.
2. Contiguous memory space and the same type of data
• Advantages: Allow the array to be randomly accessed/randomly access the array elements based on the subscript.
• Disadvantages: Adding and deleting elements in the array requires a large amount of data movement in order to ensure memory continuity.
3. The search time complexity of the array is not O(1), even if it is a sorted array, it takes O(logn) to find a certain data
4. Advantages of container/ArrayList and array comparison
• ArrayList encapsulates many array operations for easy use
• ArrayList supports dynamic expansion
• Dynamic expansion still inevitably moves data in memory.If the amount of data can be determined in advance, the data size should be specified when creating an ArrayList.
5. Disadvantages of container/ArrayList and array comparison
• ArrayList cannot store basic types. To store basic types, boxing is involved, and unboxing has performance loss
• The amount of data is known, and the operation of the data is very simple. Most methods of ArrayList are not involved, and arrays can be used.
6. How to choose container/ArrayList and array
• For business development, you can use ArrayList directly, which is simple. Lower performance has almost no impact
• The underlying development compares the network framework, the performance must be optimized to the extreme, and the array must be used.

### 10. Linked list: A group of scattered memory blocks are connected together through pointers.

1. Single list
```Node head = node0;
Node tail = noden;
**
tail.next = null ;
copy the code```
2. Circular linked list
```Node head = node0;
Node tail = noden;
**
Copy code```
3. Doubly linked list
```Node head = node0;
Node tail = noden;
head.pre = null ;
**
tail.next = null ;
tail.pre = noden- 1 ;
copy the code```
4. Doubly circular linked list
```Node head = node0;
Node tail = noden;
**
tail.pre = noden- 1 ;
copy the code```

### 11. Comparison of array and linked list

1. The time complexity of linked list insertion and deletion is O(1), and the time complexity of random access is O(n).
2. The time complexity of array insertion and deletion is O(n), and the time complexity of random access is O(1).
3. The array uses continuous space on the memory, which is friendly to the CPU cache, and the data in the linked list is not continuous in the memory, and it is not friendly to the CPU cache.
4. The disadvantage of the array is that the size is fixed, and it occupies the full space after declaration.If the array is too large, it will waste memory, and even directly OOM.If it is too small, the expansion of the array will affect performance.
5. The linked list naturally supports dynamic expansion. However, each element in the linked list must store the next and pre pointers, and a single element takes up more memory.
6. If the number of data is controllable, the performance of using arrays is better. Avoid storing next and pre pointers to occupy additional space.

### 12. Several problems with linked lists

#### 1. Single linked list implements LRU

```public  class  LRULinkedList < T > {
class  Node < T > {
public T data;
public Node next;
public  Node (T data, Node next) {
super ();
this .data = data;
this .next = next;
}
}

private  static  int DEFAULT_CAPACITY = 6 ;
private  int capacity = DEFAULT_CAPACITY;
private  int count = 0 ;
private Node head = null ;
public  LRULinkedList ( int capacity) {
this .capacity = capacity;
}
public  boolean  isFull () {
return count == capacity;
}
public Node createNode (T data) {
Node node = new Node(data, null );
return node;
}
public  void  access (T data) {
if (data == null ){
throw  new IllegalArgumentException( "The accessed element cannot be empty!" );
}
if (head == null ){
count++;
return ;
}
//The head node is the data to be accessed
return ;
}
Node curr = head;
while (curr.next != null && !curr.next.data.equals(data)){
curr = curr.next;
}
if (curr.next != null && curr.next.data.equals(data)){
//The element to be accessed already exists
Node target = curr.next;
curr.next = target.next;
} else {
//The element to be accessed does not exist
if (isFull()){
//The linked list is full
//Delete the current end node

//There is a problem with this writing, print the result:
//The current data is: -> 10 -> 8 -> 6 -> 4 -> 2 -> 9 -> 7 -> 5 -> 3 -> 1
//Node c = head;
//while(c != null && c.next != null) {
//c = c.next;
//}
//c = null;

Node c = head;
while (c != null && c.next != null && c.next.next != null ) {
c = c.next;
}
c.next = null ;

} else {
//The linked list is not full
count++;
}
}
}
Node target = createNode(data);
}
private  void  printAll ()  {
System.out.print( "The current data is: ");
Node curr = head;
while (curr != null ) {
System.out.print( "->" + curr.data);
curr = curr.next;
}
}
public  static  void  main (String[] args)  {
LRULinkedList<Integer> list = new LRULinkedList<>( 6 );
list.access( 1 );
list.access( 3 );
list.access( 5 );
list.access( 7 );
list.access( 9 );
list.access( 2 );
list.access( 4 );
list.access( 6 );
list.access( 8 );
list.access( 10 );
list.printAll();

Person a = new Person();
a.name = "a" ;
Person b = new Person();
b.name = "b" ;
Person c = new Person();
c.name = "c" ;
a.friend = b;
b.friend = c;

//There is a problem with writing like this: friend of b: name:c
//try {
//c = null;
//System.out.println("friend of b:" + b.friend);
//} catch (Exception e) {
//}

//try {
//b.friend = null;
//System.out.println("b's friend:" + b.friend);
//} catch (Exception e) {
//}
}
public  static  class  Person {
public String name;
public Person friend;
@Override
public String toString ()  {
return  "name:" + name;
}
}
}
Copy code```

#### 2. The above example leads to a misunderstanding

```//A.attr and C both point to the same object B
A.attr = B;
BInstance C = B;
Blanking//C
C = null ;
//null case A.attr not
duplicated code```
• A.attr -> B
• C -> B
• C = null, it just breaks the link between the variable name of C and the instance of B, but B is still linked by A.attr. B itself will not be made blank.

#### 3. Joseph issue an Ali T questions: How do I use a line of code to solve the problem of Josephus

##### 3.1. Using arrays to solve
```/**
* Joseph's problem: use an array to solve
*/
public  class  JosephusArray  {
public  static  void  main (String[] args)  {
JosephusArray t = new JosephusArray();
int [] arr = new  int [ 11 ];
for ( int i = 0 ; i <arr.length; i++) {
arr[i] = i + 1 ;
}
System.out.println( "The value of the array:" );
Arrays.stream(arr).forEach(System.out::println);
int result = t.findLastItemData(arr, 3 );
System.out.println( "Final remaining Item value:" + result);
}

public  int  findLastItemData ( int [] arr, int k)  {
if (arr == null || arr.length <= 0 ) {
return - 1 ;
}
if (arr.length == 1 ) {
return  0 ;
}
int length = arr.length;
int count = arr.length;
int index = 0 ;
int step = 0 ;
int tagIndex = -1 ;
while (count> 1 ) {
while (step <k) {
if (arr[index] !=- 1 ) {
step++;
tagIndex = index;
}
if (index == length- 1 ) {
index =  0 ;
}  else {
index++;
}
}
arr[tagIndex] = -1 ;
step = 0 ;
count--;
}
while (arr[index] ==- 1 ) {
if (index == length- 1 ) {
index = 0 ;
} else {
index++;
}
}
return arr[index];
}
}

//Print the result:
The value of the array:
. 1
2
. 3
. 4
. 5
. 6
7
. 8
. 9
10
. 11
final residual value of Item: 7
copy the code```
##### 3.2. Use a circular list to solve
```public  class  JosephusLinkedList < T > {
public  static  class  Node < T > {
public T data;
public Node<T> next;
public  Node (T data)  {
super ();
this .data = data;
}
}
private Node<T> tail;
public  void  add (Node<T> node)  {
if (head == null ) {
head = tail = node;
} else {
tail.next = node;
tail = node;
}
}
public  void  remove (Node<T> node)  {
if (head == null || node == null ) {
return ;
}
Node curr = head;
while (curr.next != node) {
curr = curr.next;
}
head.next = null ;
head = tail = null ;
return ;
}
Node next = node.next;
curr.next = next;
if (node  == head) {
}
node.next = null ;
}
public  int  findLastItemData ( int k)  {
if (head == null ) {
return - 1 ;
}
Node curr = head;
Node pre = null ;
int step = 0 ;
while (step <k) {
pre = curr;
curr = curr.next;
step++;
}
remove(pre);
step = 0 ;
}
return ( int ) head.data;
}
public  static  void  main (String[] args)  {
for ( int i = 1 ;i<= 11 ;i++) {
}
int result = t.findLastItemData( 5 );
System.out.println( "The value of the last remaining item:" + result);
}
}

//print the results:
the value of the last remaining items: 8
copy the code```

#### 4. Array implements LRU

```public  class  LRUBasedArray < T > {
public  static  int DEFAULT_CAPACITY = 6 ;
private  int capacity = DEFAULT_CAPACITY;
private T[] data;
private  int count;
private Map<T, Integer> positionHolder;

public  LRUBasedArray ( int capacity)  {
this .count = 0 ;
this .capacity = capacity;
this .data = (T[]) new Object[capacity];
this .positionHolder = new HashMap<>(capacity);
}
public  void  clear ()  {
positionHolder.clear();
data = (T[]) new Object[capacity];
count = 0 ;
}
public  boolean  isFull ()  {
return count == capacity;
}
public  boolean  contains (T item)  {
return positionHolder.containsKey(item);
}
public  void  access (T item)  {
//First determine whether the item already exists
boolean contains = contains(item);
if (contains) {
//Get the index of the item
int index = positionHolder.get(item);
if (index == 0 ) {
data//current to be accessed, is already in the array of the head
return ;
} else {
//The current data to be accessed is not at the head of the array. You need to move the data to the head and move other array elements to the right
transferToRight(index);
}
} else {
//Judging whether the array is full
boolean isFull = isFull();
if (isFull) {
//The array is full
//Empty the tail element
removeTail();
//Move the element to the right
transferToRight(capacity- 1 );
//Insert the head element
} else {
//The array is not full
//Move the element to the right
transferToRight(count);
//count plus one
count++;
}
}
}
public  void  setHead (T item)  {
data[ 0 ] = item;
positionHolder.put(item, 0 );
}
public  void  removeTail ()  {
positionHolder.remove(data[capacity- 1 ]);
data[capacity- 1 ] = null ;
}
public  void  transferToRight ( int toIndex)  {
for ( int i = toIndex- 1 ; i >= 0 ; i--) {
data[i + 1 ] = data[i];
positionHolder.put(data[i + 1 ], i+ 1 );
}
}
public  void  printAll ()  {
for ( int i = 0 ; i <count; i++) {
System.out.println( "item" +i+ ":" + data[i]);
}
}
public  static  void  main (String[] args)  {
LRUBasedArray<Integer> lruBasedArray = new LRUBasedArray<>( 6 );
lruBasedArray.access( 1 );
lruBasedArray.access( 2 );
lruBasedArray.access( 3 );
lruBasedArray.access( 4 );
lruBasedArray.access( 5 );
lruBasedArray.access( 6 );
lruBasedArray.access( 7 );
lruBasedArray.access( 3 );
lruBasedArray.access( 3 );
lruBasedArray.access( 3 );
lruBasedArray.access( 8 );
lruBasedArray.access( 9 );
lruBasedArray.access( 10 );
lruBasedArray.printAll();
}
}

//Run Results
item0: 10
ITEM1: . 9
ITEM2: . 8
Item3: . 3
ITEM4: . 7
ITEM5: . 6
copy the code```

#### 5. Custom singly linked list, check whether the character is a palindrome string

```public  class  PalindromeSinglyList < T > {
public  class  Node < T > {
public T data;
public Node<T> next;
public  Node (T data, Node<T> next)  {
super ();
this .data = data;
this . next = next;
}
@Override
public String toString ()  {
return  "Node [data=" + data + "]" ;
}
}

public  void  add (T item)  {
if (head == null ) {
head = new Node<T>(item, null );
return ;
}
Node<T> tail = head;
while (tail.next != null ) {
tail = tail.next;
}
tail.next = new Node<T>(item, null );
}
public Node inverseList (Node tail)  {
Node curr = head;
Node next = null ;
while (curr.next != tail) {
next = curr.next.next;
curr.next = next;
}
curr.next = null ;
return tail;
}
public  boolean  compareTwoList (Node leftHead, Node rightHead)  {
if (leftHead == null || rightHead == null ) {
return  false ;
}
}
return leftHead == null && rightHead == null ;
}
private  void  printNode (Node node)  {
while (node  != null ) {
System.out.println(node);
node = node.next;
}
}
public  boolean  isPalindrome ()  {
if (head == null ) {
//empty list
return  false ;
}
if (head.next == null ) {
//Only the head element
return  true ;
}
if (head.next.next == null ) {
//There are only 2 elements
}
//There are >=3 elements
//First determine whether the number of elements is odd or even
Node slow = head;
Node fast = head;
while (slow.next != null && fast.next != null && fast.next.next != null ) {
slow = slow.next;
fast = fast.next.next;
}
if (fast.next != null ) {
//even elements
} else {
//odd number of elements
}
//Print two Nodes and subsequent Nodes
System.out.println( "List elements on the left half:" );
System.out.println( "List elements on the right half:" );
System.out.println( "Whether the palindrome string:" + result);
return result;
}
public  static  void  main (String[] args)  {
int [] d1 = new  int [] { 1 , 2 , 3 , 4 , 3 , 2 , 1 };
int [] d2 = new  int [] { 1 , 2 , 3 , 2 , 1 };
int [] d3 = new  int [] { 1 , 2 , 2 , 1 };
int[] d4 = new  int [] { 1 , 0 , 1 , 0 };
PalindromeSinglyList list1 = new PalindromeSinglyList();
for ( int item:d1) {
}
PalindromeSinglyList list2 = new PalindromeSinglyList();
for ( int item:d2) {
}
PalindromeSinglyList list3 = new PalindromeSinglyList();
for ( int item:d3) {
}
PalindromeSinglyList list4 = new PalindromeSinglyList();
for ( int item:d4) {
}
list1.isPalindrome();
System.out.println( "===============" );
list2.isPalindrome();
System.out.println( "===============" );
list3.isPalindrome();
System.out.println( "===============" );
list4.isPalindrome();
}
}

//operation result
List elements on the left half:
Node [data= 4 ]
Node [data= 3 ]
Node [data= 2 ]
Node [data= 1 ]
List elements on the right half:
Node [data= 4 ]
Node [data= 3 ]
Node [data= 2 ]
Node [data= 1 ]
Whether palindrome string: true
===============
List elements on the left half:
Node [data= 3 ]
Node [data= 2 ]
Node [data= 1 ]
List elements on the right half:
Node [data= 3 ]
Node [data= 2 ]
Node [data= 1 ]
Whether palindrome string: true
===============
List elements on the left half:
Node [data= 2 ]
Node [data= 1 ]
List elements on the right half:
Node [data= 2 ]
Node [data= 1 ]
Whether palindrome string: true
===============
List elements on the left half:
Node [data= 0 ]
Node [data= 1 ]
List elements on the right half:
Node [data= 1 ]
Node [data= 0 ]
Whether palindrome string: false

Copy code```

#### 6. Single linked list reversal

```public  class  LinkedListTest  {
public  class  Node < T > {
public T data;
public Node<T> next;
public  Node (T data) {
this .data = data;
}
}
public Node reverse (Node list)  {
if (list == null ) {
throw  new IllegalArgumentException( "The head node of the linked list cannot be empty!" );
}
if (list.next == null ) {
return list;
}
Node curr = list;
Node next = null ;
while (curr.next != null ) {
next = curr.next.next;
curr.next.next = list;
list = curr.next;
curr.next = next;
}
return list;
}
private  void  testReverse ()  {
Node list = new Node<Integer>( 3 );
Node n1 = new Node<Integer>( 2 );
Node n2 = new Node<Integer>( 4 );
Node n3 = new Node<Integer>( 6 );
Node n4 = new Node<Integer>( 8 );
list.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
Node result = reverse(list);
while (result != null ) {
System.out.println( "Current value:" + result.data);
result = result.next;
}
}
public  static  void  main (String[] args)  {
t.testReverse();
}
}

//Run Results:
Current value: 8
Current Value: 6
Current Value: 4
Current Value: 2
Current Value: 3
copy the code```
1. Detection of rings in singly linked lists
```public  boolean  checkCircle (Node list)  {
if (list == null || list.next == null || list.next.next == null ) {
return  false ;
}
Node slow = list;
Node fast = list;
while (slow.next != null && fast.next != null && fast.next.next != null ) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return  true ;
}
}
return  false ;
}
private  void  testCheckCircle ()  {
Node list = new Node<Integer>( 3 );
Node n1 = new Node<Integer>( 2 );
Node n2 = new Node<Integer>( 4 );
Node n3 = new Node<Integer>( 6 );
Node n4 = new Node<Integer>( 8 );
list.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n1;
//n3.next = n4;
boolean result = checkCircle(list);
System.out.println( "The current singly linked list has a ring:" + result);
}

public  static  void  main (String[] args)  {
t.testCheckCircle();
}

//The result:
the current single-chain looped: to true
copy the code```

#### 7. The merger of two ordered singly linked lists

```public Node mergeTwoSortedList (Node l1, Node l2)  {
if (l1 == null || l2 == null ) {
throw  new IllegalArgumentException( "Parameter cannot be empty!" );
}
Node soldier = new Node( null );
Node curr = soldier;
while (l1 != null && l2 != null ) {
if (l1.data.hashCode() <l2.data.hashCode()) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
if (l1 != null ) {
curr.next = l1;
}
if (l2 != null ) {
curr.next = l2;
}
return soldier.next;
}
public  void  testMergeTwoSortedList ()  {
Node<Integer> l1 = new Node<Integer>( 1 );
Node<Integer> l11 = new Node<Integer>( 3 );
Node<Integer> l12 = new Node<Integer>( 9 );
Node<Integer> l13 = new Node<Integer>( 19 );
l1.next = l11;
l11.next = l12;
l12.next = l13;

Node<Integer> l2 = new Node<Integer>( 2 );
Node<Integer> l21 = new Node<Integer>( 4 );
Node<Integer> l22 = new Node<Integer>( 6 );
Node<Integer> l23 = new Node<Integer>( 12 );
l2.next = l21;
l21.next = l22;
l22.next = l23;
Node result = mergeTwoSortedList(l1, l2);
while (result != null ) {
System.out.println( "Current item value:" + result.data);
result = result.next;
}
}

public  static  void  main (String[] args)  {
t.testMergeTwoSortedList();
}

//Run Results:
Current Item Value: 1
Current Item Value: 2
Current Item Value: 3
Current key: 4
Current Item Value: 6
Current key: 9
Current Item Value: 12
Current Item Value: 19
copy the code```

#### 8. Delete the Kth last node of the singly linked list

```public Node deleteLastK (Node list, int k)  {
if (list == null || k < 1 ) {
throw  new IllegalArgumentException( "The parameter is wrong!" );
}
Node fast = list;
int count = 0 ;
while (fast.next != null && count <k- 1 ) {
fast = fast.next;
count++;
}
if (count <k- 1 ) {
throw  new IllegalArgumentException( "The length of the list is not enough!" );
}
if (fast.next == null ) {
//There are only k nodes in the linked list, and only the head node can be deleted
Node curr = list;
list = list.next;
curr.next = null ;
return curr;
}
Node slow = list;
fast = fast.next;
while (slow.next != null && fast.next != null ) {
slow = slow.next;
fast = fast.next;
}
Node next = slow.next.next;
slow.next.next = null ;
slow.next = next;
return list;
}
public  void  testDeleteLastK ()  {
Node list = new Node<Integer>( 3 );
Node n1 = new Node<Integer>( 2 );
Node n2 = new Node<Integer>( 4 );
Node n3 = new Node<Integer>( 6 );
Node n4 = new Node<Integer>( 8 );
Node n5 = new Node<Integer>( 10 );
Node n6 = new Node<Integer>( 12 );
list.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
Node result = deleteLastK(list, 4 );
while (result != null ) {
System.out.println( "Current item value:" + result.data);
result = result.next;
}
}
public  static  void  main (String[] args)  {
t.testDeleteLastK();
}

//Run Results:
Current Item Value: 3
Current Item Value: 2
Current key: 4
Current key: 8
Current Item Value: 10
Current Item Value: 12
copy the code```

#### 9. Find the middle node of the singly linked list

```public Node findMiddleNode (Node list)  {
if (list == null ) {
throw  new IllegalArgumentException( "Parameter cannot be empty!" );
}
if (list.next == null || list.next.next == null ) {
//Only 1 node, or only 2 nodes. Take the head node as the intermediate node
return list;
}
Node slow = list;
Node fast = list;
while (slow.next != null && fast.next != null && fast.next.next != null ) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public  void  testFindMiddleNode ()  {
Node list = new Node<Integer>( 3 );
Node n1 = new Node<Integer>( 2 );
Node n2 = new Node<Integer>( 4 );
Node n3 = new Node<Integer>( 6 );
Node n4 = new Node<Integer>( 8 );
Node n5 = new Node<Integer>( 10 );
Node n6 = new Node<Integer>( 12 );
list.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
Node middle = findMiddleNode(list);
System.out.println( "The value of the middle node:" + middle.data);
}
public  static  void  main (String[] args)  {
t.testFindMiddleNode();
}

//Run Results: The
value of the intermediate node: 6
copy the code```

### 13.Stack: A linear table structure with restricted operations that only supports unidirectional stacking and popping.

#### 2. Use a linked list to implement the stack

```public  class  StackBasedOnLinkedList  {
public  class  Node  {
public  int data;
public Node next;
public  Node ( int data, Node next)  {
super ();
this .data = data;
this .next = next;
}
public  int  getData ()  {
return data;
}
}

private Node top;
public  void  push ( int data)  {
Node node = new Node(data, null );
if (top == null ) {
top = node;
} else {
node.next = top;
top = node;
}
}
public  int  pop ()  {
if (top == null ) {
return - 1 ;
}
int value = top.data;
top = top.next;
return value;
}
public  void  printAll ()  {
while (top!= null ) {
System.out.println( "Current value:" + top.data);
top = top.next;
}
}
public  static  void  main (String[] args)  {
t.push( 1 );
t.push( 2 );
t.push( 3 );
t.push( 4 );
t.push( 5 );
t.printAll();
}
}

//Run Results:
Current value: 5
Current value: 4
Current Value: 3
current value: 2
Current Value: 1
copy the code```

#### 3. Use 2 stacks to realize the browser's open, forward and backward functions

```public  class  SimpleBrowser  {
public  class  Node  {
public String data;
public Node next;

public  Node (String data, Node next)  {
super ();
this .data = data;
this .next = next;
}

public String getData ()  {
return data;
}
}

public  class  StackBasedOnLinkedList  {
public Node top;

public  void  push (Node node)  {
if (top == null ) {
top = node;
} else {
node.next = top;
top = node;
}
}

public String pop ()  {
if (top == null ) {
return  "The current stack is empty!" ;
}
String result = top.data;
top = top.next;
return result;
}

public  void  clear ()  {
while (top != null ) {
pop();
}
}

public  boolean  hasElements ()  {
}
public  void  printAll ()  {
Node curr = top;
while (curr != null ) {
System.out.println( "Current element value:" + curr.data);
curr = curr.next;
}
}
}

public String currentPage;

public  SimpleBrowser ()  {
this .backStack = new StackBasedOnLinkedList();
this .forwardStack = new StackBasedOnLinkedList();
}

public  boolean  canGoBack ()  {
return  this .backStack.hasElements();
}

public  boolean  canGoForward ()  {
return  this .forwardStack.hasElements();
}

public String goBack ()  {
if (canGoBack()) {
String url = this .backStack.pop();
this .forwardStack.push( new Node(url, null ));
this .currentPage = this .backStack.top == null ? Null : this .backStack.top.data;
return url;
}
return  null ;
}

public String goForward ()  {
if (canGoForward()) {
String url = this .forwardStack.pop();
this .backStack.push( new Node(url, null ));
this .currentPage = url;
return url;
}
return  null ;
}

public String open (String url)  {
this .forwardStack.clear();
this .backStack.push( new Node(url, null ));
this .currentPage = url;
return url;
}

public  static  void  main (String[] args)  {
SimpleBrowser t = new SimpleBrowser();
t.open( "url1" );
t.open( "url2" );
t.open( "url3" );
t.open( "url4" );
t.open( "url5" );
t.open( "url6" );
t.open( "url7" );
t.open( "url8" );
t.goBack();
t.goBack();
t.goBack();
t.goBack();
System.out.println( "Current Page:" + t.currentPage);
t.goBack();
t.goForward();
t.goForward();
System.out.println( "Current Page:" + t.currentPage);
t.open( "urlX" );
System.out.println( "Current page:" + t.currentPage);
}
}

//operation result
Current page: url4
Current page: url5
Current page: urlX
Copy code```

### 14. Queue: A linear table with limited operations, first in, first out, is a typical queue.

#### 3. Build an array-based queue

```/**
* Queue constructed as an array.
*/
public  class  QueueBasedOnArray  {
public String[] items;
public  int head, tail;
public  int size;

public  QueueBasedOnArray ( int capacity)  {
this .size = capacity;
this .items = new String[size];
head = tail = 0 ;
}

/**
* Determine whether the queue is empty
*
* @return
*/
public  boolean  isEmpty ()  {
return head == tail;
}

/**
* Determine whether the queue is full
*
* @return
*/
public  boolean  isFull ()  {
return tail == size;
}

/**
* Join the team
*
* @param item
* @return
*/
public  boolean  enqueue (String item)  {
//As long as the queue is full before, you cannot continue to add elements, even if you delete elements
if (isFull()) {
//The current queue is full
return  false ;
}
items[tail] = item;
tail++;
return  true ;
}

/**
* Departure
*
* @return
*/
public String dequeue ()  {
if (isEmpty()) {
return  null ;
}
String result = items[head];
return result;
}

/**
* Print all elements in the current queue
*/
public  void  printAll ()  {
if (isEmpty()) {
return ;
}
System.out.println( "All elements of the queue:" );
for ( int i = head; i <tail; i++) {
System.out.println( "Current element value:" + items[i]);
}
}
public  static  void  main (String[] args)  {
QueueBasedOnArray t = new QueueBasedOnArray( 6 );
t.enqueue( "1" );
t.enqueue( "2" );
t.enqueue( "3" );
t.enqueue( "4" );
t.enqueue( "5" );
t.enqueue( "6" );
t.enqueue( "7" );
t.printAll();
t.dequeue();
t.dequeue();
t.dequeue();
t.dequeue();
t.enqueue( "X" );
t.printAll();
}
}

//operation result:
All elements of the queue:
Current element value: 1
Current element value: 2
Current element value: 3
Current element value: 4
Current element value: 5
Current element value: 6
All elements of the queue:
Current element value: 5
current element value: 6
copy the code```

#### 4. Build an array-based queue, as long as the array has free space, you can continue to add elements

```public  class  DynamicQueueBasedOnArray  {
public String[] items;
public  int head, tail;
public  int size;

public  DynamicQueueBasedOnArray ( int capacity)  {
size = capacity;
items = new String[size];
head = tail = 0 ;
}

public  boolean  isEmpty ()  {
return head == tail;
}

public String dequeue ()  {
if (isEmpty()) {
return  null ;
}
String result = items[head];
return result;
}

/**
* Join the team
* When entering the queue, if the tail of the queue has reached the threshold, see if the head is at the position of 0 and not at the position of 0, indicating that the elements of the queue from the position of 0->head-1 have been taken out, and the queue still has space.
* The element should be moved, and then the new element should be added to the end of the queue.
* @param item
* @return
*/
public  boolean  enqueue (String item)  {
if (tail == size) {
if (head == 0 ) {
//The queue is full
return  false ;
} else {
//The queue is not full
//The positions from 0 to head-1 are empty
for ( int i = head; i <tail; i++) {
}
head = 0 ;
}
}
items[tail] = item;
tail++;
return  true ;
}

public  void  printAll ()  {
if (isEmpty()) {
return ;
}
System.out.println( "All elements in the current queue:" );
for ( int i = head; i <tail; i++) {
System.out.println( "Current element value:" + items[i]);
}
}

public  static  void  main (String[] args)  {
DynamicQueueBasedOnArray t = new DynamicQueueBasedOnArray( 6 );
t.enqueue( "1" );
t.enqueue( "2" );
t.enqueue( "3" );
t.enqueue( "4" );
t.enqueue( "5" );
t.enqueue( "6" );
t.enqueue( "7" );
t.enqueue( "8" );
t.printAll();
t.dequeue();
t.dequeue();
t.dequeue();
t.dequeue();
t.enqueue( "X" );
t.printAll();
}
}

//operation result:
All elements of the current queue:
Current element value: 1
Current element value: 2
Current element value: 3
Current element value: 4
Current element value: 5
Current element value: 6
All elements of the current queue:
Current element value: 5
Current element value: 6
Current element value: X
Copy code```

#### 5. Construct an unbounded queue based on a linked list

```/**
* Build a queue based on a linked list
* The linked list itself is unbounded, so the number of elements in the queue is not limited
*/
public  class  QueueBasedOnLinkedList  {
public  class  Node {
public String data;
public Node next;
public  Node (String data, Node next)  {
this .data = data;
this .next = next;
}
public  Node (String data)  {
this .data = data;
}
}

public Node tail;

public  void  enqueue (String data)  {
if (head == null ) {
head = tail = new Node(data);
} else {
tail.next = new Node(data);
tail = tail.next;
}
}
public String dequeue ()  {
if (head == null ) {
return  null ;
}
String data = head.data;
if (head == null ) {
tail = null ;
}
return data;
}
public  void  printAll ()  {
Node curr = head;
System.out.println( "All elements in the current queue:" );
while (curr != null ) {
System.out.println( "Current element value:" + curr.data);
curr = curr.next;
}
}
public  static  void  main (String[] args)  {
t.enqueue( "1" );
t.enqueue( "2" );
t.enqueue( "3" );
t.enqueue( "4" );
t.dequeue();
t.printAll();
}
}

//operation result:
All elements of the current queue:
Current element value: 2
current element value: 3
current element value: 4
copy the code```

#### 6. Build an array-based circular queue

1. Tail points to an index of an element that has not yet been stored. This is convenient for judging whether the queue is empty. Tail points to the'next', so when head==tail, the queue is empty.
2. If tail points to the last element in the queue, to determine whether the queue is empty, it is necessary to determine whether the element at the head position or the tail position is empty. In order to ensure that it is empty, the array at the corresponding position must be set every time the queue is left The element is left blank, and then it can be'head+1'.
1 and 2 are more visible, and tail points to the'next' to simplify the code.
3. In a circular queue built on the basis of an array, there must be 1 position to be wasted.
• Because tail points to the'next', it is the position where there is no element currently stored.
• The circular queue is circular, and this position can only be an index value on the ring.
• Unlike the acyclic pairs constructed by arrays, tail can be up to n, and n is not in the range of the array index value.
```public  class  CircleQueueBasedOnArray  {
public String[] items;
public  int head, tail;
public  int size;

public  CircleQueueBasedOnArray ( int capacity)  {
head = tail = 0 ;
size = capacity;
items = new String[size];
}

public  boolean  isEmpty ()  {
return head == tail;
}

public  boolean  isFull ()  {
return (tail + 1 )% size == head;
}

public  boolean  enqueue (String item)  {
if (isFull()) {
return  false ;
}
items[tail] = item;
tail = (tail + 1 )% size;
return  true ;
}

public String dequeue ()  {
if (isEmpty()) {
return  null ;
}
String result = items[head];
head = (head + 1 )% size;
return result;
}

public  void  printAll ()  {
if (isEmpty()) {
return ;
}
System.out.println( "All elements in the current queue:" );
for ( int i = head; i != tail; i = (i + 1 )% size) {
System.out.println( "Current element value:" + items[i]);
}
}
public  static  void  main (String[] args)  {
CircleQueueBasedOnArray t = new CircleQueueBasedOnArray( 6 );
t.enqueue( "1" );
t.enqueue( "2" );
t.enqueue( "3" );
t.enqueue( "4" );
t.enqueue( "5" );
t.enqueue( "6" );
t.printAll();
t.dequeue();
t.dequeue();
t.dequeue();
t.printAll();
t.enqueue( "11" );
t.enqueue( "12" );
t.enqueue( "13" );
t.enqueue( "14" );
t.enqueue( "15" );
t.printAll();
}
}

//Current running results:
//It can be seen from the printing results: In the circular queue built on the basis of arrays, 1 position will be wasted, in order for the tail to point to the'next'.
All elements of the current queue:
Current element value: 1
Current element value: 2
Current element value: 3
Current element value: 4
Current element value: 5
All elements of the current queue:
Current element value: 4
Current element value: 5
All elements of the current queue:
Current element value: 4
current element value: 5
current element value: 11
current element value: 12
current element value: 13
copy the code```

### 15. Recursion

#### 1. Conditions that can be solved by recursion

1. The solution of a problem can be decomposed into solutions of several sub-problems.
2. The original problem and the sub-problem are completely the same except for the different data scales.
3. The problem is decomposed into sub-problems and cannot be decomposed indefinitely.It must have a termination condition, that is, a recursive termination condition.

#### 2. Disadvantages of recursion

1. If the recursion level is too deep, it will cause a stack overflow.
• Taking JVM as an example, the depth of each thread stack is limited. If the number of recursion is too large, stack frames are constantly pushed onto the function call stack, and Stack Overfllow is triggered if the limit is exceeded.
2. Recursion may have double counting problems
• For example, f(n) = f(n-1) + f(n-2), f(n-1) = f(n-2) + f(n-3), f(n-2) is repeated Calculated 2 times
• As an example to avoid repeated calculations, the results of the previously specified parameters should be stored in a hash table
3. Each time the recursion is called, a stack frame is created and pushed onto the stack. The stack frame contains temporary variables. Multiple calls will increase the space complexity of the algorithm.
• Compared with the while loop, we can declare 1 variable and use it repeatedly in the while loop, with low space complexity
4. Recursion is'synchronous' and needs to wait for the result of the previous call.If the number of calls is too large, it will accumulate to a high time cost.

#### 3. Several recursive problems

##### 3.1. For n-stairs, you can go up 1 or 2 steps each time, how many ways are there in total?
```private Map<Integer,Integer> results = new HashMap<Integer,Integer>();
public  int  goStairs ( int n) {
if (n <= 1 ){
return  1 ;
}
if (n == 2 ){
return  2 ;
}
if (results.containsKey(n)){
return results.get(n);
}
return goStairs(n- 1 ) + goStairs(n- 2 );
}
Copy code```

### 16. How to evaluate a sorting algorithm: It is measured from three aspects: the execution efficiency of the sorting algorithm, the space complexity of the sorting algorithm, and the stability of the sorting algorithm.

#### 1. The execution efficiency of the sorting algorithm

1. Best case, worst case, average case time complexity.
• Some of the data to be sorted are close to order, and some are completely disordered. The different degree of order affects the execution time of sorting, and it is necessary to know the performance of the algorithm under different degree of order data.
2. Time complexity coefficient, constant, low order.
• Time complexity reflects the increasing trend of execution time when n is large, and coefficients, constants, and low-levels are ignored when expressed.
• However, in actual sorting scenarios, you may only encounter a small data size of less than 1000. Therefore, for different algorithms with the same order of time complexity, their coefficients, constants, and low-level must be considered.
3. The number of comparisons and the number of exchanges (movements).
• The sorting algorithm based on comparison will definitely involve comparison between elements and position exchange (or movement). Therefore, the number of comparison and exchange (or movement) should also be taken into consideration.

#### 2. Memory consumption of sorting algorithm

1. Like other algorithms, its memory consumption is measured by space complexity.
2. In-place sorting: specifically refers to a sorting algorithm whose space complexity is O(1).

#### 3. The stability of the sorting algorithm

1. Stability refers to: If there are elements with equal values in the sequence to be sorted, after sorting, the original order of elements with equal values remains unchanged.
2. After sorting, the original order between elements of equal value remains unchanged, which is called a stable sorting algorithm.
3. After sorting, the original order between elements of equal value changes, which is called an unstable sorting algorithm.
4. For example, a set of data should be sorted according to the attribute value of attr1 from large to small. When the attribute value of attr1 is equal, it is sorted according to the attribute value of attr2 from small to large.
• First sort by attr2 attribute value from smallest to largest
• Then use the stable sorting algorithm to sort from large to small according to attr1.

### 17. Bubble Sort

#### 3. One bubbling will move at least one element to the correct position. Repeat n times to complete the sorting of n data.

```public  class  BubbleSort  {
public  void  bubbleSort ( int [] arr)  {
if (arr == null || arr.length <= 1 ) {
return ;
}
int length = arr.length;
//moved is used to mark whether element interaction occurs for each bubbling. If no interaction occurs, it means that the current data has been sorted and the comparison can be aborted.
boolean moved = false ;
int temp;
for ( int i = 0 ; i <length; i++) {
moved = false ;
for ( int j = 0 ; j <length- 1 -i; j++) {
if (arr[j]> arr[j + 1 ]) {
temp = arr[j];
arr[j] = arr[j + 1 ];
arr[j + 1 ] = temp;
moved = true ;
}
}
if (!moved) {
System.out.println( "Bubbling times:" + (i + 1 ));
break ;
}
}
}

public  static  void  main (String[] args)  {
BubbleSort t = new BubbleSort();
int [] arr = { 12 , 54 , 32 , 8 , 6 , 3 , 111 , 45 };
t.bubbleSort(arr);
Arrays.stream(arr).forEach(System.out::println);
}
}

//Run Results:
bubbling times: . 6
. 3
. 6
. 8
12 is
32
45
54 is
111
copy the code```

#### 4. Time complexity, space complexity, and stability of bubble sort

1. Best-case time complexity: O(n)
• All elements are in order.
• After bubbling once and finding that there is no element exchange, the sorting is terminated.
2. Worst case time complexity: O(n^2)
• All elements are completely in reverse order
• bubbling n times.
3. Average case time complexity: O(n^2)
• Order: the number of correctly sorted pairs of elements in the original array
• Full order: The original array is completely ordered, and its order is called full order
• Reverse order: the number of wrongly sorted element pairs in the original array
• Reverse order degree = full order degree-order degree
• The degree of reversal is the number of times the original array needs to perform element swaps
• Full order degree = n*(n-1)/2, the average reverse order degree is full order degree/2 = n*(n-1)/4
• The number of comparison exchanges must be greater than the number of exchanges, and the worst time complexity is O(n^2). So the average time complexity of bubble sorting is O(n^2)
4. The space complexity is O(1), which is a stable sort.

### 18. Insertion sort

#### 3. Repeat the whole process until the unsorted interval elements are empty.

```public  class  InsertSort  {
public  void  insertSort ( int [] a)  {
if (a == null || a.length <= 1 ) {
return ;
}
int value;
int j;
for ( int i = 1 ; i <a.length; i++) {
value = a[i];
j = i- 1 ;
for (; i >= 0 ; j--) {
if (a[j]> value) {
a[j + 1 ] = a[j];
} else {
break ;
}
}
a[j + 1 ] = value;
}
}

public  static  void  main (String[] args)  {
InsertSort t = new InsertSort();
int [] a = { 1 , 2 , 31 , 32 , 19 , 18 , 17 , 16 , 61 , 58 , 54 };
t.insertSort(a);
System.out.println( "Run result:\n" );
Arrays.stream(a).forEach(System.out::println);
}
}

operation result:

1
2
16
17
18
19
31
32
54
58
61 is
duplicated code```

### 19. Select Sort

#### 2. Every time the smallest element is found in the unsorted interval, it is placed at the end of the sorted interval.

```public  class  SelectSort  {
public  void  selectSort ( int [] a)  {
if (a == null || a.length <= 1 ) {
return ;
}
int minIndex;
int temp;
for ( int i = 0 ; i <a.length- 1 ; i++) {
minIndex = i;
for ( int j = i + 1 ; j <a.length; j++) {
if (a[j] <a[minIndex]) {
minIndex = j;
}
}
temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}

public  static  void  main (String[] args)  {
SelectSort t = new SelectSort();
int [] a = { 3 , 5 , 7 , 2 , 4 , 6 , 89 , 40 };
t.selectSort(a);
System.out.println( "Select the sorted array:" );
Arrays.stream(a).forEach(System.out::println);
}
}

Select the sorted array:
2
. 3
. 4
. 5
. 6
. 7
40
89
duplicated code```

### 20. The time complexity of bubble sort and insertion sort is the same, both are O(n^2). Why is insertion sort more common?

#### 2. Comparison of element exchange between the two

```//Bubble sort
if (a[j]> a[j + 1 ]){
temp = a[j];
a[j] = a[j + 1 ];
a[j + 1 ] = temp;
moved = true ;
}

//Insert sort
if (a[j]> value){
a[j + 1 ] = a[j];
} else {
break ;
}
Copy code```

### 21. Merge Sort

#### 3. Pseudo code

```public  void  sort ( int [] arr)  {
splitSort(arr, 0 , arr.length- 1 );
}
public  int [] splitSort( int [] arr, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return  new  int [] {arr[startIndex] };
}
int midIndex = (startIndex + endIndex)/2 ;
int [] a1 = splitSort(arr, startIndex, midIndex);
int [] a2 = splitSort(arr, midIndex + 1 , endIndex);
int [] result = merge(a1, a2);
return result;
}
public  int [] merge( int [] a1, int [] a2) {
int [] result = new  int [a1.length + a2.length];
int i1 = 0 ;
int i2 = 0 ;
for ( int i = 0 ; i <result.length; i++) {
if (a1[i1]> a2[i2]) {
result[i] = a2[i2];
i2++;
} else {
result[i] = a1[i1];
i1++;
}
}
return result;
}
Copy code```

### 22. Quick Sort

#### 3. Pseudo code

```public  void  sort ( int [] arr) {
quickSort(arr, 0 , arr.length- 1 );
}
public  void  quickSort ( int [] arr, int startIndex, int endIndex) {
if (arr == null || startIndex >= endIndex){
return ;
}
int pivot = partition(arr, startIndex, endIndex);
quickSort(arr, startIndex, pivot- 1 );
quickSort(arr, pivot + 1 , endIndex);
}
public  int  partition ( int [] arr, int startIndex, int endIndex) {
int value = arr[endIndex];
int pivot = endIndex;
for ( int i = startIndex; i<endIndex- 1 ; i++){
if (a[i ] <value){
if (pivot == endIndex){
if (i != startIndex){
swap(i, startIndex);
}
pivot = startIndex;
} else {
swap(pivot + 1 , i);
pivot++;
}
}
}
if (pivot != endIndex){
pivot = pivot + 1 ;
swap(endIndex, pivot);
}
return pivot;
}
Copy code```