If so, why not now? – 2021/03/13
King for algo
1. How to analyze the execution efficiency and resource consumption of statistical algorithms
1. What is complexity analysis
- Data structures and algorithms solve ‘how to make code run faster and save storage ‘.
- The performance of data structures and algorithms needs to be evaluated from two dimensions of execution time and occupied space.
- Time complexity and space complexity are used to describe performance problems respectively, which are collectively called complexity.
- Complexity describes the relationship between algorithm execution time or space occupied and the growth of data size.
2. Why complexity analysis
- Run the code aside, and get the algorithm execution time and memory usage through statistical monitoring, so as to evaluate the algorithm performance, called post-statistical method.
- In contrast to performance testing, complexity analysis is independent of hardware environment and data size. It is efficient, instructive and can estimate rough operating performance in advance.
- Ability to write code that performs better
3. How to do complexity analysis: big O notation
4. Source of big O notation
- The execution time of the algorithm is proportional to the total number of times each line of code is executed: T(n) = O(f(n))
- T(n) : total algorithm execution time
- F (n) : total number of executions per line of code
- N: Indicates the size of the data
- O: indicates that the execution time of the code is proportional to the number of times per line of code
5. Features of big O notation
- Taking time complexity as an example, time complexity describes the increasing and changing trend of algorithm execution time and data size. Constants, low orders and coefficients in the results do not have a decisive influence on this increasing trend, so these terms are ignored in time complexity analysis.
6. Time complexity analysis
- Look at the high frequency of a single piece of code: for example, in loops, look only at the segment that has the most loops
- Maximization of multiple pieces of code: for example, if a piece of code has a single layer loop and a multi-layer loop, then take the complexity of the multi-layer loop.
- Product of nested code: such as recursion, multiple loops, etc.
- Add multiple scales: for example, if the method has two parameters that control the parameters of two cycles, the complexity is the sum of the two.
7. Common complexity levels
7.1. Polynomial magnitude
- As the size of the data increases, the time taken to execute the algorithm increases in proportion to the polynomial.
- Including: constant order (O (1)), the logarithmic order (O (logn)), linear order (O (n)), linear logarithmic order (O (nlogn)), square order (O (n ^ 2)), cubic order (O (n ^ 3))
7.2. Non-polynomial magnitude
- With the increase of data size, the execution time of non-polynomial algorithm will increase dramatically, and the performance of this kind of algorithm is very poor.
- Including: exponential order (O(2^n)), factorial order (O(n!) )
Complexity 8.
- Complexity is also called progressive complexity, including time complexity and space complexity, which is used to analyze the growth relationship between algorithm execution efficiency and data size.
- The higher the complexity of the algorithm, the lower the execution efficiency.
- Almost all data structures and algorithms cannot run out of complexity: O(1), O(n), O(logn), O(nlogn), O(n^2)
2. Analyze the best, worst, average and amortized time complexity
1. Best case time complexity
- In the best case, the time complexity of executing a piece of code.
Worst-case time complexity
- In the worst case, the time complexity of executing a piece of code.
3. Weighted average or expected time complexity
- Taking into account the probability of each run, we get complexity.
4. Most of the time there is no need to distinguish between best, worst, and average time complexity
- Only when there is an order of magnitude difference in time complexity between different cases will the three types of complexity be distinguished.
5. Amortize the time complexity
5.1. Amortized time complexity is a special average time complexity
5.2. Usage Scenarios:
- The time complexity of a set of continuous operations on a data structure is low in most cases, but high in a few cases, and there is a coherent sequential relationship between the operations
- For example, if n-1 O(1) is followed by 1 O(n), then O(n) can be amortized to n-1 O(1), then the amortized time complexity is still O(1).
5.3. In scenarios where amortized complexity can be applied, general amortized complexity is the best-case time complexity.
- Exception: for example, n-1 O(1) followed by 1 O(n^2), then the amortized time complexity is O(n).
3. Arrays: Why are arrays numbered from 0 in many programming languages
An array of 1.
1.1. An array is a linear table data structure. It uses a contiguous set of memory Spaces to store a set of data of the same type
1.2. The linear table
- A linear table is a structure in which data is arranged as a line.
- The data on a linear table, at most, can only go in two directions.
- Arrays, lists, queues, stacks are all linear table structures
1.3. Nonlinear tables
- In a nonlinear table, there is no simple contextual relationship between data
- Such as binary trees, heaps, graphs are nonlinear tables
1.4. Contiguous memory space and same type of data
- These two features make arrays randomly accessible
- Random access refers to data access by randomly selecting subscripts
- Inserting and deleting an array is inefficient because a lot of moving is required to keep the memory space of the array elements continuous
1.5. How does an array implement random access to array elements by subscript
- Int [] a = new int[10];
- The computer allocates a contiguous memory space from 1000 to 1039 (because 1 int is 4 bytes).
- The first address of the memory block, base_address, is 1000.
- When a computer needs to access an element with subscript I in an array, it first computes the memory address of that element
A [I]_address = base_address + data_type_size * I Data_type_size indicates the size of each element in the array,intType data each is4Bytes.Copy the code - The time to find elements in an array, even a sorted array, with binary search, is order logn.
1.6. Inefficient array insertion and improvement
- If the array is ordered, and we insert an element at position K, in order to empty out K, the elements from the original position K to N have to be moved back, order N time.
- If the data stored in the array is irregularly treated as a collection of stored data, in order to improve performance, the element in the original K position can be moved to the end of the array, and the new element can be placed in position K, the time complexity is O(1).
1.7. Inefficient deletion and improvement of arrays
- Delete the element at position K, and move it for memory continuity, order n time.
- To improve performance, multiple deletions can be performed at one time.
- For example, to delete elements A, B, and C3, each deletion does not actually delete the data, but only records that the data has been deleted.
- When there is no more space in the array to store the data, another real delete is triggered, so that only one data move is performed.
- Delete performance improvements, similar to the tag collation algorithm in the JVM garbage collection algorithm
- First find gC-root and mark the non-garbage data
- Garbage data is removed and non-garbage data is moved to make memory compact
2. Array out of bounds
2.1. Different languages encounter array transgressions, and the corresponding compiler handling logic is different
- Exceptions are thrown for Java, not for C
- As far as C is concerned, no error is reported as long as the memory address computed by the array offset is available
2.2. Many computer viruses exploit the vulnerability of arrays out of bounds to access illegal addresses to attack systems.
3. Can containers completely replace arrays?
3.1. Java provides an ArrayList, which is the underlying array.
- ArrayList encapsulates insert, delete, and so on
- ArrayList supports automatic expansion
- Capacity expansion involves memory application and data relocation, resulting in low performance. If you have determined the amount of data in advance, you are advised to specify the initial capacity at the beginning to avoid multiple capacity expansion
3.2. ArrayList cannot store basic types, such as int and long, which are encapsulated as Integer and long, and unboxing can affect performance.
3.3. Arrays can be used directly if the amount of data is known in advance and without most of the methods provided by ArrayList.
Integer[][] is better than ArrayList<ArrayList>
3.5. For extreme performance, use arrays, and container classes for scenarios with less stringent performance requirements.
4. Why do array subscripts start at 0
4.1. Probably due to historical reasons, the original programming language started at 0 and continued later
4.2. The memory model of array storage determines that starting from 0 can reduce CPU computation
- An array is a contiguous array of data of the same type. The real meaning of the subscript is the offset relative to the address of the head of the array’s memory block
- The memory address with subscript K starting from 0 is:
a[k]_address = base_address + k * type_size Copy the code - The memory address with subscript K starting from 1 is:
a[k]_address = base_address + (k-1) * type_size Copy the code - The subscript starts at 1, and the CPU executes one more subtraction instruction for each random access to an array element.
5. Addressing a two-dimensional array (5 rows and 8 columns)
- Take a[3][2], the third element in line 4. The address is the first address of the array memory block + the full 3 rows + the second column of line 4
- a[3][2] = base_address + type_size * (8 * 3 + 2)
4. Linked list (1) : How to implement LRU cache elimination algorithm
1. Caching is a technique that improves data read performance by trading space for time.
- The size of the cache is limited. When the cache space is used up, the cache elimination policy determines which data should be cleaned and which data should be retained.
2. Cache elimination strategy
- FIFO/First In,First Out
- /LFU/Least Frequently Used
- Least Recently Used policy /LRC/Least Recently Used
3. Linked list: A series of discrete memory blocks connected by Pointers
- Most common linked lists: single linked lists, double linked lists, circular linked lists
- The first node of a linked list is called a head node, and the last node is called a tail node
- The header is used to record the base address of the linked list, through which the whole list can be traversed
- List deletion, insert time is O(1)
- Regardless of the time complexity of finding and locating the node
4. Loop lists
- Circular linked list is a special single linked list.
- The advantage of a circular list is that it is convenient to go from the end of the chain to the head of the chain.
- Circular linked lists are suitable when the data to be dealt with has a circular structure, such as Joseph’s problem.Didn’t see the solution.
- An Ali pen test: I am how to use a line of code to solve the Joseph ring problem
5. Bidirectional linked lists
- Bidirectional linked lists support two directions, each node has a successor pointer next to the next node, and a precursor pointer prev to the previous node.
- Bidirectional lists support O(1) to find the preV, which makes bidirectional list deletion and insertion performance better than single-linked lists in some cases.
6. Delete bidirectional linked list
- Removing a data from a linked list involves two cases:
- Delete “node whose value is equal to a value” from linked list
- Delete “node to which a specific pointer points” from linked list
- Delete “node whose value is equal to a value” from linked list
- So whether it’s a singly linked list or a bidirectionally linked list, the first thing you have to do is go through and find this node,O(n).
- The time complexity of simple deletion is O(1)
- This type of deletion, both are order n.
- Delete “node to which a specific pointer points” from linked list
- In this case, the nodes to be deleted are already identified and no traversal is required.
- The precursor of this node:
- The single linked list does not know, but still traverses until p ext = target, indicating that p is the precursor of target. The time is order n.
- The bidirectional list finds target.prev directly. The time complexity is O(1).
7. Bidirectional list insertion
- Insert 1 node in front of a specified node in a bidirectional list in order of 1 time
- A singly linked list is O(n), because it traverses to find the previous node at the specified node
8. For an ordered list, bidirectional lists can also be queried by value more efficiently than single-linked lists
- Record the node P found last time
- Now I want to find T, compare the magnitude of P to T, and decide whether to go forward or backward from P
- A singly linked list can only traverse backwards from the beginning
9. Time for space and space for time
- Programs that are too slow can be sped up by consuming more storage/memory
- For programs that consume too much memory, you can reduce the memory footprint by increasing the execution time
10. Array and linked list comparison
- Insert delete array O(n), linked list O(1)
- Random access array O(1), linked list O(n)
- Arrays actually use a contiguous memory space, friendly to THE CPU cache mechanism,1 cache line can load multiple array elements at a time, better access performance;
- A linked list is a list of hashed memory blocks strung together by Pointers that are not contiguous, cache-unfriendly to CPU, and cannot be preread effectively.
- The disadvantage of an array is that the size of the array is fixed. After the array is declared, it will occupy a continuous segment of memory space. If the array is declared too large, the system does not have enough continuous memory space to allocate. If the value is too small, the system needs to expand the capacity, apply for more memory space, and perform data migration, resulting in poor performance.
- The linked list itself has no size limit and naturally supports dynamic expansion/because it is not a contiguous memory space
- If you are very strict with memory and use arrays, because every node in the linked list contains the next pointer, memory consumption doubles.
- Frequent insertion and deletion of linked lists will frequently apply for and release memory, which is prone to memory fragmentation and trigger frequent GC in Java.
11. Use linked lists to implement LRU cache elimination algorithm
- When there is a new data to be accessed, the search starts at the beginning node
- If the node is found, remove it from its original position and insert it into the head of the list
- If the node is not found, there are two cases
- When the list space is not full, insert directly into the head of the list
- When the linked list space is full, the end node is first deleted and then inserted into the head of the list
5. Array and linked list part code
1. Implement an int array
public class Array {
private int[] data;
private int n;
private int count;
public Array(int capacity) {
this.data = new int[capacity];
this.n = capacity;
this.count = 0;
}
public int find(int index) {
if(index >= 0 && index < count) {
return data[index];
}
return -1;
}
public boolean insert(int index,int value) {
if(count == n) {
System.out.println("Array is full");
return false;
}
if(index < 0 || index > count) {
System.out.println("Index value range out of bounds");
return false;
}
for(int i = count; i > index; i--) {
data[i] = data[i - 1];
}
data[index] = value;
++count;
return true;
}
public boolean delete(int index) {
if(index < 0 || index > count - 1) {
System.out.println("Index value range out of bounds");
return false;
}
for(int i = index; i < count - 1; i++) {
data[i] = data[i + 1];
}
--count;
return true;
}
public void printAll(a) {
for(int item : data) {
System.out.print(item + "");
}
System.out.println("");
}
public static void main(String[] args) {
Array array = new Array(5);
array.printAll();
array.insert(0.3);
array.insert(0.4);
array.insert(1.5);
array.insert(3.9);
array.insert(3.10); array.printAll(); }} Run result:0 0 0 0 0
4 5 3 10 9
Copy the code2. Implement an array that can be automatically expanded
public class GenericArray<T> {
private T[] data;
private int size;
public GenericArray(int capacity) {
data = (T[]) new Object[capacity];
size = 0;
}
public GenericArray(a) {
this(10);
}
public int getCapacity(a) {
return data.length;
}
public int count(a) {
return size;
}
public boolean isEmpty(a) {
return size == 0;
}
private void checkIndex(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Index value is invalid!"); }}private void checkIndexAdd(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Index value is invalid!"); }}public void set(int index, T e) {
checkIndex(index);
data[index] = e;
}
public T get(int index) {
checkIndex(index);
return data[index];
}
public boolean contains(T e) {
for (int i = 0; i < data.length; i++) {
if (data[i].equals(e)) {
return true; }}return false;
}
public int indexOf(T e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
returni; }}return -1;
}
private void resize(int capacity) {
T[] newData = (T[]) new Object[capacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
public void add(int index, T e) {
checkIndexAdd(index);
if (size == data.length) {
resize(size);
}
for (int i = size; i > index; i--) {
data[i] = data[i - 1];
}
data[index] = e;
++size;
}
public void addFirst(T e) {
add(0, e);
}
public void addLast(T e) {
add(size, e);
}
public T remove(int index) {
checkIndex(index);
T ret = data[index];
for (int i = size - 1; i > index; i--) {
data[i - 1] = data[i];
}
data[size - 1] = null;
--size;
if (size == data.length / 4 && data.length / 2! =0) {
resize(data.length / 2);
}
return ret;
}
public void removeFirst(a) {
remove(0);
}
public void removeLast(a) {
remove(size - 1);
}
public void removeElement(T e) {
int index = indexOf(e);
if(index ! = -1) { remove(index); }}}Copy the code3. Use a custom single linked list to check whether the string is a palindrome string
public class SinglyLinkedList {
class Node {
private int data;
private Node next;
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
public int getData(a) {
returndata; }}private Node head;
public Node createNode(int data, Node next) {
return new Node(data, next);
}
public void insertBefore(Node p, int data) {
insertBefore(p, createNode(data, null));
}
public void insertBefore(Node p, Node newNode) {
if (p == null) {
System.out.println("Target location node is empty!");
return;
}
if (newNode == null) {
System.out.println("New node is empty!");
return;
}
if (p == head) {
newNode.next = head;
head = newNode;
return;
}
Node curr = head;
while(curr.next ! =null&& curr.next ! = p) { curr = curr.next; }if(curr.next == p) { newNode.next = p; curr.next = newNode; }}public void insertAfter(Node p, int data) {
insertAfter(p, createNode(data, null));
}
public void insertAfter(Node p, Node newNode) {
if (p == null) {
System.out.println("Target location node is empty!");
return;
}
if (newNode == null) {
System.out.println("New node is empty!");
return;
}
newNode.next = p.next;
p.next = newNode;
}
public void insertToTail(int data) {
insertToTail(createNode(data, null));
}
public void insertToTail(Node newNode) {
if (head == null) {
head = newNode;
return;
}
Node curr = head;
while(curr.next ! =null) {
curr = curr.next;
}
curr.next = newNode;
}
public void insertToHead(int data) {
insertToHead(createNode(data, null));
}
public void insertToHead(Node newNode) {
if (head == null) {
head = newNode;
} else{ newNode.next = head; head = newNode; }}public void deleteNode(Node node) {
if (head == null) {
System.out.println("The header is null!");
return;
}
if (node == null) {
System.out.println("Target node is empty!");
return;
}
if (node == head) {
head = head.next;
return;
}
Node curr = head;
while(curr.next ! =null&& curr.next ! = node) { curr = curr.next; }if(curr.next == node) { curr.next = curr.next.next; }}private boolean compareTwoLinkedList(Node head1,Node head2) {
if(head1 == null || head2 == null) {
return false;
}
//
Node n1 = head1;
Node n2 = head2;
while(n1 ! =null) {
System.out.print(" | n1:" + n1.data);
n1 = n1.next;
}
while(n2 ! =null) {
System.out.print(" | n2:" + n2.data);
n2 = n2.next;
}
//
while(head1 ! =null&& head2 ! =null && head1.data == head2.data) {
head1 = head1.next;
head2 = head2.next;
}
if(head1 == null && head2 == null) {
return true;
}
return false;
}
private Node inverseLinkedList(Node tail) {
Node curr = head;
Node next = null;
while(curr.next ! = tail) { next = curr.next; curr.next = curr.next.next; next.next = head; head = next; } curr.next =null;
tail.next = head;
head = tail;
return head;
}
public boolean palindrome(a) {
if(head == null) {
System.out.println("The header is null!");
return false;
}
if(head.next == null) {
System.out.println("Only the header!");
return true;
}
if(head.next.next == null) {
if(head.data == head.next.data) {
return true;
}else {
return false;
}
}
Node s = head;
Node f = head;
while(f.next ! =null&& f.next.next ! =null){
s = s.next;
f = f.next.next;
}
if(f.next == null) {
// There are an odd number of nodes
Node right = s;
Node left = inverseLinkedList(s);
return compareTwoLinkedList(left,right);
}else {
There are an even number of nodes
Node right = s.next;
Node left = inverseLinkedList(s);
returncompareTwoLinkedList(left,right); }}private void printAll(a) {
Node curr = head;
while(curr ! =null) {
System.out.print("" + curr.data + ";"); curr = curr.next; }}public static void main(String[] args) {
/* * int[] d1 = new int[] {1,2,3,4,4,3,2,1}; Int [] d2 = new int[] {1,2,3,3,2,1}; * int[] d3 = new int[] {1,2,2,1}; Int [] d4 = new int[] {1,0,0,1}; * /
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};
SinglyLinkedList list1 = new SinglyLinkedList();
for(int item:d1) {
list1.insertToTail(item);
}
System.out.println("list1 is:");
list1.printAll();
System.out.println("list1 is palindrome:" + list1.palindrome());
SinglyLinkedList list2 = new SinglyLinkedList();
for(int item:d2) {
list2.insertToTail(item);
}
System.out.println("list2 is:");
list2.printAll();
System.out.println("list2 is palindrome:" + list2.palindrome());
SinglyLinkedList list3 = new SinglyLinkedList();
for(int item:d3) {
list3.insertToTail(item);
}
System.out.println("list3 is:");
list3.printAll();
System.out.println("list3 is palindrome:" + list3.palindrome());
SinglyLinkedList list4 = new SinglyLinkedList();
for(int item:d4) {
list4.insertToTail(item);
}
System.out.println("list4 is:");
list4.printAll();
System.out.println("list4 is palindrome:" + list4.palindrome());
}
}
list1 is:
1;2;3;4;3;2;1; | n1:4 | n1:3 | n1:2 | n1:1 | n2:4 | n2:3 | n2:2 | n2:1list1 is palindrome:true
list2 is:
1;2;3;2;1; | n1:3 | n1:2 | n1:1 | n2:3 | n2:2 | n2:1list2 is palindrome:true
list3 is:
1;2;2;1; | n1:2 | n1:1 | n2:2 | n2:1list3 is palindrome:true
list4 is:
1;0;1;0; | n1:0 | n1:1 | n2:1 | n2:0list4 is palindrome:false
Copy the code4. Use arrays to implement LRU algorithm
public class LRUBasedArray<T> {
private static int DEFAULT_CAPACITY = 1 << 3;
private int count;
private int capacity;
private T[] data;
private Map<T, Integer> holder;
public LRUBasedArray(a) {
this(DEFAULT_CAPACITY);
}
public LRUBasedArray(int capacity) {
this.count = 0;
this.capacity = capacity;
this.data = (T[]) new Object[capacity];
this.holder = new HashMap<T, Integer>(capacity);
}
public boolean contains(T t) {
return holder.containsKey(t);
}
public boolean isFull(a) {
return count == capacity;
}
public void access(T t) {
if(t == null) {
throw new IllegalArgumentException("Access to NULL is not allowed");
}
if (contains(t)) {
// indicates that t has been cached
Integer index = holder.get(t);
transferToRight(index);
addToHead(t);
} else {
T was not cached before
if (isFull()) {
/ / is full:
//
holder.remove(data[capacity - 1]);
transferToRight(capacity - 1);
addToHead(t);
} else {
/ / below:
//transferToRight(count); addToHead(t); count++; }}}public void transferToRight(int endIndex) {
for (int index = endIndex; index > 0; index--) {
data[index] = data[index - 1]; holder.put(data[index], index); }}public void addToHead(T t) {
data[0] = t;
holder.put(t, 0);
}
@Override
public String toString(a) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < count; i++) {
sb.append(data[i]);
sb.append("");
}
return sb.toString();
}
public static void main(String[] args) {
testDefaultConstructor();
testSpecifiedConstructor(4);
testWithException();
}
private static void testWithException(a) {
System.out.println("Test illegal access!");
LRUBasedArray<Integer> lru = new LRUBasedArray<Integer>();
lru.access(null);
}
public static void testDefaultConstructor(a) {
System.out.println("Test the default constructor");
LRUBasedArray<Integer> lru = new LRUBasedArray<Integer>();
lru.access(1);
lru.access(2);
lru.access(3);
lru.access(4);
lru.access(5);
System.out.println(lru);
lru.access(6);
lru.access(7);
lru.access(8);
lru.access(9);
System.out.println(lru);
}
public static void testSpecifiedConstructor(int capacity) {
System.out.println("Test constructor with specified construction parameters");
LRUBasedArray<Integer> lru = new LRUBasedArray<Integer>(capacity);
lru.access(1);
System.out.println(lru);
lru.access(2);
System.out.println(lru);
lru.access(3);
System.out.println(lru);
lru.access(4);
System.out.println(lru);
lru.access(2);
System.out.println(lru);
lru.access(4);
System.out.println(lru);
lru.access(7);
System.out.println(lru);
lru.access(1);
System.out.println(lru);
lru.access(2); System.out.println(lru); }} tests the default constructor5 4 3 2 1
9 8 7 6 5 4 3 2Tests the specified constructor parameter constructor1
2 1
3 2 1
4 3 2 1
2 4 3 1
4 2 3 1
7 4 2 3
1 7 4 2
2 1 7 4Test for illegal access! Exception in thread"main"Java. Lang. IllegalArgumentException: do not allow accessnull
at ***.LRUBasedArray.access(LRUBasedArray.java:34)
at ***.LRUBasedArray.testWithException(LRUBasedArray.java:88)
at ***.LRUBasedArray.main(LRUBasedArray.java:83)
Copy the code5. LRU algorithm using single linked list
public class LRUBaseLinkedList<T> {
class Node<T>{
public T data;
public Node next;
public Node(T data, Node next) {
super(a);this.data = data;
this.next = next; }}public Node createNode(T data) {
Node node = new Node(data,null);
return node;
}
private Node head;
private static int DEFAULT_CAPACITY = 8;
private int capacity = DEFAULT_CAPACITY;
private int count;
public LRUBaseLinkedList(int capacity) {
this.capacity = capacity;
}
public boolean isFull(a) {
return count == capacity;
}
public void access(T t) {
if(t == null) {
throw new IllegalArgumentException("Access elements cannot be empty!");
}
if(head == null) {
head = createNode(t);
count++;
return;
}
if(head.data.equals(t)) {
return;
}
Node curr = head;
while(curr.next ! =null && !curr.next.data.equals(t)) {
curr = curr.next;
}
if(curr.next ! =null && curr.next.data.equals(t)) {
// The element to be accessed already exists
Node next = curr.next;
if(next.next == null) {
curr.next = null;
next.next = head;
head = next;
}else{ curr.next = next.next; next.next = head; head = next; }}else {
// The element to be accessed does not exist
if(isFull()) {
// The element is full
//1: delete the last element of the list
Node c = head;
while(c ! =null&& c.next ! =null&& c.next.next ! =null) {
c = c.next;
}
c.next = null;
//2: add t to the head of the list
addHead(t);
}else {
// The element is not full
//1: add t directly to the list headeraddHead(t); count++; }}}public void addHead(T t) {
Node newNode = createNode(t);
newNode.next = head;
head = newNode;
}
private void printAll(a) {
System.out.println("Current data :\n");
Node curr = head;
while(curr ! =null) {
System.out.print("- >"+ curr.data); curr = curr.next; }}public static void main(String[] args) {
LRUBaseLinkedList<Integer> list = new LRUBaseLinkedList<>(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(); }} Current data is: ->10 -> 8 -> 6 -> 4 -> 2 -> 9
Copy the code6. Several single linked list problems
- Single-linked list inversion
- Single linked list ring detection
- The combination of two ordered singly linked lists
- Delete the KTH node from the penultimate of a single linked list
- Find the middle node of a singly linked list
public class LinkedListSample {
class Node {
public int data;
public Node next;
public Node(int data, Node next) {
super(a);this.data = data;
this.next = next; }}/** * single-linked list inversion **@param list
* @return* /
public Node reverse(Node list) {
if (list == null) {
throw new IllegalArgumentException("Parameters cannot be empty!");
}
if (list.next == null) {
return list;
}
Node curr = list;
Node pre = list;
Node next;
while(curr.next ! =null) {
next = curr.next;
curr.next = curr.next.next;
next.next = pre;
pre = next;
}
return pre;
}
/** * check if the linked list has a ring **@param list
* @return* /
public boolean checkCircle(Node list) {
if (list == null) {
return false;
}
Node slow = list;
Node fast = list;
while(fast.next ! =null&& fast.next.next ! =null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true; }}return false;
}
/** * merge two ordered single-linked lists **@param l1
* @param l2
* @return* /
public Node mergeTwoSortedList(Node l1, Node l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
// Introduce the sentinel node
Node soldier = new Node(0.null);
Node curr = soldier;
while(l1 ! =null&& l2 ! =null) {
if (l1.data <= l2.data) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
if(l1 ! =null) {
curr.next = l1;
} else {
curr.next = l2;
}
return soldier.next;
}
/** * delete the last KTH node ** from the single list@param list
* @param k
*/
public Node deleteLastK(Node list, int k) {
if (list == null) {
throw new IllegalArgumentException("Singly linked lists cannot be empty!");
}
if (k < 1) {
throw new IllegalArgumentException("K must be > = 1!");
}
Node fast = list;
int i = 0;
// The fast node moves forward k times first
while(fast.next ! =null && i < k) {
fast = fast.next;
i++;
}
if (i < k) {
throw new IllegalArgumentException("Single-linked lists are not long enough!");
}
Node slow = list;
while(slow.next ! =null&& fast.next ! =null) {
slow = slow.next;
fast = fast.next;
}
// The node to be deleted is solw.next
Node next = slow.next;
slow.next = next.next;
next.next = null;
return list;
}
/** * find the center node ** of a single linked list@return* /
public Node findMiddleNode(Node list) {
if (list == null) {
throw new IllegalArgumentException("Singly linked lists cannot be empty!");
}
Node slow = list;
Node fast = list;
while(fast.next ! =null&& fast.next.next ! =null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public void printAll(Node list) {
if (list == null) {
throw new IllegalArgumentException("Singly linked lists cannot be empty!");
}
Node curr = list;
System.out.println("Single linked list :");
while(curr ! =null) {
System.out.print("Current node :" + curr.data + "; "); curr = curr.next; }}public static void main(String[] args) {
LinkedListSample test = new LinkedListSample();
System.out.println("\n Test single linked list flip");
test.testReverse();
System.out.println("\n Tests whether a single linked list is looped");
test.testCircle();
System.out.println("\n test merge 2 sorted single linked lists");
test.testMergeTwoSortedList();
System.out.println("\n Test delete the last KTH element of a single list");
test.testDeleteLastK();
System.out.println("\n test to find the center node of a single linked list");
test.testFindMiddleNode();
}
private void testReverse(a) {
Node node1 = new Node(5.null);
Node node2 = new Node(4.null);
Node node3 = new Node(3.null);
Node node4 = new Node(2.null);
Node node5 = new Node(1.null);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
Node result = reverse(node1);
printAll(result);
}
private void testCircle(a) {
Node circle = new Node(100.null);
Node node1 = new Node(5.null);
Node node2 = new Node(4.null);
Node node3 = new Node(3.null);
Node node4 = new Node(2.null);
Node node5 = new Node(1.null);
node1.next = node2;
node2.next = node3;
node3.next = circle;
circle.next = node4;
node4.next = node5;
node5.next = circle;
System.out.println("Does the single linked list have rings :" + checkCircle(node1));
}
private void testMergeTwoSortedList(a) {
Node node1 = new Node(3.null);
Node node2 = new Node(7.null);
Node node3 = new Node(8.null);
Node node4 = new Node(20.null);
Node node5 = new Node(30.null);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
Node node21 = new Node(1.null);
Node node22 = new Node(2.null);
Node node23 = new Node(13.null);
Node node24 = new Node(40.null);
Node node25 = new Node(50.null);
node21.next = node22;
node22.next = node23;
node23.next = node24;
node24.next = node25;
Node result = mergeTwoSortedList(node1, node21);
printAll(result);
}
private void testDeleteLastK(a) {
Node node1 = new Node(3.null);
Node node2 = new Node(7.null);
Node node3 = new Node(8.null);
Node node4 = new Node(20.null);
Node node5 = new Node(30.null);
Node node6 = new Node(1.null);
Node node7 = new Node(2.null);
Node node8 = new Node(13.null);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node8;
Node result = deleteLastK(node1, 5);
printAll(result);
}
private void testFindMiddleNode(a) {
Node node1 = new Node(3.null);
Node node2 = new Node(7.null);
Node node3 = new Node(8.null);
Node node4 = new Node(20.null);
Node node5 = new Node(30.null);
Node node6 = new Node(1.null);
Node node7 = new Node(2.null);
Node node8 = new Node(13.null);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node8;
Node result = findMiddleNode(node1);
System.out.println("Intermediate node :"+ result.data); }} Test single linked list flip single linked list: current node:1; Current node:2; Current node:3; Current node:4; Current node:5; Test whether the single linked list is looped:trueTest merger2Single-linked list: current node:1; Current node:2; Current node:3; Current node:7; Current node:8; Current node:13; Current node:20; Current node:30; Current node:40; Current node:50; Delete the KTH element from a single linked list:3; Current node:7; Current node:8; Current node:30; Current node:1; Current node:2; Current node:13; Test to find the middle node of the center node of a single linked list:20
Copy the code