I. Data structure

  • What is a data structure?

Data structures are the way computers store and organize data

There are three types of data structures: linear structure, tree structure, and graph structure. Each type of data structure includes the following types:

Two. Linear table

  • A linear list is a finite sequence of n elements of the same type (n>=0)

  • A1 is the first node, and an is the last node.
  • A1 is the precursor and successor of A2
  • Common linear tables are arrays, linked lists, stacks, queues, and hash tables.

3. Array

  • An array is a linear list of sequentially stored elements with contiguous memory addresses

  • Disadvantages of arrays: You can’t change the size of arrays dynamically

Dynamic class design requirements Design principles:

The interface design is as follows:

  • size

The number of member variables in an array

  • clear

Size =0 if the array member variable is generic, size=0 if the array member variable is basic, size=0 if the array member variable is object, size=0, loop through the array to set the value of each member variable to NULL

  • add

By default, the data is added to the last bit of the array. Add element directly to index=size, then size++

  • print

Override the corresponding print method to customize the print content. For example, if you print an array in Java, the class name is printed by default. By default, you call the toString method of the array. Understand the train of thought

  • remove

If the array member variable is generic, if it is a basic data type, when deleting the data whose index=n, move the data after index=n in sequence to the range of index=n-size-1. Index =n-size-1; size–; delete the last array; size– represents the subscript value of the last array

  • add_index

Size = old size+1, traversal the old array, traversal the range (old size-1), traversal the old array, traversal the range (old size-1) to index=n, Move the old array index= (old size-1) to the new array size, and finally insert the new array index=n

  • indexOf

If the incoming data is NULL, just loop through the array to find the index with null subscript. If the passed data is not null, loop through the passed data with the original array data, use equals to check whether the data is equal, and return the corresponding index

  • The interface test

Assert tests the interface, or simply prints the data

  • Dynamic capacity

The idea of dynamic capacity expansion is to apply for a new block of contiguous address memory space, which is n times the size of the original array, and then copy the data in the original array to the new array, destroying the memory space of the original array.

  • The generic

The purpose of generics is to make dynamic arrays more generic. Array, where E is generic, is a generic type. In Java, generics can only hold object data types, but basic data types are not available. To specify the generic type in the declaration array,

  • Object type

When an array holds object type data, the actual storage distribution is as follows: The array holds the memory address of the object, and the memory address refers to the object allocated in the heap space

  • equals

In Java (Java based on the Java language), the equals method is used to determine whether or not a comparison object is equal. If you do not override equals, the default memory address of the comparison object is the memory address. If you override equals, you can specify the type of comparison

  • A null value processing

Can I store null data? The answer is yes. If you pass in a null, the default value for index=n is null, but fetching index=n may cause an error because the object is null

  • Dynamic arrays have an obvious drawback: they can be a huge waste of memory space

4. Linked List

  • A linked list is a linear list of chained storage where the memory addresses of all elements are not necessarily contiguous
  • Whereas dynamic arrays waste space, linked lists allocate storage space only when they are used
  • Data stores are shown as follows:

  • Dynamic design linked lists

Rule: When compiling linked lists, pay attention to boundary tests, index=0, size, size-1, etc.

  • size
  • clear

Size =0, then set the first pointer to NULL. You do not need to set Node next to null

  • add

Insert a Node element at index=n, make the next pointer to the newly inserted Node element index=n-1, and the next pointer to the newly inserted Node element index=n, and size++

  • remove

If index=0, find first, first.next. Next where index=index+1; If the index! Index =n+1; index=n+1

  • Get the node corresponding to index

I =0; I =0; I =0; I <index node = node.next, return the last node.

  • indexOf

If the element is null, the linked list is iterated to get Node, and then the data stored in Node is compared to null. If it is not null, the Node is iterated through the linked list and compared to the data stored in the Node.

  • Exercise – Remove a node from a linked list

Delete the value of this node, change the next pointer to this node, assign the value of the next node to be deleted to Node, and assign the node.Next-next pointer to the Node.next pointer

  • Exercise – Reverse a one-way linked list

Generally, the implementation effect of one-way linked list considering inversion is as follows:

Recursive: Create this algorithm

Non-recursive: First declare a newHead pointer to null, then set the head. Next pointer to the newHead pointer, then set the newHead pointer to the node corresponding to head, and then set head to the next node. When we point head. Next to newHead, there is no pointer to the next node, so we initially create a TMP pointer to head. Next.

  • Exercise – Determine if a linked list has rings

Judging by the speed and slow pointer, if there is a loop, fast and slow will meet, similar to the playground running circle, otherwise there is no loop.

The Java code in the video is as follows:

