Learn more about Java basics
This series of notes is based on the geek Time course data Structures and The Beauty of Algorithms
This directory
- Complexity analysis
- An array of
- The list
- The stack
- The queue
Complexity analysis
The best-case time complexity is, in the best case, the time complexity of executing this code. The worst-case time complexity is, in the worst case, the time complexity of executing this code.
Average case time complexity, taking into account the probability of each case, should be called weighted average time complexity or expected time complexity.
Amortized time complexity, and its corresponding analysis method, amortized analysis (or amortized analysis). A data structure for a set of continuous operation, the time complexity in most cases is very low, only a few cases of high time complexity and the and the coherent temporal relationship between operation, this time, we can put together a set of operations analysis, look to whether can high time complexity of the operation of time consuming, Amortized to other operations that are less time complex. Moreover, in the case where amortized time complexity analysis can be applied, the general amortized time complexity is equal to the best-case time complexity.
An array of
The time of an array lookup operation is not O(1). Even a sorted array, binary lookup, is order logn. Correct: Arrays support random access with a time complexity O (1) based on subscripts.
Inefficient inserts and deletes
- Insert: average O(n) from best O(1) to worst O(n)
- Insert: If the array is out of order, when inserting a new element, you can move the element in the KTH position to the end of the array and insert the core element into the KTH position, where the complexity is O(1). The author illustrates with examples
- Delete: average O(n) from best O(1) to worst O(n)
- Multiple deletions are centralized to improve deletion efficiency and record the deleted data. Each deletion does not move data, but records that the data has been deleted. When the array has no more storage space, a real deletion is triggered again. That is, the JVM tag cleanup garbage collection algorithm.
Why are arrays numbered from 0 instead of 1 in most programming languages?
In terms of offset, a[0] 0 is the offset. If you count from 1, you get an extra K-1. Increased CPU burden. Why do I write for(int I = 0; i<3; I ++) instead of for(int I = 0; i<=2; I++). The first one can just say 3-0 = 3 and have three numbers, while the second one is 2-0+1 and has one more addition, which is annoying.
The list
What is a linked list?
- Like an array, a linked list is a linear list.
- From the perspective of memory structure, the memory structure of linked list is discontinuous memory space, which is a data structure that connects a group of scattered memory blocks in series for data storage.
- Each memory block in the linked list is called a Node. In addition to storing data, the node also needs to record the address of the next node in the chain, that is, the successor pointer next.
Why do you use linked lists? That’s the nature of linked lists
- O(1) level for high efficiency in data insertion and deletion (just changing the pointer), O(n) level for low efficiency in random access (traversing from head to tail).
- Compared to arrays, memory space is more expensive because each node that stores data needs extra space to store subsequent Pointers.
Commonly used linked lists: single linked lists, circular linked lists and bidirectional linked lists
- Singly linked lists
- Each node contains only one pointer, the successor pointer.
- A singly linked list has two special nodes, the first node and the last node. Why special? The first node address represents the entire list, and the next pointer to the last node points to the null address.
- Performance: The time complexity of node insertion and deletion is O(1), and the time complexity of node search is O(n).
- Circular linked list
- They are the same as the single-linked list except that the subsequent pointer of the tail node points to the address of the first node.
- This applies to storing cyclic data, such as the Joseph problem.
- Two-way linked list
- In addition to storing data, a node has two Pointers to the previous node address (prev) and the next node address (next).
- The precursor pointer to the first node, prev, and the successor pointer to the last node point to an empty address.
- Performance features: Compared with a single linked list, storing the same data consumes more storage space. Insert and delete operations are O(1) more efficient than single linked lists. Take the deletion operation as an example. The deletion operation can be divided into two types: deleting a node with a given data value and deleting a node with a given node address. In the former case, both singly and bidirectionally linked lists need to be traversed from beginning to end to find the corresponding node for deletion, with time complexity O(n). In the second case, the delete operation must find the precursor node. Single-linked lists need to traverse from beginning to end until P ->next = q, with time complexity O(n), while bidirectional lists can directly find the precursor node, with time complexity O(1).
For an ordered list, the efficiency of a bidirectional list is higher than that of a single list. Because we can record the position P searched last time, each time we search, we decide whether to search forward or backward according to the relationship between the value to be searched and the size of P, so we only need to search half of the data on average.
- Bidirectional cyclic lists: the first node’s precursor points to the last node, and the last node’s successor points to the first node.
Array or linked list?
- Time complexity of insert, delete, and random access Array: The time complexity of insert and delete is O(n), the time complexity of random access is O(1). Linked list: the time complexity of insertion and deletion is O(1), and the time complexity of random access is O(n).
- An array of drawbacks
1) If the memory space is large, such as 100M, but there is no continuous space of 100M, the application will fail, even though the available memory space exceeds 100M. 2) The size is fixed. If the storage space is insufficient, it needs to be expanded. Once the capacity is expanded, data replication needs to be performed, which is very time-consuming.
- List disadvantages
1) More memory space is consumed because extra space is needed to store pointer information. 2) Frequent insertion and deletion operations on linked lists can lead to frequent memory requests and frees, which can easily cause memory fragmentation and, in the case of The Java language, can lead to frequent GC (automatic garbage collector) operations.
- How to choose?
Array is easy to use, in the implementation of the use of contiguous memory space, you can use the CPU buffer mechanism to preread the array of data, so the access efficiency is higher, and linked lists in memory is not contiguous storage, so CPU cache is not friendly, there is no way to preread. If the code is very memory intensive, arrays are more suitable.
Common linked list operations:
- Single-linked list inversion
- Detection of linked list ring
- Merge two ordered lists
- Delete the NTH node from the penultimate list
- Select middle node of linked list
- Array based LRU
- LRU based on linked List
- Single linked list judgment palindrome string
The stack
What is a stack?
- Last come out, first come out, this is the typical “stack” structure.
- In terms of the operation nature of the stack, it is an “operation-constrained” linear table, allowing only insertion and deletion of data at the end.
Why do you need a stack?
- Stack is a kind of data structure with limited operation. Its operation characteristics can be realized by array and linked list.
- However, any data structure is an abstraction of a particular application scenario, and arrays and linked lists, while more flexible to use, expose almost all operations and risk misoperations.
- Therefore, when a data set only involves inserting and deleting data at one end and satisfies the last-come-first-out, first-come-first-out operation characteristics, we should prefer the data structure of stack.
How to implement the stack?
Public class Stack {public void push(Item Item){} public void push(Item Item){} public void pop(){} public Boolean isEmpty(){} Public int size(){} public Item peek(){}} public Item peek(){}Copy the code
The queue
What is a queue?
- First come first, this is the typical “queue” structure.
- Two operations are supported: enqueue(), which puts a data to the end of the queue; Dequeue () takes an element from the queue head.
- So, like a stack, a queue is a linear table with limited operations.
How to implement queues?
public interface Queue { public void enqueue(T item); Public T dequeue(); Public int size(); Public Boolean isNull(); // Null}Copy the code
Queue implementation
- Sequential queue
- Linked list implementation
- Circular queue (array based)