catalogue
1, Simple understanding of linked list
1. What does the linked list look like?
2, Code implementation of linked list
2. Construction of linked list
4. Find whether to specify whether the element is in the single linked list
5. Insert an element at the specified position in the linked list
6. Delete the first occurrence of the specified element in the linked list
(1) Print the whole linked list
(2) print the linked list from the given position
1, Simple understanding of linked list
In my last article, I explained the sequence list in detail. We can know that the sequence list is stored sequentially in memory, but the linked list we will explain in this article is just the opposite. The linked list is stored randomly in memory, which also shows that the linked list is very flexible. It can make rational use of a lot of space, and can realize their own connection through some "secret signals".
1. What does the linked list look like?
The linked list is composed of nodes, which are connected one by one like the train carriage, as shown in the figure below
2. What is the node?
The linked list is composed of one node. As shown in the figure below, the storage of each data in the linked list is composed of the following two parts:
- The area of the data element itself is called the data field;
- The area where the pointer to the direct successor element is located is called the pointer field;
Our linked list is linked by nodes. According to the above figure, it is not difficult to find that a node has two essential parts, one to store data and the other to store the address of the next node. Through the above understanding, we almost have a preliminary understanding of the linked list. Next, we start to build our own linked list with code.
2, Code implementation of linked list
1. Construction of nodes
The construction of a linked list is inseparable from the composition of nodes, so the first step of building a linked list is of course to lay the foundation and establish nodes. We can create a class to realize the creation of a node, and then assign a value to the node through the assignment of the construction method. Of course, this reference must be the reference of this node type, because our linked list is basically realized by pointing to the next node through the node
class NodeList{
public int date;
public NodeList next;
public NodeList(int num){
this.date = num;
}
}2. Construction of linked list
With a node, we can build a linked list. First, a linked list must have a head node. If there is no head node, there will be no leader, and all the linked list data will be lost. Therefore, this head node is very important, and then initialize the linked list. In fact, it is not different from the construction of nodes. I also use a construction method to define the beginning of a linked list, But the construction method of the node is to assign a value to the node, and the linked list initialization is to build a node and assign a value to it.
public NodeList head;
public MyLinkedList(int num){
this.head = new NodeList(num);
}3. View linked list length
To find the length of the linked list, we need to build a sentinel node to traverse the whole linked list. When the sentinel node is null, a size value is returned.
//Get the length of the single linked list
public int size(){
int count = 0;
NodeList cur = this.head;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}4. Find whether to specify whether the element is in the single linked list
This needs to build a method with boolean type as the return value. First, we should establish a sentinel node and traverse the whole linked list. If the value stored in a node is the same as the specified element, it will return True. After traversing the linked list, it will return False if it has not been found
//Check whether the keyword is included and whether the key is in the single linked list
public boolean contains(int key){
NodeList cur = this.head;
while(cur != null){
if(cur.date == key){
return true;
}
cur = cur.next;
}
return false;
}5. Insert an element at the specified position in the linked list
Like the sequence table, there are three cases
(1) . tail insertion
This is the simplest insertion method. Just point the next of the last node to the new node
//Tail interpolation
public void addLast(int num){
NodeList nodeList = new NodeList(num);
if(this.head == null){
this.head = nodeList;
}else{
NodeList cur = this.head;
while(cur.next != null){
cur = cur.next;
}//cur == null
cur.next = nodeList;
}
}(2) head insertion
For head insertion, we need to consider the problem of head pointer. We can solve it in two steps:
The first step is to point the next pointer of the new node to the head pointer of the original linked list.
The second step is to change the new node into a new header pointer.
//Head insertion
public void addFirst(int num){
NodeList nodeList = new NodeList(num);//Create a node first
nodeList.next = this.head;
this.head = nodeList;
}(3) middle insertion
The middle insertion is also divided into two steps:
Step 1: the next pointer of the new node, pointing to the insertion position
In the second part, the next pointer of the front node at the insertion position points to the new node
/**
* Find the address of the node at index-1
* @param index
* @return
*/
public NodeList findIndex(int index){
NodeList cur = this.head;
while(index - 1 != 0){
cur = cur.next;
index--;
}
return cur;
}
/**
*
* @param index Insertion position
* @param num Insert element
* We can judge first, then find and then insert
*/
//Insert at any position, and the first data node is subscript 0
public void addIndex(int index,int num) {
if (index < 0 || index > size()) {
System.out.println("erro");
return;
}
if(index == size()){
addFirst(num);
return;
}
if(index == size()){
addLast(num);
return;
}
NodeList nodeList = new NodeList(num);
NodeList cur = findIndex(index);
nodeList.next = cur.next;
cur.next = nodeList;
}6. Delete the first occurrence of the specified element in the linked list
Deleting elements and adding elements are similar. They are also three methods
(1) . tail deletion
The simplest way to delete the tail is to direct the next point of the penultimate node to null
(2) header deletion
Set the original head node of the linked list as the next pointer of the original head node
(3) intermediate deletion
Point the next pointer of the front-end machine node of the node to be deleted to the next pointer of the element to be deleted
The premise is that we need to build a method to find the subscript of the previous node of the element to be deleted, so that we can use the next of the node to directly point to the next of the deleted element
/**
* Find the precursor of the keyword to delete
* @param key
* @return
*/
public NodeList searchPerv(int key){
NodeList cur = this.head;
while(cur != null){
if(cur.next.date == key){
return cur;
}//Note that cur next
cur = cur.next;
}
return null;
}
//Delete the node whose keyword is key for the first time
public void remove(int key){
if(this.head == null){
System.out.println("erro");
return;
}
if(this.head.date == key){
this.head = this.head.next;
return;
}
NodeList cur = searchPerv(key);
NodeList del = cur.next;
cur.next = del.next;
}7. Printing of linked list
This is very simple. We just need to traverse the linked list and print the elements on the node in turn
(1) Print the whole linked list
public void display(){
NodeList cur = this.head;//cur to traverse the linked list
while(cur != null){
System.out.print(cur.date+" ");
cur = cur.next;
}
System.out.println();
}(2) print the linked list from the given position
/**
* Print from the specified header node
* @param newHead Given head node
*/
public void display2(NodeList newHead){
NodeList cur = newHead;
while(cur != null){
System.out.print(cur.date+" ");
cur = cur.next;
}
System.out.println();
}8. Empty linked list
There will be a thorny problem in clearing the linked list, that is, if we release each reference from the first node and release null, but when we release the end point reference for the first time, we will find that the whole list is lost. At this time, we need to set up a sentry node. Before each release, we record the position of the head node, and then wait until the head node is released, We don't have to lose our previous position
public void clear(){
while (this.head != null) {
NodeList curNext = head.next;
this.head.next = null;
this.head = curNext;
}
}3, Summary
Through this article, we can find that in fact, the data structure is not so-called good or bad. The same is true for linked list and sequential list. It can be said that they have their own strengths and strengths. I have summarized the performance of linked list and sequential list in the following table
It is not difficult to find that the advantage of sequential list is to find and update an element, while the advantage of linked list is to insert and delete.
For the combination that needs to be searched and updated frequently, we choose the sequence table better.
For the combination that needs to be continuously inserted and deleted, we choose the linked list as the best.
Well, this article ends here. I'm glad to finish this article on the eve of Liverpool's upcoming finals. I hope Liverpool can win the championship!!! I'm Benni. I'll see you next time 😁😁😁😁😁