If fast or fast.next is null, the null pointer will be null.

  • Virtual head node

Sometimes in order to simplify the code and unify the processing logic of all nodes, it is possible to add a virtual head node (which does not store data) at the front.

Note: after adding the virtual head node, first refers to the virtual head node, first. Next refers to the node whose index=0

  • Array complexity analysis

Complexity analysis is generally divided into three directions: best-case complexity, worst-case complexity, and average case complexity. The complexity analysis of array and linked list mainly analyzes the methods of adding (add) deleting (remove) changing (set) looking up (get) and so on.

First look at the array:

Get method code:

The time complexity of get method is O(1).

Set method code:

The time complexity of set method is O(1).

Add method code:

The time complexity of add method can be divided into three types:

Best case: Add element at last, no need to move element, all time complexity O(1);

Worst-case scenario: add the first element, and move the entire array, all in O(n) time, where n represents the size of the data, not the value of the data, and move the array as many times as the array size.

The average case: Add elements anywhere in the middle and move them as many times as (1+2+3… +n)/n=1/2*n, all time complexity is O(n);

Remove method code:

The time complexity of remove method is divided into three types:

Best case: last remove element, no need to move element, all time complexity O(1);

Worst case: remove the first element, move the entire array element, all time complexity O(n), where n represents the size of the data, not the value of the data, move as many times as the array size;

Average case: remove elements anywhere in the middle, the number of moves required is: (1+2+3… +n)/n=1/2*n, all time complexity is O(n);

Array complexity summary: If it is set/get, the time complexity is O(1); If it’s an Add /remove element, the average time complexity is O(n)

  • Linked list complexity analysis

  • Array and linked list complexity comparison results are as follows

  • Amortized complexity

After several consecutive cases of low complexity and several cases of high complexity, use the amortized complexity, which is the best case of amortized complexity

  • The reduction of an array

If the memory is tight and dynamic data has a lot of free space, you can consider the operation.

  • Complexity oscillation

5. Bidirectional linked lists

You can make linked lists more comprehensive

  • clear
size=0;
first=null;
last=null;

Copy the code
  • add

  • remove

  • The interface test

Assert test

  • Two-way linked list VS unidirectional linked list

For the same deletion operation with the same complexity, the operation steps of bidirectional linked list are half less than that of unidirectional linked list. All bidirectional linked lists are highly efficient

  • Bidirectional linked lists VS dynamic arrays

Unidirectional circular linked lists

  • add

When you add, you have to think about size equals 0

  • remove

Make sure that size is equal to 1

  • The interface test

Assert test

7. Bidirectional circular linked lists

  • add

  • remove

  • A static linked list

  • Array optimization ideas

V. Stack

  • 1. The concept of stack
  • A stack is a special kind of linear table that can only proceed at one end
  • The operation of adding elements to the stack, commonly called push, is pushed
  • The operation of removing an element from the stack, commonly called pop, is removed from the stack (only the top element can be removed, also called “popping the top element”)
  • Here the concept of stack is different from stack space, which is now a data structure and stack space is a kind of memory
  • The dynamic array custom stack is preferred

  • 2. Stack data structure interface design

Based on push and POP principles, you don’t want to design weird interfaces

  • Stack application – browser forward and backward

Use two stacks to store data

Back up: Pops the top element from 1 into 2

Forward: Pops the top element from 2 into 1

New input data: Whenever there is a new input element, no matter how much data there is in 2, empty it and put the new input element in 1 as the top element on the stack

  • Exercise – Valid parentheses

Take advantage of the first-in, first-out feature of the stack to answer this question

Code implementation

6. Queue

  • A queue is a special kind of linear table that can only operate at both ends
  • Rear: You can only add elements from the rear of the queue, usually called enQueue
  • Queue head (front) : Only elements can be removed from the queue head, usually called deQueue
  • First In First Out, FIFO
  • Custom queues with bidirectional lists are preferred, because queues operate from head to tail and are more efficient than queues with dynamic arrays

  • Queue interface design

  • Exercise – Implement queues with stacks

Let’s do it with two stacks

Vii. Deque

  • A dual-ended queue is a queue that can be added or deleted at both ends

  • Deque is short for double ended Queue

  • Interface design of two – end queue

Circle Queue

  • The loop queue is implemented using arrays at the bottom, which can also be seen as an optimization of arrays
  • Circular queues are single-ended by default
  • Circular double-ended queue: a circular queue that can be inserted and deleted at both ends

  • Custom loop queue code

  • Circular queue capacity expansion

The principle of capacity expansion is to point the front of the original queue to the index=0 of the new memory, and then store the front to the end of the queue

Nine. Circular double – ended queue

See the video for the lecture