1, the preface
A linked list is a non-sequential storage structure on a physical storage unit. The logical order of data elements is realized by linking the order of Pointers in the linked list. A linked list consists of a series of nodes (each element of the list is called a node) that can be dynamically generated at run time. Because linked lists are not continuous linear data structures, programs using linked lists have a major advantage over arrays when running on machines with relatively little memory.
2, definitions,
Linked lists are often defined as such, where value is used to represent the value of the list node, the next pointer is used to indicate the successor node (optionally named, as long as it can store the node value and mark the next node), and the end of the list if there is no (NULL).
interface Node<T> {
/ / the node values
value: T;
// Reference to the next node
next: Node<T> | null;
}
Copy the code3. Operation of linked lists
For linked list operations, I personally feel that the two most important operations are initialization and traversal, and judging from LeetCode’s questions, more than half of them are like this. Some students like to put an empty node at the head of a linked list. This is a personal programming habit, but I generally don’t like it (not to save memory, ha ha ha), so choose a habit that works for you. None of the code implementations in this article contain empty headers.
3.1. Initialization
Let’s talk about initialization, which is to construct a linked list from a bunch of data. There are generally two operations for initializing linked lists: head interpolation and tail interpolation.
Header method: use a variable to point to the head node of the existing linked list. Each time the new node is inserted in front of the head node, and then let the variable point to the newly inserted node. Therefore, the order of the linked list data constructed by the header method is opposite to the order of the input.
The process of inserting a node by head insertion:
/** * Initializes the linked list with the header method *@param {Array<number>} Arr is used to initialize linked list data */
function initialize(arr) {
// If the first step in the figure
let head = null;
// In this example, it is used only to illustrate the problem
let tail = null;
arr.forEach((val) = > {
const node = createNode(val);
// If the list is empty, make the header pointer point to the first node
if (head == null) {
// As shown in step 2
head = node;
// In this example, it is used only to illustrate the problem
tail = node;
} else {
// Make the new node point to the head node, as shown in step 3
node.next = head;
// Let the head pointer point to the latest node, as shown in step 4head = node; }});return head;
}
Copy the codeTail insertion method: use a variable to point to the end of the existing linked list, each time the new node is inserted after the tail node, and then let the variable point to the newly inserted tail node, so the order of the linked list data constructed by tail insertion method is the same as the order of input.
Tail insert process of node:
/** * Initializes the linked list with tail insertion *@param {Array<number>} Arr is used to initialize linked list data */
function initialize(arr) {
// As shown in the first step
let head = null;
let tail = null;
arr.forEach((val) = > {
const node = createNode(val);
if (head == null) {
// For an empty list, set the head and tail Pointers to the first node, as shown in the first step
head = node;
tail = node;
} else {
// Set the following pointer to the new node, as shown in step 3
tail.next = node;
// Make the last node pointer to the last node, as shown in step 4tail = node; }});return head;
}
Copy the codeMy personal programming habit is to use the second one, but even with the header method, you can use one more variable to remember the end of the list, which has the advantage that if at some point you need to insert at the end, you can just use the end pointer instead of going through it.
3.2 Traversal of linked lists
Traversal of linked lists is almost a standard paradigm, which is the knowledge that must be mastered for linked lists. For unidirectional linked lists, simply give the head pointer to complete the traversal.
When traversing the linked list, we sometimes declare a precursor node, so that in the traversal process, we can find the current node, and can find the precursor node of the current node, very useful in some times, this is also a programming skill must master.
It is important not to change the head pointer while iterating through the list, because once you change the head pointer, it will not be found again. If you need to use the head pointer, the code will have to be redesigned.
List traversal process:
The complexity of list traversal is O(N);
The algorithm is as follows:
/** * traverses the list *@param {Node<number>} Head pointer */
function traverse(head) {
let node = head;
// The pre is useless in this example, just to show that this is a programming trick
let pre = null;
// If the current node points to empty (for empty lists, start directly to empty)
while (node) {
console.log(node);
// Make pre lag so that it always points to the previous node (if node is null,pre points to the last node, if node is the first node or if the linked list is empty,pre points to null)pre = node; node = node.next; }}Copy the code3.3. Insert a node in the specified position
You must be careful with the operation of the linked list, otherwise you may lose successor nodes or make the node pointing of the list behave in an unexpected way.
Let’s demonstrate the process of inserting a node in the middle of a table:
newNode.next = node; pre.next = newNode;These two lines of code must not be interchanged.
The average time complexity of linked list inserts is: O(N)
The algorithm is as follows:
/** * Insert the node at the specified position K in the list. If K is less than 1, insert the node at the head. If K is greater than the length of the list, insert the node directly at the end@param {Node<number>} Head The head of the chain@param {number} Val Specifies the value *@param {number} Where K is inserted,K is the number of nodes, not the index */
function insert(head, val, K) {
const newNode = createNode(val);
// If it needs to be inserted in the head
if (K < 1) {
newNode.next = head;
head = newNode;
return head;
}
let node = head;
// declare a null pointer because it lags behind node a table node, mainly used to record the last node
let pre = null;
// declare a counter to mark the number of nodes that have been traversed
let counter = 0;
let inserted = false;
while (node) {
counter++;
// If the insertion position is found, there is no need to continue the loop after the insertion is complete
if (counter === K) {
// It must be remembered with a temporary variable first, otherwise the successor nodes will be lost
let nextNode = node.next;
// Insert a new node
node.next = newNode;
newNode.next = nextNode;
// The tag is inserted
inserted = true;
break;
}
// Remember the current node and iterate backwards
pre = node;
node = node.next;
}
// If you have already inserted it, you don't need to do anything
if (inserted) {
return head;
}
If K is greater than or equal to the length of the list, insert it directly into the end of the list
if (counter < K && pre) {
// The node is null and the pre pointer points to the last node in the list
pre.next = newNode;
} else {
// If the linked list is empty and the previous loop has not been executed once, then simply point head to the new node
head = newNode;
}
return head;
}
Copy the code3.4, find
Search is mainly divided into value search or location search. The idea of searching is similar to traversal, so the algorithm flow will not be described here.
The average algorithmic complexity of lookups is O(N).
The algorithm is as follows:
/** * Find the linked list node by index *@param {Node<number>} Head The list header *@param {number} Idx target index */
function findIndex(head, idx) {
let node = head;
let counter = 0;
The target index is not found or the target index is found
while (node && counter < idx) {
counter++;
node = node.next;
}
return counter === idx ? node : null;
}
/** * Find node * based on node value@param {Node<number>} Head The list header *@param {number} Val Target node value */
function find(head, val) {
let node = head;
// Terminate the loop by finding the node value or iterating to the end of the list
while(node && node.val ! == val) { node = node.next; }return node;
}
Copy the code3.5, delete,
List of deleted is relatively simple, specific nodes can be directly away, that have advantages relative to the array, because after removing elements in the array, need to move forward a all elements and then to reduce the size, when the data of each unit is a complex structure, the time overhead but can’t be ignored.
Procedure for deleting linked list nodes:
Note also that when a list is deleted, the order of these statements cannot be swapped. If the order is swapped, it will not meet the expectation.
If we do not consider the time complexity of search, the time complexity of linked list deletion is O(1).
The algorithm is as follows:
/** * removes the node * with the value val from the list@param {Node<number>} Head The head of the linked list *@param {number} Val Specifies the value */ to be deleted
function remove(head, val) {
if(! head) {console.warn("can not remove element from empty linked list");
return;
}
let node = head;
let pre = null;
while (node) {
// The destination node is found and the loop needs to end
if(node.value ! = val) {break;
}
pre = node;
node = node.next;
}
// If pre exists, the user is not deleting the header
if (pre) {
// As shown in step 2
pre.next = node.next;
// Figure 3
node.next = null;
node = null;
} else {
// When deleting a header, use a temporary variable to write down the second node (even if it doesn't exist)
let nextHead = head.next;
// Unreference the second node from the header
head.next = null;
// make the header pointer point to the next node
head = nextHead;
}
return head;
}
Copy the code4, extension,
Bidirectional and circular lists are not covered in this article, if you can master the above knowledge, bidirectional and circular lists are not a problem, interested readers can consult the information.
This section selects some high-frequency interview questions to analyze the ideas and solutions.
4.1. Reverse linked lists
The 206th.
So this is a question of understanding the head interpolation and the tail interpolation, and it can be done in order N time.
In the process of traversing the linked list, we use the head interpolation method to build a new list. When the original list traversing is completed, the new list is also built, that is, the list inversion is completed.
The algorithm is as follows:
/** * reverses the specified list *@param {Node<number>} Head Head node to be reversed */
function reverseList(head) {
let reverseList = null;
let node = head;
while (node) {
let nextNode = node.next;
node.next = null;
if (reverseList === null) {
reverseList = node;
} else {
node.next = reverseList;
reverseList = node;
}
node = nextNode;
}
return reverseList;
}
Copy the code4.2 Insert sort the linked list
The 147th question
Sorting an array is a little bit more complicated than sorting an array because we can access the elements directly by subscript. In this paper, insertion sort is a simple description of linked list sort.
Insertion sort of way of thinking is similar to play poker with us in the process of touch card, when we touch up the first card, can be directly inserted into, that is to say, the first card thought and orderly, every time we touch up behind a card, we all need to start from the last card, if to insert card is smaller than the currently selected card, It means that the card can’t be inserted in this position, so we have to put the card we currently choose behind the wrong one, and then continue to compare, and repeat the process until we find the right position. The algorithm flow can be referenced here
But for linked lists, the process is reversed.
So first of all, we’re going to iterate over the list which is absolutely necessary, so let’s take out our list iterate paradigm code.
Build a new list while iterating through the old one.
Because the insertion of the linked list node is not as troublesome as the array, the array needs to be misplaced, and the linked list can be directly inserted, but you need to find the appropriate insertion position in the new table, which must be found from the head of the new table.
The time of this algorithm is the same as the average time of array insertion sort, which is O(N ^ 2).
This algorithm process is not given in this paper. If you have any questions, you can directly check the official explanation of LeetCode or contact the author.
The algorithm is as follows:
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/** * direct insert sort on the list *@param {ListNode} head
* @return {ListNode}* /
function insertionSortList(head) {
if(! head) {return head;
}
// A new table to build
let newHead = null;
let node = head;
while (node) {
let nextNode = node.next;
node.next = null;
if (newHead === null) {
newHead = node;
} else {
let sortNode = newHead;
let preSortNode = null;
// Find the appropriate insert location in the new table
while (sortNode && sortNode.val <= node.val) {
preSortNode = sortNode;
sortNode = sortNode.next;
}
// If inserted on the first node
if (preSortNode === null) {
node.next = newHead;
newHead = node;
} else {
let preNext = preSortNode.next;
preSortNode.next = node;
node.next = preNext;
}
}
node = nextNode;
}
// Return the new table to complete the sorting
return newHead;
}
Copy the code4.3. Flip linked lists in a group of K
Question 25
It is said that this question is the original interview question of Microsoft in a certain year. As you can see, this is a difficult problem, don’t be scared, when you really understand the list, the difficulty is just like that, ha ha ha.
This problem also examines list insertion operations, but the difficulty lies in the introduction of flip conditions. Let’s start by thinking about some boundary conditions. First of all, if the list passed in is empty or flips as a group of K=1, nothing needs to be done. If there are still some nodes left after the n component is flipped, output them as required.
When the counter is 0, we need to initialize a variable (groupStartNode) so that we can remember the first node of the list that started the inversion. If the counter is equal to K at any point in time, the linked list from groupStartNode to the current node can be reversed. We already know how to reverse a linked list. To simplify things, first disconnect the next node of the current node. Remember it with a variable called nextNode before disconnecting, and then fetch it back from it after the inversion, and then initialize groupCounter and groupStartNode to complete the inversion. If the list has been traversed, groupCounter is still less than K.
The algorithm flow is as follows:
The algorithm is as follows:
/** * invert the list as a group of K *@param {Node<number>} Head Indicates the head of the list to be flipped *@param {number} Size of each group of k flips *@returns {Node<number>} Flipped list */
var reverseKGroup = function(head, k) {
// The list does not need to be flipped if it is empty or if the inversion node is 1
if(! head || k ==1) {
return head;
}
let newHead = null;
let pre = null;
let node = head;
let groupHead = head;
let groupCounter = 0;
// Start traversing the list
while(node ! =null) {
groupCounter++;
// It indicates that the number of bytes in a group is K and needs to be reversed.
if (groupCounter === k) {
let nextNode = node.next;
node.next = null;
// Convert to exactly the same process as in question 1
const reverse = reverseList(groupHead);
// Whether the first group is flipped
if(! newHead) { newHead = reverse; }else {
pre.next = reverse;
}
// After flipping, pre is the last node in the new list
pre = groupHead;
// To simplify things, we had a disconnect operation before, now we can connect it back.
groupHead.next = nextNode;
// The next node is the node whose next turn starts
groupHead = nextNode;
// Since the rollover has been completed, the counter needs to be reset to zero
groupCounter = 0;
node = nextNode;
} else{ node = node.next; }}return newHead || head;
};
/** * reverse linked list *@param {Node<number>} Head The head of the linked list *@returns * /
function reverseList(head) {
let reverseHead = null;
while(head ! =null) {
let next = head.next;
head.next = reverseHead;
reverseHead = head;
head = next;
}
return reverseHead;
}
Copy the codeconclusion
Linked lists also have the advantage over arrays that their length can grow indefinitely if there is enough memory. For other languages (C#, Java, etc.), the expansion cost of array is relatively large. First, we need to apply for a longer continuous space from the system (in some cases, it may not be able to apply for). Then copy the old data into the new array, and then release the original array, which is not negligible if each item is large.
The average algorithm complexity of linked lists is compared with that of arrays as follows:
| operation | An array of | The list |
|---|---|---|
| Random access | O(1) | O(N) |
| insert | O(N) | O(N) |
| To find the | O(N) | O(N) |
| Delete (do not consider pre-lookup) | O(N) | O(1) |
Although most of the article is talking about the advantages of linked list over array, but if you need to sort its data, some sorting algorithms can not be directly used, so in the actual development, we need to decide whether to use linked list or data storage data according to the requirements.
Due to the limited level of the author, it is inevitable that there will be mistakes in the writing process. If there are any mistakes, please correct them. Please contact the author at [email protected], your opinions will help me make better progress. This article is the author’s original, if reproduced please contact the author.