Comparison of data structure knowledge points
1. Summarize the difference between contiguous List and Linked List
The list is stored in memory in order. Elements are stored in memory as contiguous memory locations and are more suitable for random access, but insertion or deletion of elements is slower and the size of the array must be specified at the time of array declaration. Chained lists are not stored in memory sequentially. Each element holds the address of the next element. It does not support random access, but insertion or deletion of elements is faster and the size of the linked table is variable.
2.Summarize the difference between contiguous stack and Queue
Stack: A stack is a linear data structure in which elements can be inserted and deleted only from one side of the list, called the top. A stack follows the LIFO (Last In First Out) principle.
Queue: A queue is a linear data structure in which elements can be inserted only from one side of the list called rear, and the elements can be deleted only from the other side called the front. The queue data structure follows the FIFO (First In First Out) principle.
3. Summarize the difference of the following operations between Contiguous List and Singly Linked List:
①. Retrieve Operation检索，查找
The Contiguous List supports random access and can return the element at the specified position directly, with O(1) time complexity.
A Singly Linked List does not support random access and requires traversing over the nodes, with O(n) time complexity.
②. Replace Operation替换
The Contiguous List directly changes the element at the position that needs to be replaced. A Singly Linked List needs to be checked to find the node first, then the pointer is modified
③. Clear Operation清空
Since the nodes of a Contiguous List are dynamically assigned, single-linked lists need to be cleared manually one by one, while Singly Linked List can be cleared directly by letting the number of valid data go to zero.
④. Insert Operation插入
Contiguous List need to be traversed one by one from back to front and involve movement of elements, single linked tables also need to be traversed to find the position, but there is no movement of elements, just change the pointer directly
⑤. Delete Operation删除
Deleting an element from a contiguous list requires moving that element, and all the numbers after it are moved forward after the deletion. In contrast, a single-linked table first finds a specific location and changes the pointer pointing to it.
4. Summarize the similarities and differences between Circular Queue and Singly Linked Queue:
Both circular queues and chained queues are linear tables that follow the first-in, first-out (FIFO) principle. Circular queues are stored sequentially, with the pointer to the last element pointing to the head node. Chained queues are non-sequential storage.
5. Sequential Search vs. Binary Search
They are both algorithms that search through a list to find a particular entry.
The elements of a Sequential search can be arranged in any order, while in a binary search, the elements must be arranged in order.
Sequential search is not suitable for large data sets, and binary search is suitable for large data sets because it takes less time.
| Best time complexity | worst time complexity | |
|---|---|---|
| Sequential Search | O(1) | O(n) |
| Binary search | O(1) | O(logn) |
6. Average Time Complexity/Best Time Complexity/Worst Time Complexity/Space Complexity/Stability of each Sort
| Average time complexity | Best time complexity | Worst time complexity | Space complexity | Stability | |
|---|---|---|---|---|---|
| Quick sort | O(nlogn) | O(nlogn) | O(n^2) | O(logn)辅助栈 | N |
| Merge sort | O(nlogn) | O(nlogn) | o(nlogn) | o(n) | Y |
| Heap sort | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | N |
| Insertion sort | O(n^2) | O(n) | O(n^2) | O(1) | Y |
| Selection sort | O(n^2) | O(n^2) | O(n^2) | O(1) | Y |
7. Quick Sort for one turn/Shortness of Quick Sort/Improvement Method
Drawback :First of all, it is unstable, the speed of the algorithm depends heavily on the partitioning operation, and if it does not partition well, the speed may drop to O(N^2) in the worst case (for an array that is already sorted).
Solution: Compare the keywords of the elements in the first, middle and last positions of the data to be ranked, and take the median value of the three as the base element
8. Prim Algorithm with Kruskal Algorithm
Prim Algorithm and Kruskal Algorithm are all Greedy algorithm. Prim’s Algorithm looks for the vertex that is closest to the joined vertex. The time complexity is O(n2),Suitable for solving edge-dense MST. Kruskal’s Algorithm The algorithm is to find the closest vertex to the fixed vertex distance. The time complexity is O(eloge),which is suitable for finding the MST with sparse edges.