preface
If data structures are the foundation of algorithms, then arrays and linked lists are the foundation of data structures. Because the stack, stack, pair, graph and other more complex array node basically can be represented by arrays and lists, so it is important to understand the basic operation of arrays and lists.
List of knowledge quite a lot, so divided into two parts, this is mainly to explain the list flip problem solving skills, the next part is mainly about the list pointer knowledge, a lot of dry goods, it is recommended to collect again. See the guarantee harvest full!
Today, we will take a look at the basic operation of the list and its common ideas in the interview. This article will explain the core knowledge of the list from the following points
- What is a linked list, what are the pros and cons of a linked list
- The expression and basic operation of the linked list
- The common way to solve the problem of the list in the interview – flip
What is a linked list
I believe you have begun to wait to use the list to solve the problem, but before we start to review the definition of the list, as well as its advantages and disadvantages, the knife is not mistakenly cut the work!
The definition of a linked list
A linked list is a discontinuous and non-sequential storage structure on a physical storage unit. It is connected by a node through Pointers. Each node includes data and Pointers.
The list is discontiguous, and the list is dissequential, and the array is contiguous, and the array is sequential, so let’s look at the memory representation of integer arrays 1,2,3,4
So what does a linked list look like in memory
You can see the location of the distribution of each node in the continuous, between nodes and by the hands together, so if we want to find such as a value of 3 nodes, only through 1 from the beginning to the end node traversal search, if the element is less good, if too many elements, such as more than ten thousand), for every element, to find, from the very beginning The time complexity is O(n), which is not so much as O(1) for an array.
In addition to the search performance of the list is not as good as the array, there is an advantage that the performance of the array is higher than the list, here introduce the principle of program locality, what is called the principle of program locality.
We know that the CPU runs very fast. If the CPU has to fetch data from memory for every operation, it is undoubtedly time-consuming. Therefore, there are many levels of caches integrated between the CPU and memory. Therefore, if the data in memory can be loaded into L1,L2, and L3 cache in the following figure, then the next CPU fetch can be directly from these caches, which can speed up the CPU execution, then when the data in memory can be loaded into L1,L2, and L3 cache in advance? The answer is that when an element is used, elements near that element’s address are loaded into the cache ahead of time
For example, when the program uses the first element in the array (1), the CPU will add 2, 3, and 4 to the L1,L2, and L3 cache in advance, because the CPU thinks that since 1 is used, the next element 2, 3, and 4 are likely to be used. So when the CPU executes 2,3,4 again, it just pulls it from the L1,L2,L3 cache, and it improves performance a lot
If you view a CPU hour as a second, it takes 3 seconds to read from L1, 11 seconds to read from L2, 25 seconds to read from L3, and 1 minute and 40 seconds to read from memory, so the principle of program locality can greatly improve CPU performance
As for the linked list, since each node of the list is randomly distributed in memory and connected only through Pointers, the addresses of these nodes are not adjacent, so it is impossible to use the principle of program locality to load the nodes into L1,L2 and L3 cache in advance to improve the performance of the program.
Voice-over: The principle of program locality is a very important principle in the computer. It will not be expanded here. It is recommended that you consult relevant information to understand it in detail
As mentioned above, the non-sequential and non-sequential nature of linked lists does put them at a performance disadvantage compared to arrays, so when should you use lists? Consider the following
- Large memory space allocation
Due to the continuity of the array space, if you want to allocate 500 MB of space for an array, the 500 MB of space must be contiguous and unused. Therefore, the array space allocation requirements are stricter. If there is too much memory fragmentation, allocating large contiguous space may cause failure. The linked list is more appropriate in this case because it is discontinuous.
- Elements are frequently deleted and inserted
If it involves frequent delete and insert elements, use the list will be much more efficiently, for array, if you want to insert an element between the elements, need to move the rest of the elements one by one in the future (see chart), thought that the new elements make room (in the same way, if is to remove the need to be deleted element to the element after the move forward one by one), the efficiency is low.
While the insertion and deletion of the linked list is relatively simple, the pointer position can be changed, other elements do not need to do any movement operation (as shown in the figure: take the insertion as an example)
To sum up: if the data is mainly to look up, rarely involves adding and deleting, select array, if the data involves frequent insertion and deletion, or the element allocation space is too large, tend to choose list.
Said so many theories, I believe that readers should have a deeper understanding of the difference between array and list, especially the principle of program locality, is not open a lot of horizons ^_^, if the interview asked about the difference between array and list can answer the principle of program locality, will be a very big highlight!
Let’s take a look at the representation of the list and the techniques for solving it
I have put all the relevant code in the article on Github. If you need to, you can visit my Github address to download and run. All the code in the article has been implemented and run in Java
The representation of a linked list
Because of the characteristics of the list (query or delete elements to start from the node), so we only need to define the head node in the list, in addition to frequent use of the length of the list, you can define an additional variable to represent.
It should be noted that the definition of the head node is exquisite. Generally speaking, there are two definitions of the head node. One is to directly take an element node as the head node, as follows
One has a virtual node as the head node, or sentinel, as follows
So what’s the benefit of defining this sentinel, assuming we don’t define this sentinel, what’s the basic operation of adding elements to a list
/** * Nodes in a linked list, where data is the value of the node and next is a reference to the next node */
class Node {
int data;// The node array field, value
Node next = null;// A reference to a node, pointing to the next node
public Node(int data) {
this.data = data; }}/** * list */
public class LinkedList {
int length = 0; // List length is optional
Node head = null; / / head node
public void addNode(int val) {
if (head == null) {
head = new Node(val);
} else {
Node tmp = head;
while(tmp.next ! =null) {
tmp = tmp.next;
}
tmp.next = newNode(val); }}}Copy the codeSee the problem? Pay attention to the code below
There are two problems:
- Each insertion of an element requires a null comparison with the node. If a linked list has many elements to be inserted, it requires many times of null comparison, which is not so efficient
- The insertion logic of the head node is inconsistent with that of the other nodes (one needs to be inserted after a null judgment, and the other needs to be inserted directly without a null judgment), which is not so logical in terms of program logic (because the nodes are at the same level as the nodes, so the add logic should be the same).
Both of these problems can be solved if sentinel nodes are defined. Let’s look at the linked list definition using sentinel nodes
public class LinkedList {
int length = 0; // List length is optional
Node head = new Node(0); // Sentinel node
public void addNode(int val) {
Node tmp = head;
while(tmp.next ! =null) {
tmp = tmp.next;
}
tmp.next = newNode(val); }}Copy the codeAs you can see, the linked list with sentinel nodes defined is much clearer in logic, not having to null each node every time an element is inserted, and unifying the add logic for each node.
So the list that we’re going to use for the rest of the problem set is going to be in the form that defines the sentinel.
Have done so many early preparation work, finally want to start our dinner: the common routine of linked list problem solving – flip!
Linked list common problem solving routine
A friendly
Given the array 1, 2, 3, 4, construct the following list head–>4—->3—->2—->1
See clearly, is the reverse order structure list! We all know how to construct the list in reverse order (insert 1,2 as an example). The addNode method defined in the preceding code is called continuously for each element (insert 1,2 as example).
Head insertion method is relatively simple, directly on the code, directly follow the steps of the GIF above to complete the logic, as follows
public class LinkedList {
int length = 0; // List length is optional
Node head = new Node(0); // Sentinel node
/ / head interpolation
public void headInsert(int val) {
// 1. Construct a new node
Node newNode = new Node(val);
// 2. The new node points to the node after the head node
newNode.next = head.next;
// 3. The header node points to the new node
head.next = newNode;
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
int[] arr = {1.2.3.4};
// Create a linked list
for (int i = 0; i < arr.length; i++) {
linkedList.headInsert(arr[i]);
}
// To print a linked list, print 4-->3-->2-->1linkedList.printList(); }}Copy the codeA profound
Now let’s make it harder and look at the old Google interview question: Given a head pointer and a node pointer to a unidirectional linked list, define a function to delete the node in O(1).
As we know, given a node to delete its successor, it’s easy to simply point the node’s pointer to the successor
As shown in the diagram: given node 2, delete its successor node 3 and point the next pointer of node 2 to 3’s successor node 4.
But given node 2, how do you delete node 2 itself? Notice that they don’t say that you can’t change the value of the node, so there’s a very clever way to do this: replace the node! We first find node 3 through node 2, and then assign the value of node 3 to node 2, and then the value of node 2 becomes 3, and then the problem becomes the simple requirement in the figure above, which is to remove node 3 according to node 2. Look at the picture
However, it is important to note that this technique only works if the node to be deleted is an intermediate node. If the node to be deleted is a tail node, you still need to find the successor node of the tail node and delete the tail node
/** * delete node *@param deletedNode
*/
public void removeSelectedNode(Node deletedNode) {
// If this node is the tail node, we still need to go through the successors of the tail node, and then delete the tail node
if (deletedNode.next == null) {
Node tmp = head;
while(tmp.next ! = deletedNode) { tmp = tmp.next; }// Find the successor of the end node and delete the end node
tmp.next = null;
} else {
Node nextNode = deletedNode.next;
// Assign the value of the deleted node's successor to the deleted node
deletedNode.data = nextNode.data;
// Delete the nextNode node
deletedNode.next = nextNode.next;
nextNode.next = null; }}Copy the codeStarting to advanced: List flipping
Next we will focus on the flip of the list, the flip of the list can be derived from a lot of deformation, is a very popular interview test point, basically test the list must be flipped! So mastering the flip of the list is a required course!
What is a list flip: given a list head–>4– >3–>2–>1, flip it to head–>1–>2–>3–>4. Since flipping lists is so common and so important, let’s explain in detail how to do it both recursively and non-recursively
- Recursive flip
About recursive wrote three articles before, if not read before, it is strongly recommended that click here to see, summarizes the common problem solving recursive routines, gives the recursive common four steps of problem solving, if watching for the following recursion formula in solving problems will be more profound, there is no need to do, we directly set of recursive way:
First of all, we need to see if the flipped list is recursive: the problem can be decomposed into sub-problems with the same solution idea, sub-sub-problems… Until the final subproblem can no longer be decomposed.
To flip the head – > 4 – > 3 – > 2 – > 1 list, do not consider the head node, analysis of 4 — – > 3 – > 2 – > 1, observe carefully we found that as long as the first 3 – – > 2 – > 1 flip into 3 2 < < — – 1, Then point 3 to 4 (as shown below)
Figure: There are three main steps in flipping a linked list
Just follow the steps above to define the function of the flip function. In this way, since the subproblem has the same idea of solving as the original problem, the subproblem after splitting will continue to call the flip function.
Notice from step 1 above that the size of the problem has been reduced (as shown below), from flipping the whole list to just flipping part of it! The problem and the subproblem are all from a certain node to flip, with the same solution, and when narrowed down to flip only a node, obviously is the termination condition, in line with the recursion condition! Then flip 3–>2–>1, 2–>1 to keep calling the defined recursive function!
Now that the condition of recursion is met, we can use the recursive four steps to solve the problem. (Note that after the head is flipped, the successor node changes and needs to be reset!) Don’t forget this step)
Based on the analysis above, it is clear that the function of this recursive function is to reverse the list at the beginning of a node and then return the new head node
/** * reverse the list from node */
public Node invertLinkedList(Node node) {}Copy the codeThe steps of flipping a linked list have been drawn in detail above. A brief summary of the steps is as follows
- According to node node (a value of 4), first turn after the node of the node invert (node – > next), flip after 4 – > 3 – > 2 – > 1 into 4 — – > 3 < — — — < 2-1
- The next node (3) of node points to node, and the next node (3) of node is null (to avoid forming a ring), so it becomes 4<– 3<– 2<– 1
- Return the new head node, because the new head node changed from 4 to 1, so you need to reset the head
InvertLinkedList (invertLinkedList) invertLinkedList (invertLinkedList)
/** * recursively reverse the list from node */
public Node invertLinkedList(Node node) {
if (node.next == null) {
return node;
}
// Step 1: Flip the list after node
Node newHead = invertLinkedList(node.next);
// Step 2: Set node's successor node to node (4), and set node's successor node to null (to prevent ring)
node.next.next = node;
node.next = null;
// Step 3: Return the flipped head node
return newHead;
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
int[] arr = {4.3.2.1};
for (int i = 0; i < arr.length; i++) {
linkedList.addNode(arr[i]);
}
Node newHead = linkedList.invertLinkedList(linkedList.head.next);
// Do not forget to set the head node's successor!
linkedList.head.next = newHead;
linkedList.printList(); // print 1,2,3,4
}
Copy the codeVoiceover: Since the successor node of head changes after the flip, don’t forget to reset it!
InvertLinkedList recurses n times, so the time is O(n). InvertLinkedList recurses n times, so the space is O(n). I’m pressing n times, so the space complexity is also O(n).
Recursive function to understand must be from the function, from the function of the function, the recursive functions defined clearly understand, defined later, due to problems with split up the solution of the subproblem with the same train of thought, so the child the functions can be defined as long as the last call, never were unfolding subproblems, which is recursive common pitfalls. If you look closely at the function, it is actually implemented as shown in the following figure. (check the code to see if it is clear ^_^)
- Non-recursive flipped lists (iterative solution)
We know that recursion is more likely to cause stack overflow, so if there are other algorithms with similar or better time/space complexity, the non-recursive solution should be preferred. Let’s look at how to use iteration to flip the list. The main idea is as follows
Step 1: Define two nodes: pre and cur, where CUR is the successor node of PRE. If it is defined for the first time, it is necessary to remove the pointer that pre points to CUR. Otherwise, due to the subsequent reversal of the linked list, cur will point to Pre, and a loop is made (as follows)
Step 2: Once you know cur and pre, it is easy to flip, you can point cur to Pre, then set cur to pre, set the subsequent node of cur to cur and repeat this step forward. The complete GIF is as follows
Note: As with the recursion, the successor node of head changes from 4 to 1 after the iteration, so be sure to reset it.
Know to understand the idea, the implementation of the code is much easier, directly on the code
/** * Iteratively flip */
public void iterationInvertLinkedList(a) {
/ / step 1
Node pre = head.getNext();
Node cur = pre.getNext();
pre.setNext(null); // Pre is the head node to avoid the loop after flipping the list
/ / step 2
while(cur ! =null) {
/** * Do pay attention!! */ * * * * * * * * * * * * * * * *
Node next = cur.getNext();
cur.setNext(pre);
pre = cur;
cur = next;
}
// In this case, pre refers to the end node of the original list, which is the successor node of the head list
head.next = pre;
}
Copy the codeThe time complexity is O(n) because the loop is n times, and the space complexity is O(1) because there is no extra space to use, and the recursive function is not called to keep pressing the stack like recursion. Compared with recursion, the space complexity is O(1).
It took a lot of effort to figure out how to flip the list, and if you look at the next few twists of the flip list, you’ll see that the length of time we spent talking about flip the list was worth it.
Now let’s look at the distortion of a list flip
Given a list of the head node head, and two integers from and to, in the list to the from node and node to the part of the flip. Given, for example, the following list, the from = 2, head to = 4 – > 5 – > 4 — — > 3 — – > 2 – > 1 after the flip, list into the head – > 5 – > 2 – > 3-4 – > > 1
With the idea of flipping the whole list before, it is relatively easy to flip part of the list now. The main steps are as follows:
- From -1, from, to, to+1, to+1, to+1, to+1, to+1, to+1, to+1, to+1 The from and to nodes may also exceed the tail nodes, which are not reversed.
- Invert the node from to to
- Point the from-1 node to the to node and the FROM node to + 1 node
Know the above idea, the code is simple, according to the above steps 1,2,3 to achieve, comments are also written in detail, look at the following code (from to the node of the reversal we use iterative reversal, of course, the use of recursion is also possible, limited to the length of the relationship is not expanded, you can try).
/** * Iteratively flip nodes from to */
public void iterationInvertLinkedList(int fromIndex, int toIndex) throws Exception {
Node fromPre = null; / / the from 1 nodes
Node from = null; / / the from nodes
Node to = null; / / to node
Node toNext = null; / / to + 1 nodes
Step 1: Find from-1, from, to, to+1
Node tmp = head.next;
int curIndex = 1; // The index of the header node is 1
while(tmp ! =null) {
if (curIndex == fromIndex-1) {
fromPre = tmp;
} else if (curIndex == fromIndex) {
from = tmp;
} else if (curIndex == toIndex) {
to = tmp;
} else if (curIndex == toIndex+1) {
toNext = tmp;
}
tmp = tmp.next;
curIndex++;
}
if (from == null || to == null) {
// Do not flip when from or to exceeds the end node
throw new Exception("Not eligible.");
}
// Step 2: Use the loop iteration method to flip nodes from to to
Node pre = from;
Node cur = pre.next;
while(cur ! = toNext) { Node next = cur.next; cur.next = pre; pre = cur; cur = next; }// Step 3: Point from-1 to the to node (if the head node is reversed from the head node, you need to reset the head successor), and point from to + 1
if(fromPre ! =null) {
fromPre.next = to;
} else {
head.next = to;
}
from.next = toNext;
}
Copy the codeDeformation problem 2: give a linked list, each k nodes a group to flip, and return the flipped list. K is a positive integer whose value is less than or equal to the length of the list. If the total number of nodes is not an integer multiple of K, the last remaining nodes are kept in their original order.
Example: given the linked list: the head – > 1 – > 2 – > 3 – > when k = 2, 4 – > 5, shall return: the head – > 4 – > 2 – > 1 – > 3 – > 5 when k = 3, shall return: the head – > 3 – > 2 – > 1 – > 4 – > 5:
- Your algorithm can only use constant extra space.
- You can’t just change the values inside a node, but actually switch nodes.
This problem is the original problem of LeetCode, which belongs to the hard level. If you understand this problem, it should be basically ok to flip the linked list. With the basis of flipping the linked list before, I believe this problem is not difficult.
As long as we can find a way to flip a list of K nodes, the problem is solved (then we just have to repeat the flip for a list of K nodes).
Let’s take the following linked list as an example
-
First, we need to record a set of three successive nodes of this linked list, defined as startKPre, and then define a step to iterate twice from the head node (1) of this linked list to find the starting and ending nodes of this linked list, as shown in the figure below
-
After startK and endK are found, the list of startK and endK is flipped according to the previous iterative flipping method
-
Then, startKPre is pointed to endK, and startK is pointed to endKNext, which completes the reversal of a group of K nodes.
Once you know how to flip a set of K nodes, you only need to flip the list of k nodes repeatedly. The following code should be easier to understand according to the diagram
/** * the list is inverted every k@param k
*/
public void iterationInvertLinkedListEveryK(int k) {
Node tmp = head.next;
int step = 0; // Count to find the head and tail
Node startK = null; // number of nodes in a linked list
Node startKPre = head; // k prefixes of a set of linked list header nodes
Node endK; // there are k end nodes in a list
while(tmp ! =null) {
// The next node of TMP, because the replacement node of TMP will change, so save ahead of time
Node tmpNext = tmp.next;
if (step == 0) {
// the number of nodes in a list is k
startK = tmp;
step++;
} else if (step == k-1) {
// At this point, k endK of a set of linked list intervals are found, and this part of the list is flipped by iteration
endK = tmp;
Node pre = startK;
Node cur = startK.next;
if (cur == null) {
break;
}
Node endKNext = endK.next;
while(cur ! = endKNext) { Node next = cur.next; cur.next = pre; pre = cur; cur = next; }In this case, endK and startK are the first and last nodes in a set of linked lists
startKPre.next = endK;
startK.next = endKNext;
// The current group of k is finished, and the next group of K is started
startKPre = startK;
step = 0;
} else{ step++; } tmp = tmpNext; }}Copy the codeWhat’s the time complexity? I’m going through the list n times, and I’m going to flip every k nodes, so I’m going to flip it n times, so the time complexity is O(2n), so I’m going to get rid of the constant terms, so it’s O(n). Note: the time complexity of this problem is thought to be O(k * n), in fact, it does not flip the list every time the loop, only when the loop list elements every K nodes will flip
Deformation 3: Deformation 2 is for the order of k a group of flips, then how to reverse the order of K a group of flips
For example, given the following list, the head — — > 1 > 2 > 3 — – > 4 – > 5 reverse k after a group of flip, list into (k = 2) head – > 1 – > 3 – > 2 – > 5 – > 4
This question is a bytedance interview question, it is really sick enough, the order k a group of flip is already a hard level, reverse order K a group of flip is a super hard level, but in fact, with the previous knowledge, it should not be difficult, just a little deformation, as long as the following deformation of the list can be
Each step of the code is actually using a good function we implemented before, so we did before every step is foreshadowed oh! To solve bytedance’s ultimate interview question!
/** * invert a list of each k *@param k
*/
public void reverseIterationInvertLinkedListEveryK(int k) {
// Flip the list first
iterationInvertLinkedList();
// A set of k inverted lists
iterationInvertLinkedListEveryK(k);
// Flip the list again
iterationInvertLinkedList();
}
Copy the codeTherefore, it is very important to master basic list flipping! The problem is more in this basis to do the corresponding deformation
conclusion
In detail in this paper, the essential difference between a linked list and array believe that everybody on the difference between the two should have a more profound understanding of, especially the program locality principle, I believe you should be able to shine at the moment, then turn through the list of unit 1 introduction, believe that after the list turn what should not be too difficult for us, However, I suggest that you personally implement the code in the article oh, so that the impression will be more profound! Some look like the train of thought is such one thing, but the real operation will still have many pits, paper come zhongjue shallow, must know this matter to practice!
All of the code in this article has been updated on my Github address, and you can download and run it if you want
In the next article, we’ll look at another key point in solving linked lists: the fast pointer. Stay tuned!
If it is helpful, please kindly forward + looking, thanks!
