Three hundred rows per day (13 days: linked list)
Note: here are the synchronous notes and records of JAVA self-study and understanding. If you have any questions, please correct them
1, About linked list
The logical structure and physical structure of the linked list are not as close as the sequential list. The physical storage of the linked list is not strictly continuous. Its continuity is not guaranteed by the hardware, but more guaranteed by the relevant variables in the code, which is what we call "chain".
It's like our chain, one after another, but this is the image of the linked list we logically explain, but in fact, our chain in physical storage is not so clear. Specifically, physical storage is more like the headset you take out of your pocket:
Because it has been said that its physical address space is not necessarily continuous, it is possible that the next address of the natural link may be larger and smaller than the current address.
Linked list has many excellent properties. The first is its excellent deletion and insertion properties. Its insertion only needs to create a new node and modify the link pointer relationship between two logically connected nodes in the linked list, which is more consistent with our abstract logical thinking. Instead of using the troublesome "piecewise coverage" strategy like the incidentally table, excellent O(1) complexity is obtained.
However, the linked list also has some shortcomings. For example, it can not realize random access. This makes it impossible to access a specific location with O(1) as easily as a sequential table, so sequential access must be used to access data.
These defects are also reflected in the physical storage of files in the operating system - files stored by chain storage are not commonly used in the storage structure of files (in addition, the reason is that the chain pointer in the disk is relatively fragile. Once the disk has bad points and loses the pointer, the whole file will be damaged), The continuous structure with the highest access efficiency is often used to realize high-speed storage.
Of course, the data structure is not achieved overnight, or it is almost a golden storage structure. We should tailor our clothes, analyze specific problems, and choose their own advantages and disadvantages, so as to choose the best data structure.
2, JAVA's distinctive "chain" of linked lists
1. Talk about the changes of the pointer today
In fact, we can find a natural phenomenon. With the higher level of language, we seem to dislike the use of pointers more and more. Among many common languages, only C and C + + still insist on using the concept and statement of pointer, while subsequent high-level languages, such as Python and Java, directly abandon this concept, and c# politely avoids this concept and uses it through unsafe (generally, delegate is used).
However, maybe when we study, we only look at concepts, which is true.
(refer to website )However, some people made the following comments, which I feel very reasonable.
"Every language uses pointers, and C/C + + just exposes it rather than hides it"
In the era when C was born, memory and CPU computing power were very valuable resources. The "pointer" provided by C language is more similar to the indirect addressing ability of assembly language, which can give programmers great flexibility in memory operation. In addition, C's function parameters lack "writability", and C language lacks the data type of "string". All these problems need to be solved with pointers.
Up to now, C is still widely used in operating system kernel and embedded development. The reason is that it enables programmers to "manipulate" hardware more directly and obtain high performance.
Therefore, with the development of computer, we gradually began to separate the distinction between the hardware and software of programmers. Now the high-level language gradually hides the position of "pointer", which is the representative from the bottom. But my opinion is that the first language for any computer learner should still be C. beginners of computer still need to contact the pointer. After all, the address thought contained in the pointer can lay the foundation for a computer learning career.
2. Linked list implemented in Java
Therefore, java naturally does not have the concept of pointer, so how to implement the linked list.
In operation, the most intuitive method is that when establishing a node, the "Next" variable pointing to the Next position is no longer and can not be the address of the "Next node", but directly the "Next node" itself. In fact, the java linked list may be simpler than the general C/C + + linked list, but our preconceived habits lead us to use it "strangely".
/**
* An inner class
*/
class Node {
/**
* The data
*/
int data;
/**
* The reference to the next node
*/
Node next;
/**
*******************
* The constructor
*
* @param paraValue The data.
*******************
*/
public Node(int paraValue) {
data = paraValue;
next = null;
}// Of the constructor
}// Of class Node
The above is a class nested in the defined linked list class, which is used to define the node characteristics of the linked list.
Here we use node next; The type of next is the node type itself, and no longer has the characteristics of address.
From my understanding, the feature of "one ring to one ring" in our common linked list actually exists only when C/C + + has an address agent (pointer), because the feature of pointer is like an arrow, indicating the address of a data type, not the data type itself.
In essence, the picture drawn by JAVA's linked list is not like this kind of picture. From my point of view, it is more like this image of "dolls":
So you can understand that the linked list in high-level language (non C/C + +) is more like the generalized list defined in our data structure.
However, in practical problems, for the convenience of analysis, we still use the original linked list of "one link one link" for analysis, because it is easier to understand logically.
Let's improve the basic properties and constructors of our linked list (for the assignment of constructors, please refer to the code created by the Node class above):
/**
* The header node. The data is never used.
*/
Node header;
/**
*********************
* Construct an empty linked list.
*********************
*/
public LinkedList() {
header = new Node(0);
}// Of the first constructor
2, Clearing method of linked list
The code is as follows:
/**
*********************
* Reset to empty. Free the space through garbage collection.
*********************
*/
public void reset() {
header.next = null;
}// Of reset
The emptying operation seems to be much simpler than our common linked list. We only need to make the next point of the header node (the linked list we create is the linked list of the leading node) empty. When thinking for the first time, you may fall into the doubt of "why not release the back".
To tell the truth, I also fell into this contradiction at the beginning of the period and checked it online. But then I suddenly thought that I might be trapped in the thinking formula of C/C + + linked list.
Pay attention to the actual picture of the JAVA linked list I just drew, header Next is not the address of the pointer. At least the size is definitely not the size of the address space. It is a fixed value, but the size of a Node object. However, the size of the Node will expand according to the length of the table (because there is another attribute in the Node class declaration, which constitutes the phenomenon of attribute dolly. This dolly stops at a Node = null), so this is a simple header Next is not as simple as "next Node", but all nodes behind the header
After this explanation, header next = null; The doubt about the emptying effect of is solved.
3, Linked list traversal
The code is as follows:
/**
*********************
* Overrides the method claimed in Object, the superclass of any class.
*********************
*/
public String toString() {
String resultString = "";
if (header.next == null) {
return "empty";
} // Of if
Node tempNode = header.next;
while (tempNode != null) {
resultString += tempNode.data + ", ";
tempNode = tempNode.next;
} // Of while
return resultString;
}// Of toString
The traversal of the linked list is the iterative operation of the object, not the subscript increment operation of the sequential list. We use tempnode = tempnode next; The operation of completes the effect of subsequent iterations of the object until tempNode == null ends the iteration.
In the specific implementation, the basic robustness guarantee is provided first (if the judgment is empty, the table will not be traversed). The first step is to create a work node, because our traversal only requires access to the valid data area, so the work node is the next position of the header pointer node tempnode = header next;
Then complete the iteration of the effective area through the while operation and input it into the output character. It's not very difficult.
4, Linked list positioning by value
The code is as follows:
/**
*********************
* Locate the given value. If it appears in multiple positions, simply return
* the first one.
*
* @param paraValue The given value.
* @return The position. -1 for not found.
*********************
*/
public int locate(int paraValue) {
int tempPosition = -1;
Node tempNode = header.next;
int tempCurrentPosition = 0;
while (tempNode != null) {
if (tempNode.data == paraValue) {
tempPosition = tempCurrentPosition;
break;
} // Of if
tempNode = tempNode.next;
tempCurrentPosition++;
} // Of while
return tempPosition;
}// Of locate
The algorithm of linked list location by value is nothing more than the expansion of traversal algorithm.
Because as long as a counter is synchronously updated based on the original traversal, and then the data is terminated and the counter is returned when the data is found.
Based on this idea, the follow-up question is what kind of code to reflect and how to locate the subscript in your linked list. Our code defines that the head node is not included in the effective count, so the first effective node is the subscript 0 (the second node of the whole chain).
First set the default subscript value tempPosition to - 1. The reason for setting a default illegal value is that in the case of an empty table, the while() loop will not be executed, which is convenient for directly skipping the illegal value returned when the while returns directly. Caution: this number has no effect on checking.
We just put the counter in while() to count, and wait until tempnode After data = = paravalue, deliver the counter to tempPosition, exit while() and the result will be delivered by tempPosition. This advantage is that after all traversals are completed, but no conditions such as fetching are met, tempPosition will not know the counter, so it will still return the default value of - 1, warning that there is no such number.
5, Linked list insertion operation
The code is as follows:
/**
*********************
* Insert a value to a position. If the list is already full, do nothing.
*
* @param paraPosition The given position.
* @param paraValue The given value.
* @return Success or not.
*********************
*/
public boolean insert(int paraPosition, int paraValue) {
Node tempNode = header;
Node tempNewNode;
for (int i = 0; i < paraPosition; i++) {
if (tempNode.next == null) {
System.out.println("The position " + paraPosition + " is illegal.");
return false;
} // Of if
tempNode = tempNode.next;
} // Of for i
// Construct a new node.
tempNewNode = new Node(paraValue);
// Now link them.
tempNewNode.next = tempNode.next;
tempNode.next = tempNewNode;
return true;
}// Of insert
The core of the insertion operation of linked list lies in two parts
1. Find the location
2. Insert
1. Insertion of O (1)
Note that the O(1) I mentioned here mainly refers to the complexity of inserting the operation itself, not the complexity of finding the location of the value.
To put it simply, inserting is the process of modifying two pointers, but the premise is to find the node in front of our target element:
Necessary preparations:
1). Know that I want to delete the value of node 2
2). Get the pointer of node 1 before node 2
3). Create node 5 and complete the necessary assignment
Specific operation:
1). Point the next of the new node 5 to our target node
2). The next pointer of the previous node 1 points to our new node 5
complete
It should be noted that the operation process is not replaceable. Step 2 has the function of breaking the chain. This operation must be executed last. Once it is executed first, the 5 node will not be able to find the subsequent node to be inserted.
2. Insertion positioning skills and special circumstances
The problem of finding the location is similar to the counter function of the locate() function we just constructed.
The above insertion logic has a basic premise: know the precursor node of the target node.
for (int i = 0; i < paraPosition; i++) {
if (tempNode.next == null) {
System.out.println("The position " + paraPosition + " is illegal.");
return false;
} // Of if
tempNode = tempNode.next;
} // Of for i
Here we illustrate with an example:
① When our paraPosition < length (total logical length of the linked list), for example, the paraPosition in the figure below can be 0,1,2.
Here, we create a precursor pointer tempNode. In order to perform the insertion operation normally, we need to ensure that the tempNode pointer accurately falls in front of the insertion node.
As long as the subscript of temp i=0 is always in front of the node, we can ensure that every time we traverse the node, we can always start from the subscript of temp i=0, so as to ensure that the node is always in front of the subscript of temp i=0.
If the position we need to insert is paraPosition=1, the above code for loop will be executed only once and tempNode will be executed only once, just in front of paraPosition=1.
But here's a special note. Although the method we use is a forward interpolation method, there are cases where logical backward interpolation can be realized.
② When our paraposition = length (the total logical length of the linked list), it is logically out of bounds
In the above figure, the for loop will be executed three times, i=2 for the third time, and tempNode = tempNode will be completed according to the code at the end of this round next; Operation, tempNode moves from the position of subscript 1 to the position of subscript 2, and then a new round of for loop ends because i == 3 does not meet i < paraposition. Although the loop ends and the i local variable is cleared, the tempNode always stops at the position of the last element.
When inserting at this time, tempNode implements an insertion between the tail node and NULL. Because we logically ignore NULL, it constitutes an illusion of inserting after the last element.
But its essence is that i points to NULL, so why can i point to NULL? Because there is any for loop, the loop factor is from [0, N]. When the for loop ends normally, the loop factor is always N.
③ When our paraposition > length (total length of linked list logic), that is, we need to end the code before the for loop is finished.
In this case, there is no need to use the diagram to help explain. It will be simpler if we directly combine it with code analysis.
If the number of iterations of the for loop becomes larger, the only possible error is tempnode = tempnode next;， Therefore, as long as the tempnode is guaranteed every round next; It can't be null, because the precursor nodes are null (pointing to the next element of the tail node). There must be no target node after the precursor.
6, Linked list deletion
The code is as follows:
public boolean delete(int paraPosition) {
if (header.next == null) {
System.out.println("Cannot delete element from an empty list.");
return false;
} // Of if
Node tempNode = header;
for (int i = 0; i < paraPosition; i++) {
if (tempNode.next.next == null) {
System.out.println("The position " + paraPosition + " is illegal.");
return false;
} // Of if
tempNode = tempNode.next;
} // Of for i
tempNode.next = tempNode.next.next;
return true;
}// Of delete
The core of the deletion operation of linked list lies in two parts
1. Find the location
2. Delete
Finding the location is the same as the insertion scheme. I won't repeat it here. We mainly discuss the characteristics of the deletion operation itself.
1. Deletion of O (1)
Deleting itself is simpler than inserting.
To put it simply, insertion is the process of modifying two pointers, while deletion only needs to modify one pointer.
Necessary preparations:
1). Know that I want to delete the value of node 1
2). Get the pointer of node 0 before node 1
Specific operation:
1). Point the next of the precursor node 0 to the next node of our target node 1
complete
If it is a language with real pointers such as C/C + +, it may also need to use the free() method to release the space of node 1, but we also said when talking about the deletion of Java linked list just now: the Java pointer does not refer to the address, but the node itself. Therefore, this is only a value assignment operation and does not need the programmer to manually complete the release operation.
6, Simulation
The code is as follows:
public static void main(String args[]) {
LinkedList tempFirstList = new LinkedList();
System.out.println("Initialized, the list is: " + tempFirstList.toString());
for (int i = 0; i < 5; i++) {
tempFirstList.insert(0, i);
} // Of for i
System.out.println("Inserted, the list is: " + tempFirstList.toString());
tempFirstList.insert(5, 100);
// tempFirstList.delete(4);
// tempFirstList.delete(2);
System.out.println("Deleted, the list is: " + tempFirstList.toString());
tempFirstList.delete(0);
System.out.println("Deleted, the list is: " + tempFirstList.toString());
for (int i = 0; i < 5; i++) {
tempFirstList.delete(0);
System.out.println("Looped delete, the list is: " + tempFirstList.toString());
} // Of for i
}// Of main
The operation results are as follows:
summary
Today seems to be the most written time. After all, it is our dear chain structure.
In fact, the linked list is the first barrier encountered by many programmers. Anyway, when I first learned programming a few years ago, I just didn't understand it for a long time. I felt that it was obscure and difficult to understand, and I couldn't carry the address, node and pointer clearly.
But with the increase of your programming time and the expansion of other computer knowledge, you will become more and more familiar with it. Until now, it has appeared in the minds of programmers as basic common sense.
But I have to say that writing linked lists in Java today is my first time to write linked lists in a language without pointers. I have many unique experiences. Although I feel that it is not as easy as C/C + + writers, and some places are always confused by the address of C/C + + pointers, this attempt also gives me a new understanding of the chain structure simulation of these high-level languages, Especially when it is suddenly found that the storage structure of Java is not a "chain" in the traditional sense of "one ring one ring", but more like a generalized table.