The list
“This is the 10th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.
About the author
- The authors introduce
๐ Blog home page: author’s home page ๐ Introduction: ๐ฅ, a high quality creator in JAVA field, ๐, a junior in college, participated in various provincial and national competitions and won a series of honors. ๐ pay attention to me: pay attention to my learning materials, document download all have, regularly update the article every day, inspirational to do a JAVA senior program ape ๐จ๐ป.
A linked list is a basic data structure, but as for the parts of the data structure, a few points need to be made:
- In the entire field of Java development, there is no book that really explains data structures, just look at DATA structures in C:
- Data structures are a part of all development, and it can be explained that mastery of data structures is entirely up to you later.
- The core of a data structure: reference data type operations.
Linked lists can actually be understood as genetic data or, in technical terms, as dynamic arrays of objects, which have the greatest merit of representing the concept of “many”, such as “multiple employees”. But one of the biggest problems with traditional object arrays is that they hold a fixed amount of data. Consider: What if you now want to expand the range of an object array?
Create a new array of objects, copy the original contents into the new array, and change the way the original array is referenced.
public class TestLinkDemo{
public static void main(String args[]){
Object ob[] = new Object [3]; }}Copy the codeHowever, in the actual development, we have to face a problem is that the array is a linear structure of fixed length. That is to say, although the above code can be satisfied with storing multiple contents, once we have insufficient content or too much content, it may lead to a waste of resources. The best way to solve this problem is to not define a fixed-length array and store as much data as possible.
The basic structure of linked lists
class Node{// Only the Node class can save data and set it at the same time
private Object data;// The actual data to save
private Node next;// Define the next node
public Node(Object data){
this.data = data;
}
public void setData(Object data){
this.data = data;
}
public Object getData(a){
return this.data;
}
public void setNext(Node next){
this.next = next;
}
public Node getNext(a){
return this.next; }}public class TestLinkDemo{
public static void main(String args[]){
//1. Encapsulate several nodes
Node root = new Node("The locomotive");
Node n1 = new Node("Carriage 1");
Node n2 = new Node("Cars 2");
Node n3 = new Node("Three carriages");
//2. Set the node relationship
root.setNext(n1);
n1.setNext(n2);
n2.setNext(n3);
//3. Output linked list
print(root);
}
public static void print(Node node){
if(node ! =null) {// Indicates that there is a node
System.out.println(node.getData());
print(node.getNext());// Continue to pull down}}}Copy the codeThroughout the implementation of the linked list, the Node class was used to save data and the next Node, but we found that the client needed to create the Node itself and configure the relationship. The so-called linked list requires a separate class, let’s say Link, which implements Node data storage and relationship processing.
List implementation structure description
Through the previous analysis, it can be found that the biggest class of linked list is Node, but the above procedures are by the user to match the Node relationship, but the matching work of these nodes should not be completed by the user, should be responsible for a program.
So specifically responsible for a few operations of the class, become a linked list class – Link, responsible for dealing with a few relationships, and the user does not need to care about the node, only care about Link processing operations.
Real development – Standard process
class Link{// Take charge of the list operation
// Define Node as an inner class that can only serve the Link class
private class Node{// Take charge of the relationship matching between data and nodes
private Object data;// The actual data to save
private Node next;// Define the next node
public Node(Object data){
this.data = data;
}
public void setData(Object data){
this.data = data;
}
public Object getData(a){
return this.data; }}// The following is the Link class
}
public class TestLinkDemo{
public static void main(String args[]){}}Copy the codeAdd list data — public void add(data)
Through the analysis of the above program, it can be found that, for the realization of the linked list, the Node class is the key to the whole operation, but first to study the problem of the previous program: Node is a separate class can be directly used by the user, but this class is directly used by the user, there is no significance, namely: This class is useful, but can’t be used by users. Let the Link class use it.
class Link{// Take charge of the list operation
// Define Node as an inner class that can only serve the Link class
private class Node{// Take charge of the relationship matching between data and nodes
private Object data;// The actual data to save
private Node next;// Define the next node
public Node(Object data){
this.data = data;
}
public void setData(Object data){
this.data = data;
}
public Object getData(a){
return this.data;
}
public void setNext(Node next){
this.next = next;
}
public Node getNext(a){
return this.next;
}
// First call: this = link. root
// Second call: this = link.root.next
// Third call: this = link.root.next
public void addNode(Node newNode){// Handle node relationships
if(this.next == null) {// The next node is empty
this.next = newNode;
}else{// The next node of the current node is not empty
this.next.addNode(newNode); }}public void nodePrint(a){
System.out.println(this.getData());
if (this.getNext()==null)
{
return;
}else{
this.getNext().nodePrint(); }}}/ / the following is the Link class -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
private Node root; // It belongs to the root node, without which data cannot be saved
// Add data
public void add(Object data){
if(data == null) {// Store null values manually
return ;// End the method call
}
// If you want to store data, you must encapsulate the data in the Node class
// If there is no encapsulation, the sequence of nodes cannot be determined
Node newNode = new Node(data);
if(this.root == null) {this.root = newNode;// Set the first node to the root node
}else{// The root node exists
this.root.addNode(newNode); }}// Output data
public void print(a){
if (this.root == null) {return;
}
System.out.println(this.root.getData());
if (this.root.getNext()==null) {return;
}
else{
this.root.getNext().nodePrint(); }}}public class TestLinkDemo1{
public static void main(String args[]){
Link link = new Link();
link.add("Hello");
link.add("World"); link.print(); }}Copy the codeAdd multiple data — public void addAll(Data array)
public void addAll(String date[]){
for(int x = 0; x<date.length; x++){this.add(date[x]); }}Copy the code2.5 Number of Statistics – public int size()
Defined in the Link class
private int count;// Count the number
Copy the codeAdd count++ on the last line of adding data
public void add(Object data){
if(data == null) {// Store null values manually
return ;// End the method call
}
// If you want to store data, you must encapsulate the data in the Node class
// If there is no encapsulation, the sequence of nodes cannot be determined
Node newNode = new Node(data);
if(this.root == null) {this.root = newNode;// Set the first node to the root node
}else{// The root node exists
this.root.addNode(newNode);
}
count++;
}
Copy the codePublic Object[] toArray()
For a data structure like a linked list, two operations are critical: delete and retrieve all data.
Define an array of manipulation pins in the Link class:
private int foot = 0;
Copy the codeTo store the data in an array, both the Link class and the Node class need to use it. Therefore, we can define the return array in the Link class, which must appear as an attribute. Only then can the Node class access the array and operate on it.
private Object [] retData ; // Return type
Copy the codeAdd toArray() to the Link class:
// List data is converted to an array of objects
public Object[] toArray(){
if(this.count == 0) {return null;
}
this.retData = new Object[this.count];
this.root.toArrayNode();
this.foot = 0;// set the following table to zero
return this.retData;
}
Copy the codeAdd toArrayNode() method to Node:
public void toArrayNode(a){
Link.this.retData[Link.this.foot++] = this.data;
if(this.next ! =null) {this.next.toArrayNode(); }}Copy the codeBut according to the above approach to development, each time to invoke toArray () method, which will be repeated for data traversal, if in the case of data is not modified, the practice of this kind of practice is a kind of inefficient, best method is to add a change token, if found increased data or delete, said to traverse the data.
List query data – Public Boolean Contains (Lookup object)
Now, if you want to check whether a certain data exists, the basic operation principle is as follows: search one by one. The specific objects to be searched should be handed over to Node. The premise is that there is data.
In the Link class, add query operations:
// Check whether the specified data in the linked list exists
public boolean contains(Object search){
if(search == null && this.root == null)
return false;
return this.root.containsNode(search);
}
Copy the codeIn the Node class, the specific query is completed. The query flow is as follows:
Determine whether the current node content is satisfied with the query content, if so, return ture;
If the current node does not meet the requirements, continue the query. If there are no subsequent nodes, false is returned.
public boolean containsNode(Object search){
if(search.equals(this.data))
return true;
else{
if(this.next ! =null) {// Check whether the next node is empty
return this.next.containsNode(search);
}
return false; }}Copy the codePublic Object get(int index)
Multiple nodes can hold data in a linked list, and it is now required to obtain data from the specified node. However, there is a small problem with this operation: if the index to retrieve the data exceeds the number of stores, it cannot be retrieved.
Add a get(int index) method to Link:
// Get data from index
public Object get(int index){
if(index >= this.count){
return null;
}
this.foot = 0;
return this.root.getNode(index);
}
Copy the codeAdd a getNdoe(int index) method to the Node class:
// First time this == link. root
// This == link.root.next
public Object getNode(int index){
if(Link.this.foot++ == index){
return this.data;
}else{
return this.next.getNode(index); }}Copy the codePublic void set(int index,Object newData) public void set(int index,Object newData)
To modify the data, you only need to replace the data.
Add a set(int index,Object newData) method to the Link class:
// Modify the specified index data
public void set(int index,Object newData){
if(index >= this.count){
return ;
}
this.foot = 0;
this.root.setNode(index,newData);
}
Copy the codeAdd a getNode(int index) method to the Node class:
public void setNode(int index, Object newData){
if(Link.this.foot ++ == index){// Same index
this.data = newData;
}else{
if(this.next ! =null) {this.next.setNode(index,newData); }}}Copy the codeDelete data – public void Remove (data)
For the content in the linked list, the previous completion is to add operations and query operations, but there will also be a delete operation from the linked list, but the deletion operation should be divided into two cases:
Case 1: The data to be deleted is not the root node, and the last next of the point to be deleted points to the next of the point to be deleted.
All processing should be handed over to Node.
Case 2: The deleted data is the root node, and the next node is saved as the secondary node.
If the root node is deleted, it means that the save of the root node in the Link needs to be changed, and this operation is mainly handled in the Link.
Add a remove(Object Data) method to Link
// Delete data
public void remove(Object data){
if(this.contains(data)){// If the data exists, the data is processed
if(this.root.data.equals(data)){// Determine whether the data to be deleted is root data
this.root = this.root.next;// The root node becomes the next node
}else{// Not the root node
this.root.next.removeNode(this.root,data);
}
this.count --; }}Copy the codeAdd a removeNode(Node Previous, Object data) method to the Node class:
// First: this = link. root.next, previous= link. root;
// second time: this = link.root.next. Next, previous= link.root.next;
public void removeNode(Node previous, Object data){
if(this.data.equals(data)){// The current node is the node to be deleted
previous.next = this.next;
}else{
this.next.removeNode(this,data); }}Copy the codeLink linked list class template
class Link{// Select * from the list
// Define Node as an inner class that can only serve the Link class
private class Node{// Take charge of the relationship matching between data and nodes
private Object data;// The actual data to save
private Node next;// Define the next node
public Node(Object data){
this.data = data;
}
public void setData(Object data){
this.data = data;
}
public Object getData(a){
return this.data;
}
public void setNext(Node next){
this.next = next;
}
public Node getNext(a){
return this.next;
}
// First call: this = link. root
// Second call: this = link.root.next
// Third call: this = link.root.next
public void addNode(Node newNode){// Handle node relationships
if(this.next == null) {// The next node is empty
this.next = newNode;
}else{// The next node of the current node is not empty
this.next.addNode(newNode); }}public void nodePrint(a){
System.out.println(this.getData());
if (this.getNext()==null)
{
return;
}else{
this.getNext().nodePrint(); }}public void toArrayNode(a){
Link.this.retData[Link.this.foot++] = this.data;
if(this.next ! =null) {this.next.toArrayNode(); }}public boolean containsNode(Object search){
if(search.equals(this.data))
return true;
else{
if(this.next ! =null) {// Check whether the next node is empty
return this.next.containsNode(search);
}
return false; }}// First time this == link. root
// This == link.root.next
public Object getNode(int index){
if(Link.this.foot++ == index){
return this.data;
}else{
return this.next.getNode(index); }}public void setNode(int index, Object newData){
if(Link.this.foot ++ == index){// Same index
this.data = newData;
}else{
if(this.next ! =null) {this.next.setNode(index,newData); }}}// First: this = link. root.next, previous= link. root;
// second time: this = link.root.next. Next, previous= link.root.next;
public void removeNode(Node previous, Object data){
if(this.data.equals(data)){// The current node is the node to be deleted
previous.next = this.next;
}else{
this.next.removeNode(this,data); }}}/ / the following is the Link class -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
private Object [] retData ; // Return type
private int foot = 0;// Operate the subscript
private int count;// Count the number
private Node root; // It belongs to the root node, without which data cannot be saved
// Add data
public void add(Object data){
if(data == null) {// Store null values manually
return ;// End the method call
}
// If you want to store data, you must encapsulate the data in the Node class
// If there is no encapsulation, the sequence of nodes cannot be determined
Node newNode = new Node(data);
if(this.root == null) {this.root = newNode;// Set the first node to the root node
}else{// The root node exists
this.root.addNode(newNode);
}
count++;
}
// Check whether the list is empty
public boolean isEmpty(a){
this.count=0;
return false;
}
// Add more data
public void addAll(String date[]){
for(int x = 0; x<date.length; x++){this.add(date[x]); }}public int size(a){
return this.count;
}
// Output data
public void print(a){
if (this.root == null) {return;
}
System.out.println(this.root.getData());
if (this.root.getNext()==null) {return;
}
else{
this.root.getNext().nodePrint(); }}// List data is converted to an array of objects
public Object[] toArray(){
if(this.count == 0) {return null;
}
this.retData = new Object[this.count];
this.root.toArrayNode();
this.foot = 0;// set the following table to zero
return this.retData;
}
// Check whether the specified data in the linked list exists
public boolean contains(Object search){
if(search == null && this.root == null)
return false;
return this.root.containsNode(search);
}
// Get data from index
public Object get(int index){
if(index >= this.count){
return null;
}
this.foot = 0;
return this.root.getNode(index);
}
// Modify the specified index data
public void set(int index,Object newData){
if(index >= this.count){
return ;
}
this.foot = 0;
this.root.setNode(index,newData);
}
// Delete data
public void remove(Object data){
if(this.contains(data)){// If the data exists, the data is processed
if(this.root.data.equals(data)){// Determine whether the data to be deleted is root data
this.root = this.root.next;// The root node becomes the next node
}else{// Not the root node
this.root.next.removeNode(this.root,data);
}
this.count --; }}}Copy the codeIntegrated case
The establishment of a pet shop, including sales of pets on shelves, shelves off, keyword query, requires the relationship between procedures, as long as there are three pet information: name, age, color.
Corresponding relationship: A pet store has a variety of pets, according to the table design should belong to the one-to-many relationship mapping, but now the problem, one side is a pet store, many are pets, but pets are divided into cats, dogs, pigs, donkeys, fish and so on.
1. Establish pet standards
interface Pet{// Define pet
public String getName(a);
public String getColor(a);
public int getAge(a);
}
Copy the code2. For pet stores, they only focus on the standard of pets, not the specific kind of pets
class PetShop{
private Link pets = new Link();// Create a linked list to store pet information
public void add(Pet pet){// Put the pet on the shelf
this.pets.add(pet);
}
public void delete(Pet pet){// Remove the pet
this.pets.delete(pet);
}
public Link getPets(a){ // Get all pets
return this.pets;
}
public Link search(String keyword){// Keyword search
Link result = new Link();
Object [] data = this.pets.toArray();
for(int i = 0; i < data.length ; i++){
Pet pet = (Pet) data[i];
if(pet.getName().contains(keyword) || pet.getColor().contains(keyword)){
result.add(pet); // The query result is met}}returnresult; }}Copy the code3. Define a pet dog
class Dog implements Pet{
private String name;
private String color;
private int age;
public String getName(a){
return this.name;
}
public String getColor(a){
return this.color;
}
public boolean equals(Object obj){
if(obj == null) {return false;
}
if(this == obj){
return false;
}
if(! (objinstanceof Dog)){
return false;
}
Dog pet = (Dog) obj;
return this.name.equals(pet.name) && this.color.equals(pet.color) && this.age.equals(pet.age);
}
public int getAge(a){
return this.age;
}
public Dog(String name, String color, int age){
this.name = name ;
this.color = color;
this.age = age;
}
public String toString(a){
return "Dog name =" + this.name +
"Color =" + this.color +
"ๅนด้พ = " +this.age; }}Copy the codeDefining a pet cat
class Cat implements Pet{
private String name;
private String color;
private int age;
public String getName(a){
return this.name;
}
public String getColor(a){
return this.color;
}
public boolean equals(Object obj){
if(obj == null) {return false;
}
if(this == obj){
return false;
}
if(! (objinstanceof Cat)){
return false;
}
Cat pet = (Cat) obj;
return this.name.equals(pet.name) && this.color.equals(pet.color) && this.age.equals(pet.age);
}
public int getAge(a){
return this.age;
}
public Cat(String name, String color, int age){
this.name = name ;
this.color = color;
this.age = age;
}
public String toString(a){
return "Cat name =" + this.name +
"Color =" + this.color +
"ๅนด้พ = " +this.age; }}Copy the code5. Test classes
public class Pets{
public static void main(String args[]){
PetShop ps = new PetShop();
ps.add(new Dog("Black"."Black".1));
ps.add(new Dog("Golden retriever"."Golden".2));
ps.add(new Dog(labrador."White".3));
ps.add(new Dog(samoye."White".2));
ps.add(new Cat(Garfield."Yellow".3));
ps.add(new Dog(Persian cat."Golden".4));
ps.delete(new Dog(samoye."White".2));
Link all = ps.search("White");
Object [] data = all.toArray();
for(int i = 0; i < data.length ; i++){ System.out.println(data[i]); }}}Copy the code6. Complete code
class Link{// Select * from the list
// Define Node as an inner class that can only serve the Link class
private class Node{// Take charge of the relationship matching between data and nodes
private Object data;// The actual data to save
private Node next;// Define the next node
public Node(Object data){
this.data = data;
}
public void setData(Object data){
this.data = data;
}
public Object getData(a){
return this.data;
}
public void setNext(Node next){
this.next = next;
}
public Node getNext(a){
return this.next;
}
// First call: this = link. root
// Second call: this = link.root.next
// Third call: this = link.root.next
public void addNode(Node newNode){// Handle node relationships
if(this.next == null) {// The next node is empty
this.next = newNode;
}else{// The next node of the current node is not empty
this.next.addNode(newNode); }}public void nodePrint(a){
System.out.println(this.getData());
if (this.getNext()==null)
{
return;
}else{
this.getNext().nodePrint(); }}public void toArrayNode(a){
Link.this.retData[Link.this.foot++] = this.data;
if(this.next ! =null) {this.next.toArrayNode(); }}public boolean containsNode(Object search){
if(search.equals(this.data))
return true;
else{
if(this.next ! =null) {// Check whether the next node is empty
return this.next.containsNode(search);
}
return false; }}// First time this == link. root
// This == link.root.next
public Object getNode(int index){
if(Link.this.foot++ == index){
return this.data;
}else{
return this.next.getNode(index); }}public void setNode(int index, Object newData){
if(Link.this.foot ++ == index){// Same index
this.data = newData;
}else{
if(this.next ! =null) {this.next.setNode(index,newData); }}}// First: this = link. root.next, previous= link. root;
// second time: this = link.root.next. Next, previous= link.root.next;
public void removeNode(Node previous, Object data){
if(this.data.equals(data)){// The current node is the node to be deleted
previous.next = this.next;
}else{
this.next.removeNode(this,data); }}}/ / the following is the Link class -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
private Object [] retData ; // Return type
private int foot = 0;// Operate the subscript
private int count;// Count the number
private Node root; // It belongs to the root node, without which data cannot be saved
// Add data
public void add(Object data){
if(data == null) {// Store null values manually
return ;// End the method call
}
// If you want to store data, you must encapsulate the data in the Node class
// If there is no encapsulation, the sequence of nodes cannot be determined
Node newNode = new Node(data);
if(this.root == null) {this.root = newNode;// Set the first node to the root node
}else{// The root node exists
this.root.addNode(newNode);
}
count++;
}
// Check whether the list is empty
public boolean isEmpty(a){
this.count=0;
return false;
}
// Add more data
public void addAll(String date[]){
for(int x = 0; x<date.length; x++){this.add(date[x]); }}public int size(a){
return this.count;
}
// Output data
public void print(a){
if (this.root == null) {return;
}
System.out.println(this.root.getData());
if (this.root.getNext()==null) {return;
}
else{
this.root.getNext().nodePrint(); }}// List data is converted to an array of objects
public Object[] toArray(){
if(this.count == 0) {return null;
}
this.retData = new Object[this.count];
this.root.toArrayNode();
this.foot = 0;// set the following table to zero
return this.retData;
}
// Check whether the specified data in the linked list exists
public boolean contains(Object search){
if(search == null && this.root == null)
return false;
return this.root.containsNode(search);
}
// Get data from index
public Object get(int index){
if(index >= this.count){
return null;
}
this.foot = 0;
return this.root.getNode(index);
}
// Modify the specified index data
public void set(int index,Object newData){
if(index >= this.count){
return ;
}
this.foot = 0;
this.root.setNode(index,newData);
}
// Delete data
public void remove(Object data){
if(this.contains(data)){// If the data exists, the data is processed
if(this.root.data.equals(data)){// Determine whether the data to be deleted is root data
this.root = this.root.next;// The root node becomes the next node
}else{// Not the root node
this.root.next.removeNode(this.root,data);
}
this.count --; }}}interface Pet{// Define pet
public String getName(a);
public String getColor(a);
public int getAge(a);
}
class PetShop{
private Link pets = new Link();// Create a linked list to store pet information
public void add(Pet pet){// Put the pet on the shelf
this.pets.add(pet);
}
public void delete(Pet pet){// Remove the pet
this.pets.remove(pet);
}
public Link getPets(a){ // Get all pets
return this.pets;
}
public Link search(String keyword){// Keyword search
Link result = new Link();
Object [] data = this.pets.toArray();
for(int i = 0; i < data.length ; i++){
Pet pet = (Pet) data[i];
if(pet.getName().contains(keyword) || pet.getColor().contains(keyword)){
result.add(pet); // The query result is met}}returnresult; }}class Dog implements Pet{
private String name;
private String color;
private int age;
public String getName(a){
return this.name;
}
public String getColor(a){
return this.color;
}
public boolean equals(Object obj){
if(obj == null) {return false;
}
if(this == obj){
return false;
}
if(! (objinstanceof Dog)){
return false;
}
Dog pet = (Dog) obj;
return this.name.equals(pet.name) && this.color.equals(pet.color) && this.age == pet.age;
}
public int getAge(a){
return this.age;
}
public Dog(String name, String color, int age){
this.name = name ;
this.color = color;
this.age = age;
}
public String toString(a){
return "Dog name =" + this.name +
", color =" + this.color +
", age = +this.age; }}class Cat implements Pet{
private String name;
private String color;
private int age;
public String getName(a){
return this.name;
}
public String getColor(a){
return this.color;
}
public boolean equals(Object obj){
if(obj == null) {return false;
}
if(this == obj){
return false;
}
if(! (objinstanceof Cat)){
return false;
}
Cat pet = (Cat) obj;
return this.name.equals(pet.name) && this.color.equals(pet.color) && this.age == pet.age;
}
public int getAge(a){
return this.age;
}
public Cat(String name, String color, int age){
this.name = name ;
this.color = color;
this.age = age;
}
public String toString(a){
return "Cat name =" + this.name +
", color =" + this.color +
", age = +this.age; }}public class Pets{
public static void main(String args[]){
PetShop ps = new PetShop();
ps.add(new Dog("Black"."Black".1));
ps.add(new Dog("Golden retriever"."Golden".2));
ps.add(new Dog(labrador."White".3));
ps.add(new Dog(samoye."White".2));
ps.add(new Cat(Garfield."Yellow".3));
ps.add(new Dog(Persian cat."Golden".4));
ps.delete(new Dog(samoye."White".2));
Link all = ps.search("White");
Object [] data = all.toArray();
for(int i = 0; i < data.length ; i++){ System.out.println(data[i]); }}}Copy the code