What is a linked list?
- Like an array, a linked list is a linear list. 2. 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. 3. 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
1. High efficiency of data insertion and deletion at O(1) level (just need to change the pointer pointer), low efficiency of random access at O(n) level (need to traverse from the chain head to the chain tail). 2. 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
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
Circulation 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
Two-way 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.
Bidirectional cyclic list
Array or linked list?
Time complexity of insert, delete, and random access
To compare
\
Array: Insert, delete time complexity is O(n), random access time complexity 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
- If the memory space is large, for example, 100 MB, but there is no continuous space of 100 MB, the memory application fails even though the available memory space exceeds 100 MB.
- The storage capacity is fixed. If the storage space is insufficient, you need to expand the capacity. Once the capacity is expanded, data replication needs to be performed, which takes time.
List disadvantages
- Memory space is more expensive because extra space is needed to store pointer information.
- Frequent insertions and deletions of linked lists can result in frequent memory requisition and deallocation, which is prone to memory fragmentation and, in the case of the Java language, can result in frequent GC (automated 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.
How to implement LRU cache elimination algorithm?
What is caching?
Cache is a technology to improve the performance of data reading. It is not widely used in hardware design and software development, such as CPU cache, database cache, browser cache and so on.
Why cache flush? That’s the nature of caching
The size of the cache is limited. When the cache is full, what data should be purged and what data should be retained? You need to use a cache elimination strategy.
What is a cache flush policy?
This refers to the priority of cleaning up data when the cache is full.
What are the cache flushing strategies?
The three most common policies include FIFO (First In, First Out), Least Frenquently Used (Least Recently Used), and Least Recently Used LRU (Least Recently Used).
Linked lists implement LRU cache elimination strategy
When the accessed data is not stored in the cached linked list, the data is directly inserted into the linked list header, and the time complexity is O(1). When the accessed data exists in the stored linked list, the node corresponding to the data is inserted into the head of the linked list with the time complexity O(n). If the cache is full, the cleanup starts with the data at the end of the list in O(1) time.
Array implements the LRU cache elimination strategy
Use an array to store data, mark an access timestamp for each data item, each time to insert a new data item, first increase the time stamp of the data item in the array, and set the time stamp of the new data item to 0 and insert into the array. Each time an item in the array is accessed, the timestamp of the accessed item is set to 0. When the array space is full, the data item with the largest timestamp is eliminated.
LRU cache elimination strategy using linked list and HashMap
When a new data item needs to be inserted, if the new data item exists in the linked list (generally called hit), the node is moved to the head of the linked list; if it does not exist, a new node is created and put in the head of the linked list. If the cache is full, the last node of the linked list can be deleted. When accessing data, if the item exists in the list, move the node to the head of the list, otherwise -1 is returned. This makes the node at the end of the list the most recent and longest unaccessed item.
Design idea
When the memory space is sufficient, if we pursue the execution speed of the code more, we can choose algorithms and data structures with relatively high space complexity and low time complexity. Caching is an example of space for time. If the memory is relatively short, such as the code running on the mobile phone or microcontroller, at this time, it is necessary to use time for space thinking.
The question of how to determine if a string is a palindrome string.
1 Locate the middle node using the fast and slow Pointers. 2 Compare the middle node with the middle node to determine whether the time complexity is On and space complexity is O1 for the reverse restoration of the second half of palindrome 4
How to easily write the correct list code?
Understand the meaning of Pointers or references
1. Meaning: To assign a variable (object) to a pointer (reference) is to assign the address of the variable (object) to a pointer (reference). 2. Example: p — >next = q; The subsequent pointer to the p node stores the memory address of the Q node. P – > next = p – > next – > next; The subsequent pointer to the p node stores the memory address of the next node of the P node.
Beware of pointer loss and memory leaks (single linked list)
1. Insert the node
\
insert
\
Insert node X between node A and node B, b is the next node of a, p points to node A, p — >next = x; X – > next = p – > next; Obviously this causes the successor pointer to the X node to point to itself. X — >next = p — >next; P – > next = x; 2. Delete a node. Delete node B between node A and node B. B is the next node of node A and P points to node A: p – >next = P – >next – >next.
Use sentry to simplify the implementation
What is a Sentinel?
Sentinel nodes in the linked list solve boundary problems and do not participate in business logic. If we introduce the Sentinel node, the head pointer will point to the sentinel node whether the list is empty or not. A list with sentinel nodes is called a leader list, whereas a list without sentinel nodes is called an unleader list.
A situation in which sentry is not introduced
If a node is inserted after the p node, just 2 lines of code will do the job: new_node — >next = p — >next; P – > next = new_node; If (head == null){head = new_node; } P — >next = p — >next — >next; If (head — >next == null){head = null; if(head — >next == null); } As can be seen from the above situation, the insertion and deletion of the first node and the deletion of the last node need special treatment. The code becomes cumbersome, so the sentinel node is introduced to solve this problem.
Introduce the sentry situation
The Sentinel node does not store data, and the head pointer points to it whether the list is empty or not, as the head of the list always exists. In this way, inserting the first node and inserting the other nodes, deleting the last node and deleting the other nodes can be unified into the same code implementation logic.
4. What other application scenarios do Sentinels have?
The sentry’s main function is to simplify the processing of boundary conditions. For bidirectional linked list L (l.read is the header, the header has a value, l.ead. Prev is NIL), L.nil is the sentinel variable of the list, l.nil. Next points to the header; L.nil.prev pointing to the end of the table;
- Insert list (head) without sentry:
LIST_INSERT(L, x) x.next = L.head if L.head ! = NIL L.head.prev = x L.head = x x.prev = NIL - The conditional statement can be omitted by using sentry:
LIST_INSERT'(L, x) x.next = L.nil.next L.nil.next.prev = x L.nil.next = x x.prev = L.nil
Pay special attention to boundary condition processing
There are 4 boundary conditions that are often used to check whether linked lists are correct:
- Does the code work if the list is empty?
- Does the code work if the linked list contains only one node?
- Does the code work if the linked list contains only two nodes?
- Does the code logic work when dealing with head and tail nodes?
Draw pictures with examples to help you think
Hand painted
Core idea: Free up your brain and leave more space for logical thinking, so you’ll feel much clearer.
Write and practice, there is no shortcut
There are five common linked list operations:
- Single-linked list inversion
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution {public: ListNode* reverseList(ListNode* head) { auto cur = head; while(cur) { auto temp = cur->next; cur->next = prev; prev = cur, cur = temp; } return prev; */ / iteration 2 /*if (! head || ! head->next) return head; auto a = head, b = a->next; while(b) { auto c = b->next; b->next = a; a = b, b = c; } head->next = nullptr; return a; */ / the recursive version of if(! head || ! head->next) return head; auto tail = reverseList(head->next); head->next->next = head; head->next = nullptr; return tail; }};Copy the code- Linked list central detection
LinkADT<T> {private static class SingleNode<T> {public SingleNode<T> next; public T data; public SingleNode(T data) { this.data = data; } public T getNextNodeData() { return next ! = null ? next.data : null; }} public static Boolean hasLoopV1(SingleNode headNode) {if(headNode) == null) { return false; } SingleNode p = headNode; SingleNode q = headNode.next ; While (q! = null && q.next ! = null) { p = p.next; // Iterate over a node q = q.ext.next; If (q == null) {return false; } else if (p == q) {return true; } } return false; }}Copy the code- Merge two ordered linked lists
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution {public: merge(ListNode* l1, ListNode* l2) {// Merge (ListNode* l1, ListNode* l2) {// Merge (ListNode* l1, ListNode* l2) { Time complexity o (n) /*if(! l1) return l2; if(! l2) return l2; if(l1->val > l2->val) { l2->next = merge(l2->next, l1); return l2; } else { l1->next = merge(l1->next, l2); return l1; }*/ / join ListNode* dummy = new ListNode(-1); ListNode* tail = dummy; while (l1 && l2) { if (l1->val >= l2->val) tail->next = l2, tail = l2, l2 = l2->next; else tail->next = l1, tail = l1, l1 = l1->next; } if(l1) tail->next = l1; if(l2) tail->next = l2; return dummy->next; }};Copy the code- Delete the NTH node from the penultimate list
public ListNode removeNthFromEnd(ListNode head, int n) { if(n <= 0){ return head; } if(null == head){ return head; } int i = 0; ListNode tail = head; while(tail ! = null && i < n){ tail = tail.next; i++; } // Number of nodes less than n if(I < n){return head; If (tail == null){head = head.next; return head; } // The number of nodes is greater than n ListNode newHead = head; while(tail.next ! = null){ head = head.next; tail = tail.next; } head.next = head.next.next; return newHead; }Copy the code- Find the middle node of the list
class Solution { public ListNode middleNode(ListNode head) { ListNode first = head; ListNode second = head; while(first ! = null && first.next ! = null){ first = first.next.next; second = second.next; } return second; }}Copy the code