preface
The bottom foundation determines the development of the top.
Just like it and let me know you’re paying attention to technology.
This series of articles has been included in the Github Backend advancement Guide. The project is under development. Welcome star.
Preview of this series:
What is a linked list?
Linked list is also a linear list, the array is the sequential structure of the linear list, and the linked list is the chain storage structure of the linear list, it is a discontinuous, non-sequential data structure in memory, composed of a number of nodes. Each node stores data and the address of the next node. The one that stores data is called a data domain, and the one that stores addresses is called a pointer domain. Pointers are divided into precursor Pointers and successor Pointers, which are used to record the position of the previous node and the next node respectively.
Pointer: Assigning a variable to a pointer actually assigns the address value of the variable to the pointer, which can be regarded as a Reference in Java.
1.1 Unidirectional linked lists
A one-way linked list, as its name implies, is a linked list with only one direction. As shown in the figure above, a one-way linked list consists of several nodes, and each node is divided into two parts, one storing data and the other storing the location of the next node. In graph terms, the orange squares are called data fields, where data is stored. The yellow square is called the pointer field and is used to store the location of the next node, which is also called the successor pointer.
If you look at the diagram above, there are two special places, the first node and the last node. We can also call it a header or a tail. What’s so special about these two nodes? The head node can start the list with no data, and the tail node’s subsequent pointer points to NULL, indicating that this is the last node in the list.
Head node: The first node in a linked list. The head node may not store data.
Head pointer: Pointer to the first node in the list, used to store the base address of the list, and is the beginning of the entire list.
Tail node: The last node in the list, pointing to an empty null indicating that this is the last node in the list.
1.2 Unidirectional circular linked lists
Unidirectional lists are derived from unidirectional lists. The only difference is that the tail pointer of a unidirectional list points to NULL, whereas the tail pointer of a unidirectional list points to the head node. Such a single linked list connected end to end is called a unidirectional cyclic 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, which is suitable for dealing with circular structure problems, such as the famous Joseph problem.
1.3 Bidirectional linked lists
Bidirectional lists are a little more complicated because they have a precursor pointer in addition to a successor pointer. If you store the same amount of data, bidirectional lists take up more space than unidirectional lists. Although two Pointers in a bidirectional list are a waste of space, they support bidirectional traversal and give the list itself more flexibility.
1.4 Bidirectional circular linked lists
Once you know about circular and bidirectional lists, you can combine the two together to create a bidirectional circular list. You can see from the diagram that the precursor of the head node points to the tail node, and the successor of the tail node points to the head node. I’m not going to do too much here, but you know what kinds of lists there are.
2. Linked lists vs. arrays
Talking about the linked list for a long time, I do not know if you understand, I feel very boring. But the foundation is such, only to learn the foundation to better climb. Now let’s see how lists differ from arrays. First of all, the two storage structures are different. An array is a sequential storage structure, which means it is a contiguous storage space in memory, while a linked list is a chained storage structure, which means it is discontiguous. Let’s see how they behave in memory:
Through the picture, I believe you have seen the difference, because the array is a continuous storage structure, the CPU cache mechanism can be used to preread the data in the array, so the access efficiency is higher. Linked lists are not stored consecutively in memory, so they are not CACHE-friendly and cannot be preread effectively. Due to different data structures, the time complexity of array and linked list insertion, deletion, random access and other operations is opposite.
| An array of | The list | |
|---|---|---|
| Insert, delete | O(n) |
O(1) |
| Random access | O(1) |
O(n) |
Linked lists naturally support dynamic scaling because they do not generate memory up front, but only when it is actually used. The disadvantage of the array is that the size is fixed, the application is wasteful, the application is less often have to expand, move the array, if the amount of data is very time-consuming. If you can predict the size of the data in advance, it is better to specify the size during initialization to avoid the impact of moving data during expansion.
3. Basic operations of linked lists
3.1 The addition of linked lists
There are three cases for adding linked lists:
-
Increase to head
The first step is to point the successor pointer of the new node to the original head node, and the second step is to change the new node into the head node. This completes the header addition.
-
Add to the middle
Intermediate insertion is also divided into two steps. In the first step, the successor pointer of the node in front of the insertion position points to the new node; in the second step, the successor pointer of the new node points to the original node at the insertion position.
-
Add to tail
The tail of the list is the easiest to insert, simply pointing the last node’s successor to the new node.
Let’s take a look at the code, if you have enough time, I suggest you manually type it, so you can understand it more deeply.
/ * *
* @author: lixiaoshuang
* @create"But it: 2019-12-08
* * /
public class LinkedListAddDemo {
/ / head node
private static Node headNode = null;
/ / end nodes
private static Node lastNode = null;
// The length of the list
private static int size;
public static void main(String[] args) {
// Initialize a linked list
addByIndex(1.0);
addByIndex(2.1);
addByIndex(3.2);
addByIndex(4.3);
// Insert the header
addByIndex(5.0);
printNode(); // Output 5, 1, 2, 3, 4
// Insert in the middle
addByIndex(5.2);
printNode(); // Output 1, 2, 5, 3, 4
// Insert the tail
addByIndex(5.4);
printNode(); // Output 1, 2, 3, 4, 5
}
private static void addByIndex(int data, int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Out of list node range");
}
Node node = new Node(data);
if (index == 0) {
// Insert into the header
node.setNext(headNode);
headNode = node;
if (size == 0) {
lastNode = node;
}
} else if (index == size) {
// Insert to the tail
lastNode.setNext(node);
lastNode = node;
} else {
// Insert into the middle
Node prevNode = get(index - 1);
Node nextNode = prevNode.getNext();
prevNode.setNext(node);
node.setNext(nextNode);
}
size++;
}
/ * *
* Find linked list nodes by location
*
* @param index
* @return
* /
private static Node get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Out of list node range");
}
Node temp = headNode;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
/ * *
* Print nodes
* /
private static void printNode(a) {
while(headNode ! =null) {
System.out.println(headNode.getDate());
headNode = headNode.getNext();
}
}
}
/ * *
* Define a node
*
* @param <T>
* /
class Node<T> {
/ * *
* Data in a node
* /
private T date;
/ * *
* Pointer to the next node
* /
private Node next;
public Node(T date) {
this.date = date;
}
public Node getNext(a) {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public T getDate(a) {
return date;
}
public void setDate(T date) {
this.date = date;
}
}
Copy the code3.2 Deletion of linked lists
There are also three cases of list deletion and addition:
-
Remove the head
Deleting a header simply sets the header node to the next node of the current header node.
-
Remove the middle
The intermediate deletion operation only needs to point the successor pointer of the previous node to the next node of the deleted node.
-
Remove the tail
Tail deletion is done by simply pointing the next-to-last node’s successor pointer to NULL.
/ * *
* @author: lixiaoshuang
* @create"But it: 2019-12-08
* * /
public class LinkedListAddDemo {
/ / head node
private static Node headNode = null;
/ / end nodes
private static Node lastNode = null;
// The length of the list
private static int size;
public static void main(String[] args) {
// Initialize a linked list
addByIndex(1.0);
addByIndex(2.1);
addByIndex(3.2);
addByIndex(4.3);
// Delete the header
delete(0);
printNode(); // Output 2, 3, 4
// delete the tail
delete(3);
printNode(); // Output 1, 2, 3
// Delete
delete(2);
printNode(); // output 1, 2, 4
}
/ * *
* List deletion operation
*
* @param index
* /
private static void delete(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Out of list node range");
}
if (index == 0) {
// Delete the header
headNode = headNode.getNext();
} else if (index == size - 1) {
// Delete the tail
Node prevNode = get(index - 1);
prevNode.setNext(null);
lastNode = prevNode;
} else {
// Delete the middle
Node prevNode = get(index - 1);
Node nextNode = prevNode.getNext().getNext();
prevNode.setNext(nextNode);
}
size--;
}
/ * *
* Find linked list nodes by location
*
* @param index
* @return
* /
private static Node get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Out of list node range");
}
Node temp = headNode;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
/ * *
* Print nodes
* /
private static void printNode(a) {
while(headNode ! =null) {
System.out.println(headNode.getDate());
headNode = headNode.getNext();
}
}
}
Copy the code3.3 Modification of linked list
Will be modified directly modify linked list node replacement for the new node, the first step will be modified first node before a subsequent node pointer to the new node, and then a new node of the subsequent pointer to the next node is modified node, here is how to modify a node, logic and add delete is the same as the above, here is an example of an intermediate modified by illustrations. If you want to modify the data in the node without replacing the node, this is pretty easy, you can do it yourself.
/ * *
* @author: lixiaoshuang
* @create"But it: 2019-12-08
* * /
public class LinkedListOperationDemo {
/ / head node
private static Node headNode = null;
/ / end nodes
private static Node lastNode = null;
// The length of the list
private static int size;
public static void main(String[] args) {
// Initialize a linked list
addByIndex(1.0);
addByIndex(2.1);
addByIndex(3.2);
addByIndex(4.3);
// Modify the header
update(5.0);
printNode(); // output 5, 2, 3, 4
// Modify the tail
update(5.3);
printNode(); // Output 1, 2, 3, 5
// Modify the middle
update(5.1);
printNode(); // Output 1, 5, 3, 4
}
/ * *
* Linked list modifications
*
* @param data
* @param index
* /
private static void update(int data, int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Out of list node range");
}
Node newNode = new Node(data);
if (index == 0) {
// Modify the header
Node next = headNode.getNext();
newNode.setNext(next);
headNode = newNode;
} else if (index == size) {
// Modify the tail
Node prevNode = get(index - 1);
prevNode.setNext(newNode);
lastNode = newNode;
} else {
// Modify the middle
Node prevNode = get(index - 1);
Node nextNode = prevNode.getNext().getNext();
prevNode.setNext(newNode);
newNode.setNext(nextNode);
}
}
/ * *
* Find linked list nodes by location
*
* @param index
* @return
* /
private static Node get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Out of list node range");
}
Node temp = headNode;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
/ * *
* Print nodes
* /
private static void printNode(a) {
while(headNode ! =null) {
System.out.println(headNode.getDate());
headNode = headNode.getNext();
}
}
}
Copy the code3.4 Linked list query
When it comes to query, I do not know if you found it, the above code has been implemented 😭, here in the paste, we have a look:
/ * *
* Find linked list nodes by location
*
* @param index
* @return
* /
private static Node get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Out of list node range");
}
Node temp = headNode;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
Copy the code4. Interview questions
4.1 How to determine whether a one-way linked list has rings?
Here we use the method of fast and slow Pointers to determine whether a linked list has a ring. First, create two Pointers pointing to the head node of the linked list at the same time. The slow pointer takes one step and the fast pointer takes two steps to determine whether the two Pointers are equal. Here is the one-way circular linked list we introduced above. As long as the list has rings, the two Pointers will always be equal when traversing it with fast or slow Pointers (Pointers are nodes). It’s like running in the park on weekends. If the young people run faster and the old people run slower, the young people will catch up with the old people and overtake them at some point. The reason is simple, because the track in the park is circular.
If you look at the code below, I made one small change to the tail insertion in the list insertion operation, which is to make each tail node’s successor point to the head node, so that the one-way list becomes a one-way circular list.
/ * *
* @author: lixiaoshuang
* @create"But it: 2019-12-08
* * /
public class LinkedListOperationDemo {
/ / head node
private static Node headNode = null;
/ / end nodes
private static Node lastNode = null;
// The length of the list
private static int size;
public static void main(String[] args) {
// Initialize a linked list
addByIndex(1.0);
addByIndex(2.1);
addByIndex(3.2);
addByIndex(4.3);
// Check whether the list has rings
boolean ringed = isRinged();
System.out.println(ringed); // The output is true
}
/ * *
* Determine if the linked list has rings
*
* @return
* /
private static boolean isRinged(a) {
if (headNode == null) {
return false;
}
// Define the speed pointer
Node slowPointer, fastPointer;
slowPointer = fastPointer = headNode;
while(slowPointer ! =null&& fastPointer ! =null) {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext().getNext();
// If two Pointers are equal, there is a ring
if (slowPointer == fastPointer) {
return true;
}
}
return false;
}
/ * *
* List insert operation
*
* @param data
* @param index
* /
private static void addByIndex(int data, int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Out of list node range");
}
Node node = new Node(data);
if (index == 0) {
// Insert into the header
node.setNext(headNode);
headNode = node;
if (size == 0) {
lastNode = node;
}
} else if (index == size) {
// Insert to the tail
lastNode.setNext(node);
lastNode = node;
node.setNext(headNode); // Insert the tail of the last node to the head node, so the list is circular.
} else {
// Insert into the middle
Node prevNode = get(index - 1);
Node nextNode = prevNode.getNext();
prevNode.setNext(node);
node.setNext(nextNode);
}
size++;
}
}
Copy the code4.2 How to reverse linked Lists?
This is also a high frequency interview question, here I will not write the implementation, when you leave a thinking question, have time friends can try to solve it, this problem although baidu under the solution method came out, but still hope you think about it, if you really can’t figure out in the search for the solution method. You can also go to “rip data structures and algorithms” to view the source code, I have a hand knock again.
Reference 5.
Comic Book Algorithm
The Beauty of Data Structures and Algorithms
Big Talk Data Structure
6. The ending
In my opinion, there are three basic knowledge that back-end programmers should learn: “data structures and algorithms”, “computer systems”, and “Linux operating system”. In the winter of the Internet, are we not wearing enough clothes? Having been up all night, I decided to lead you to learn three basic knowledge together. The first series of this series is “Data Structure and Algorithm of Hand Tearing”, and the next series will be started after each series is finished, so don’t worry. Can pay attention to my public account, continue to chase more, continue to learn.
This series of articles has been included in the Github Backend advancement Guide. The project is under development. Welcome star.
The articles in the public account are the original bloggers, and will always be updated. If you want to witness or grow with bloggers, welcome to follow!
Finally, to see the friends here, are willing to learn the spirit, thank you to finish reading my article, the blogger will not sum up, any questions welcome comment correction, if you feel a little harvest after reading praise, attention. I need your support on the way of writing. Your support is the motivation for the next article.