🥇 Why use chained lists
In the last blog post, the blogger detailed the ordering structure of linear tables, that is, the various functions of ordered tables, such as adding, deleting, and changing. See Last Blog Order Table
Let bloggers review the storage structure of the Sequence Table in the previous chapter for you
- Logically: Continuity
- Physically: Continuity
- When there is not enough storage space for the data, it opens up a space as long as the original space to store the data.
- The advantages of sequential tables:
- 1. There is no need to add additional storage space to represent the logical relationships of elements in a table
- 2. You can quickly access elements anywhere in the table.
- Disadvantages of sequential tables:
- 1. Insert and delete operations require a large amount of data to be moved and time consuming
- 2. When the length of a linear table changes a lot, it is difficult to determine the capacity of the space. For example, the original storage space of a linear table is 100 units. To store 101 data now, if there is not enough space, first open up double the length of the data space, and the storage space becomes 200, then 99 unused spaces will result in fragmentation of the storage space.
Today, the blogger is introducing a single-chain table, which has great advantages in inserting and deleting compared to a sequential table.
🥇 What is a single-chain list
The reverse order table needs to store data, each time it needs to open up a very large space to store data, how to solve this problem?
Chain lists respond as follows, requiring data and opening up a space to use the data. So some children's shoes ask why they don't do this in the order table? Answer: If you exploit a space with one piece of data, it creates a logical discontinuity and cannot be a linear table.
- We can know the location of the second element (memory address) when the first element is found, and the address of the third element when the second element is found, so that all elements can be found by traversal
Perhaps you are a little confused in the chart above, so let's take a look at the blogger's introduction:
In the chain table, there are two concepts: data field and pointer field. - Data field: Stores the data to be manipulated
- Pointer field: Address where the next element is stored
- A data field and a pointer field combine to form a node of a chain table. When we read a node, we know the data for that node and the address of the next node.
Data storage in single-chain tables
Features: Use an arbitrary set of storage units to store elements of a sequential table, which can be contiguous or discontinuous, meaning that these elements can exist anywhere in memory that is not occupied
Chain list storage structure:
🥇 Creating a single-linked list
When it comes to implementing this list, it's a small project, so let's create a test file, TestDemo.java tests the ability to create a chain list to implement a MyLinkedList.java file to implement the various functions of the chain table
- In MyLinkedList. In the Java file, first create a node class class Node, which contains the data element of one node and the address of the next node.
- ❤️ Code:
class Node {
public int val;
public Node next;//next address in node, empty by default
public Node(int val) {
this.val = val; //Initialize data in nodes
}
Then the chain table is defined randomly using some data, and each node is joined to create a single chain table method
❤️ Code:
public void createList() {
Node node1 = new Node(12);
Node node2 = new Node(3);
Node node3 = new Node(5);
Node node4 = new Node(2);
node1.next = node2;
//Connect each node
node2.next = node3;
node3.next = node4;
this.head = node1; //Define a header node that points to the first node
}
In TestDemo. In a Java file, create an object that references MyLinkedList. Functional methods in Java files.
🥇 Print Chain List of Single Chain Lists
Walk through the entire list until the end of the list, in the MyLinkedList.java file implementation print method
📄 Algorithmic ideas:
- If the list is empty, that is this.head == null, then the list is empty and returns directly
- Create a follower node, cur, pointing to the header node, traversing each node, cur = cur.next, point to the next node
- The end flag of the chain table following node is cur!= Null, if cur. Next!= Null can only traverse to the second-to-last node, because when the first-to-last node is null, it does not enter a circular print element.
❤️ Code:
public void print() {
if(this.head == null){
return ;
}
Node cur = this.head;
while(cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
Print the newly created single-chain list
In TestDemo. Calling print method in Java file
🥇 Calculated Chain List Length for Single Chain Lists
In MyLinkedList.java file implementation size method
Algorithmic ideas:
1. Create a follower node to traverse the entire chain
2. Create a counter that adds 1 to count for each node traversed
3. When the list is empty, that is, this,head == null, returns 0, proving that the length of the list is 0
❤️ Code:
//Get the length of the single-chain list
public int size() {
if(this.head == null){
System.out.println("Head node is empty");
return -1;
}
Node cur = this.head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
🥇 Add, delete, and change single-chain lists
Head Interpolation of Single Chain List
In MyLinkedList. Implement addFirst() function in Java file
📄 Algorithmic ideas:
1. Determine if this single-chain list is empty, that is, this.head == null, if equal, then the newly inserted node is the head node, that is, this. Head = node (address to insert node)
2. Insert a node at the head of the list, that is, assign the address of the head node of the list to the next, or node, of the newly inserted node.next = this.head, and then make the head node of the new chain table equal to the address of the newly inserted node node, that is, this.head = node.
look and say
❤️ Code:
//Head Interpolation
public void addFirst(int data) {
Node node = new Node(data);
//If the list itself is empty
if(this.head == null){
this.head = node;
}else{
node.next = this.head;
this.head = node;
}
}
End Interpolation of Single Chain List
In MyLinkedList. Implement addLast() function in Java file
📄 Algorithmic ideas:
1. Determine if this single-chain list is empty, that is, this.head == null, if equal, then the newly inserted node is the head node, that is, this. Head = node (address to insert node)
2. Create a new follower node cur to traverse the list of chains
2. Find the end node in the list and return it
3. Let cur.next = node, which places the inserted node at the end of the list
Look at the picture and talk:
❤️ Code:
//Tail interpolation
public void addLast(int data) {
Node node = new Node(data);
//If the chain header node is empty, it means that the list itself is empty
if(this.head == null){
this.head = node;
return;
}
Node cur = this.head;
//Find the last node of the list so that the next of the last node equals the address of the last insertion point
while(cur.next != null){
cur = cur.next;
}
cur.next = node;
}
Insert a node into the list anywhere
In MyLinkedList. Implement addIndex(int Index,int data) function in Java file
📄 Algorithmic ideas:
1. Determine if this single-chain list is empty, that is, this.head == null, if equal, then the newly inserted node is the head node, that is, this. Head = node (address to insert node)
2. Determine the validity of the subscript Index. If Index equals 0, then call the addFirst method. If Index equals size() - call the size method, then call the addLast method. If Index < 0 or Index > size(), then print the subscript is illegal and exit the return directly.
3. If Index is legal and you want to enter or leave a node, not at the end of the list, then you need to find the precursor node of the inserted node and return to it so that node.next = cur.next, and then let cur.next = node, you can connect the inserted node.
Look at the picture and talk:
❤️ Code:
//Find the previous location to insert the node
public Node find_cur(int index){
Node cur = this.head;
int count = 0;
while(count!=index-1){
count++;
cur = cur.next;
}
return cur;
}
//Insert anywhere, the first data node is subscript 0
public void addIndex(int index,int data){
//Judging the Legality of indxx
if(index < 0 || index >size()){
System.out.println("Illegal Subscript");
}
//Insert Head Node
if(index == 0){
addFirst(data);
return;
}
//Insert Tail Node
if(index == size()){
addLast(data);
return;
}
//Insert other nodes
Node node = new Node(data);
Node cur = find_cur(index);
node.next = cur.next;
cur.next = node;
}
Find an element in a single-chain list
In MyLinkedList. Implement contans(int data) function in Java file
📄 Algorithmic ideas:
1. Create a follower node, cur initialized to cur = this.head
2. If the list is empty, that is, this,head == null, return false to exit
3. If the element you are looking for is not found in the list, return false and exit
4. Walk through the list until cur == null, cur = cur for each loop. Next looks for the corresponding element cur.next == value, found returns true, found returns false.
Look at the picture and talk:
Node with a value value value at a time of deletion of a single-chain list
In MyLinkedList. Implement remove(int data) function in Java file
📄 Algorithmic ideas:
1. Determine if the list of chains is empty, if it is empty, there is no need to delete it
2. If it is not empty, traverse the list to find the node whose value you want to delete and return to its precursor node
3. The next of this precursor node equals the address of the next node, cur.next = cur.next.next skips the node to be deleted
Look at the picture and talk:
❤️ Code:
public Node seaarchPrevNode(int value){
Node cur = this.head;
while(cur!=null){
if(cur.next.val == value){
return cur;
}else{
cur = cur.next;
}
}
return null;
}
//Delete the node whose keyword is key for the first time
public void remove(int value) {
//If the list is empty, the header node is empty
if(this.head == null){
System.out.println("Chain list is empty, no deleted nodes");
}
//If the header node is the node to be deleted
if(this.head.val == value){
this.head = this.head.next;
}
//Find this node to delete first
Node cur = seaarchPrevNode(value); //Precursor Node
// Node del = cur.next;
// cur.next = del.next;
cur.next = cur.next.next;
}
Delete All Nodes in a Single Chain Table with value Value
In MyLinkedList. Implement removeAllkey(int data) function in Java file
📄 Algorithmic ideas:
1. Set the head node, the precursor node prev = this.head, follow node cur = this.head.next
2. Traverse the chain table, depending on the cur node, traverse nodes other than the header node, if the value of a node equals the value to be deleted, cur.value == value, let the precursor node prev.next = cur.next, skip the cur node, and cur = cur.next traverses backwards again when cur. When value is not equal to value, make the precursor node prev equal to cur. Finally, if the header node equals the precursor node, delete the header node, this.head = this.head.next
Look at the picture and talk:
❤️ Code
//Delete all nodes with key value
public void removeAllKey(int value) {
Node prev = this.head;
Node cur = this.head.next;
//Determine whether the node is to be deleted before
while(cur!=null){
if(cur.val == value){
prev.next = cur.next;
cur = cur.next;
}else{
prev = cur;
cur = cur.next;
}
}
//If the header node is deletable
if(this.head.val == value){
this.head = this.head.next;
}
}
Empty Chain List of Single Chain List
In MyLinkedList. Implement clear(int data) function in Java file
📄 Algorithmic ideas:
1. Create a node to save the head.next curNext = head.next
2. head.next set to null
3. Use head = curNext loop
4. Until the next node is traversed.
look and say
❤️ Code
//Empty Single Chain List
public void clear(){
while(head != null){
Node curNext = this.head.next;
this.head.next = null;
this.head = curNext;
}
}
Summary:
💯 TestDemo.java file:
public class TestDemo {
public static void main(String[] args) {
MyLinkList myLinkList = new MyLinkList();
myLinkList.createList(); //Create Chain List
myLinkList.addIndex(0,5);
System.out.print("Original Chain List");
myLinkList.print();
myLinkList.clear();
System.out.print("New Chain List");
myLinkList.print();
}
}
💯 MyLinkedList.java file
class Node {
public int val;
public Node next;//null
public Node(int val) {
this.val = val;
}
}
//linked list
public class MyLinkList {
public Node head;//Identify the header node of a single-chain table
/**
* Creating chains in an exhaustive way is certainly low. This is just for understanding
*/
public void createList() {
Node node1 = new Node(12);
Node node2 = new Node(3);
Node node3 = new Node(5);
Node node4 = new Node(2);
node1.next = node2;
node2.next = node3;
node3.next = node4;
this.head = node1;
}
/**
* Print Single Chain List
*/
public void print() {
Node cur = this.head;
while(cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
//Get the length of the single-chain list
public int size() {
if(this.head == null){
System.out.println("Head node is empty");
return -1;
}
Node cur = this.head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
//Find out if the key word is included or not in the single-chain list
public boolean contains(int value) {
if(this.head == null){
System.out.println("Chain list is empty");
return false;
}
Node cur = this.head;
while(cur!=null){
if(cur.val == value){
return true;
}
cur = cur.next;
}
return false;
}
//Head Interpolation
public void addFirst(int data) {
Node node = new Node(data);
//If the list itself is empty
if(this.head == null){
this.head = node;
}else{
node.next = this.head;
this.head = node;
}
}
//Tail interpolation
public void addLast(int data) {
Node node = new Node(data);
//If the chain header node is empty, it means that the list itself is empty
if(this.head == null){
this.head = node;
return;
}
Node cur = this.head;
//Find the last node of the list so that the next of the last node equals the address of the last insertion point
while(cur.next != null){
cur = cur.next;
}
cur.next = node;
}
//Find the previous location to insert the node
public Node find_cur(int index){
Node cur = this.head;
int count = 0;
while(count!=index-1){
count++;
cur = cur.next;
}
return cur;
}
//Insert anywhere, the first data node is subscript 0
public void addIndex(int index,int data){
//Judging the Legality of indxx
if(index < 0 || index >size()){
System.out.println("Illegal Subscript");
}
//Insert Head Node
if(index == 0){
addFirst(data);
return;
}
//Insert Tail Node
if(index == size()){
addLast(data);
return;
}
//Insert other nodes
Node node = new Node(data);
Node cur = find_cur(index);
node.next = cur.next;
cur.next = node;
}
public Node seaarchPrevNode(int value){
Node cur = this.head;
while(cur!=null){
if(cur.next.val == value){
return cur;
}else{
cur = cur.next;
}
}
return null;
}
//Delete the node whose keyword is key for the first time
public void remove(int value) {
//If the list is empty, the header node is empty
if(this.head == null){
System.out.println("Chain list is empty, no deleted nodes");
}
//If the header node is the node to be deleted
if(this.head.val == value){
this.head = this.head.next;
}
//Find this node to delete first
Node cur = seaarchPrevNode(value); //Precursor Node
// Node del = cur.next;
// cur.next = del.next;
cur.next = cur.next.next;
}
//Delete all nodes with key value
public void removeAllKey(int value) {
Node prev = this.head;
Node cur = this.head.next;
//Determine whether the node is to be deleted before
while(cur!=null){
if(cur.val == value){
prev.next = cur.next;
cur = cur.next;
}else{
prev = cur;
cur = cur.next;
}
}
//If the header node is deletable
if(this.head.val == value){
this.head = this.head.next;
}
}
//Empty Single Chain List
public void clear(){
while(head != null){
Node curNext = this.head.next;
this.head.next = null;
this.head = curNext;
}
}
}