Of Stack

The establishment and basic operation of single linked list in C++

  • 2020-04-02 01:51:53
  • OfStack

To prepare data

Prepare variables and data structures to be used in linked list operations

The sample code is as follows: 


struct Data   //Data node type
{
 string key;  //The keyword
 string name;
 int age;
};
struct CLType  //Define the linked list structure
{
 Data nodeData;
 Data *nextNode;
};

Defines the Data type of the linked list Data element and the Data structure CLType of the linked list. The node's specific Data is stored in a structure called Data, and the nextNode pointer is used to point to the nextNode.

We can think that the linked list is the record of a class of students, where the key represents the student number, the name is the student's name, and the age is the age.

Additional nodes

To append a node is to add a node to the end of the list. The address part of the end node of the table originally saved the NULL address, so it needs to be set as the address of the new node (that is, the original end node of the table points to the new node), and then the address part of the new node is set as the NULL address, that is, the new node is the end of the table.

Since there is usually only one pointer head in a linked list, adding a node to the end requires checking from the beginning pointer head until the last node is found.

The operation steps of appending nodes are as follows:

(1) first allocate the memory address and save the new node.

(2) start from the head of the pointer to check one by one until the last node (that is, the end of the table) is found.

(3) set the address of the tail node of the table to the address of the new node.

(4) set the address part of the new node as NULL address, that is, the new node becomes the end of the table.

The sample code is as follows: 


CLType * CLAddEnd(CLType *head,Data nodeData)
{
 CLType *node,*htemp;
 if(!(node = new CLType))
 {
  cout<<" Memory allocation failed! "<<endl;  //Memory allocation failure
  return NULL; 
 }
 else
 {
  node->nodeData = nodeData;   //Save node data
  node->nextNode = NULL;     //Set the node pointer to null, that is, as the end of the table
  if(head == NULL)      //When the list is empty
  {
   head = node;
   return head;
  }
  htemp = head;
  while(htemp->nextNode != NULL)   //Find the end of the list
  {
   htemp = htemp->nextNode; 
  }
  htemp->nextNode = node;
  return head; 
 } 

}

The input parameter head is the pointer to the head of the list, and the input parameter nodeData is the data saved by the node. In the program, the new keyword is used to apply for dynamic space, and if internal allocation is successful, node will save a pointer to the memory region.

Then, the incoming nodeData is saved to the requested memory area and the pointer to the next node is set to NULL.

Insertion head

Inserting a header node is the process of adding a node at the beginning of a linked list.

The steps of inserting the header node are as follows:

(1) first allocate memory and save the newly added nodes.

(2) make new siblings point to the node pointed by the head pointer head

(3) then make the head pointer head to point to the new node

The sample code is as follows: 


CLType *CLAddFirst(CLType *head,Data nodeData)
{
 CLType *node;
 if(!(node = new CLType))
 {
  cout<<" Memory allocation failure "<<endl;
  return NULL;
 }
 else
 {
  node->nodeData = nodeData;  //Save node data
  node->nextNode = head;  //Pointer to the pointer to which the header pointer points
  head = node;   //The header pointer points to the new node
  return head;
 } 
}

The input parameter head is the pointer to the head of the linked table, and the input parameter nodeData is the data saved in the node. The program first USES the new keyword to apply for the memory space of a new save node, and if the application is successful, the node will save the pointer to the memory area.

Then, the incoming nodeData is saved to the requested memory region, and the new node points to the node pointed by the head pointer head, and then the head pointer head is set to point to the new node again.

To find the node

A node lookup is simply a search for the desired element in a linked list structure. For linked list structure, it can be generally divided into two types: searching by node number and querying by keyword.

Query by node number

That is, query the number of nodes in the linked list, the sample code is as follows: 


CLType *CLFindNodeNum(CLType *head,int k)
{
 CLType *htemp;
 int i = 1;
 htemp = head;      //Save the chain header pointer
          for(i = 1;i<k&&htemp;i++)     //Find that node
          {
        htemp = htemp->nextNode;
         }
          return htemp;      //Returns a pointer to the KTH node
}

The input parameter head is the pointer to the head of the list, and the input parameter k is the ordinal number of the node to be queried. Loop through the serial number many times to get the pointer to the node, and then return the pointer.

Query by keyword

That is, according to a keyword in the linked list to query, we take the query of the student's name as an example, the sample code is as follows: 


CLType *CLFindNodeKey(CLType *head,string name)
{
 CLType * htemp;
 htemp = head;       //Save the chain header pointer
 while(htemp)
 {
  if(htemp->nodeData.name == name) //When the node keyword is the same as the incoming keyword
  {
   return htemp;    //Returns a pointer to this node
  }
  htemp = htemp->nextNode; 
 }
 return NULL; 
}

The input parameter head is the head pointer of the linked table, and the input parameter name is the name of the student to be queried. If the name of a node is the same as the name of the node being queried, the pointer to that node is returned.

Insert the node

To insert a node is to add a node to the middle of the list.

The steps of inserting nodes are as follows:

(1) allocate memory space and save new nodes.

(2) find the logical position to insert, that is, find the node inserted after that node.

(3) modify the pointer of the insertion position node to point to the new node, and make the new node point to the node pointed to by the original insertion position.

The sample code is as follows: 


CLType *CLInsertNode(CLType *head,int k,Data nodeData)
{
 CLType *node,*nodetemp;
 if(!(node = new CLType))    //Apply for node
 {
  cout<<" Application memory failed "<<endl;
  return NULL; 
 } 
 else
 {
  node->nodeData = nodeData;  //Save the data in the node
  nodetemp=CLFindNodeNum(head,k-1);//Find the node before the insertion point by the node number lookup function
  if(nodetemp)
  {
   node->nextNode = nodetemp->nextNode;//The inserted node points to the next node of the key node
   nodetemp->nextNode = node;    //The key points to the insertion point
  } 
  else
  {
   cout<<" The correct insertion location was not found "<<endl;
   delete node;
  }
 } 
 return head;      //Return header pointer
}

The input parameter head is the pointer of the header of the linked list, and the input parameter findkey is the node keyword searched in the linked list. NodeData will be added after the node is found, and nodeData is the data of the newly added node. The program first USES the new request node space, then calls the CLFindNodeNum function to find the pointing node, and then executes the insert operation.

Delete nodes

Delete node is to delete a node in the linked list data, does not affect its position before and after the node.

The steps of deleting nodes are as follows:

(1) find the node to be deleted.

(2) make the previous node point to the next node of the current node.

(3) delete the node

Delete node can be determined by the node number to delete the node, of course, also can be determined by the node keyword to delete the node.

Let's take deleting nodes by keyword as an example. The sample code is as follows: 


int CLDeleteNode(CLType *head,string name)
{
 CLType *node,*htemp;    //Node is used to delete the previous node of a node
 htemp = head;
 node =  head;
 while(htemp)
 {
  if(htemp->nodeData.name == name)//Find the keyword and perform the delete operation
  {
   node->nextNode = htemp->nextNode;//Point the previous node to the next node of the current node
   delete htemp;     //Free the node's space (that is, delete the node)
   return 1; 
  }
  else
  {
   node = htemp;     //Point to the current node
   htemp = htemp->nextNode;  //Point to the next node
  } 
 } 
  return 0;        //Delete failed
}

Head is the pointer to the head of the linked table, and the input parameter name represents the name of the classmate to be deleted. In the program, through a loop, by the keyword in the entire list to find the node to be deleted. If the node is found to be deleted, then set the previous node (node pointer reference node) to point to the next node of the current node (node h pointer reference node), that is, logically delete the node, and then perform a delete operation on the node to free the memory space occupied by the node, that is, physically delete it.

Calculate the list length

To calculate the list length is to count the number of nodes in the list. It is convenient to calculate the list length in a sequential table, but the list length in a linked list needs to be obtained by traversing the list, because the list is not physically stored continuously.

The sample code is as follows: 


int CLLength(CLType *head)
{
 CLType *htemp;
 int Len = 0;
 htemp = head;
 while(htemp)       //Iterate through the entire array
 {
  Len++;        //Add up the number of nodes
  htemp = htemp->nextNode;    //We're dealing with the next node
 } 
 return Len;
}

The parameter head is the head pointer of the linked list. The program traverses the pointer through while. Len is the counter.

Show all the nodes

Go through all the nodes and output. 


void CLAllNode(CLType *head) 
{
 CLType *htemp;
 htemp = head;
 while(htemp)       //Iterate through the entire array
 {
  nodeData = htemp->nodeData;   //Get node data
  cout<<"key:"<<nodeData.key<<",name:"<<nodeData.name<<",age:"<<nodeData.age<<endl; 
  htemp = htemp->nextNode;    //We're dealing with the next node
 } 
}

Output node function, no return value, all defined as void. The value of its nodeData is obtained each time through a node of type CLType

A complete example of linked list operations

The code for the full example is long, so be patient...   :) 


#include<iostream>
#include<string>
using namespace std;
struct Data   //Data node type
{
 string key;  //The keyword
 string name;
 int age;
};
struct CLType          //Define the linked list structure
{
 Data nodeData;
 CLType *nextNode;
};
CLType * CLAddEnd(CLType *head,Data nodeData)
{
 CLType *node,*htemp;
 if(!(node = new CLType))
 {
  cout<<" Memory allocation failed! "<<endl;  //Memory allocation failure
  return NULL; 
 }
 else
 {
  node->nodeData = nodeData;         //Save node data
  node->nextNode = NULL;   //Set the node pointer to null, that is, as the end of the table
  if(head == NULL)   //When the list is empty
  {
   head = node;
   return head;
  }
  htemp = head;
  while(htemp->nextNode != NULL) //Find the end of the list
  {
   htemp = htemp->nextNode; 
  }
  htemp->nextNode = node;
  return head; 
 } 

}
CLType *CLAddFirst(CLType *head,Data nodeData)
{
 CLType *node;
 if(!(node = new CLType))
 {
  cout<<" Memory allocation failure "<<endl;
  return NULL;
 }
 else
 {
  node->nodeData = nodeData;  //Save node data
  node->nextNode = head;  //Pointer to the pointer to which the header pointer points
  head = node;   //The header pointer points to the new node
  return head;
 } 
} 
CLType *CLFindNodeNum(CLType *head,int k)
{
 CLType *htemp;
 int i = 1;
 htemp = head;    //Save the chain header pointer
    for(i = 1;i<k&&htemp;i++)   //Find that node
    {
     htemp = htemp->nextNode;
    }
    return htemp;     //Returns a pointer to the KTH node
} 
CLType *CLFindNodeName(CLType *head,string name)
{
 CLType * htemp;
 htemp = head;    //Save the chain header pointer
 while(htemp)
 {
  if(htemp->nodeData.name == name) //When the node keyword is the same as the incoming keyword
  {
   return htemp;  //Returns a pointer to this node
  }
  htemp = htemp->nextNode; 
 }
 return NULL; 
} 
CLType *CLInsertNode(CLType *head,int k,Data nodeData)
{
 CLType *node,*nodetemp;
 if(!(node = new CLType))   //Apply for node
 {
  cout<<" Application memory failed "<<endl;
  return NULL; 
 } 
 else
 {
  node->nodeData = nodeData;  //Save the data in the node
  nodetemp=CLFindNodeNum(head,k-1);    //Find the node before the insertion point by the node number lookup function
  if(nodetemp)
  {
   node->nextNode = nodetemp->nextNode;  //The inserted node points to the next node of the key node
   nodetemp->nextNode = node;    //The key points to the insertion point
  } 
  else
  {
   cout<<" The correct insertion location was not found "<<endl;
   delete node;
  }
 } 
 return head;      //Return header pointer
} 
int CLDeleteNode(CLType *head,string name)
{
 CLType *node,*htemp;    //Node is used to delete the previous node of a node
 htemp = head;
 node =  head;
 while(htemp)
 {
  if(htemp->nodeData.name == name)             //Find the keyword and perform the delete operation
  {
   node->nextNode = htemp->nextNode;  //Point the previous node to the next node of the current node
   delete htemp;   //Free the node's space (that is, delete the node)
   return 1; 
  }
  else
  {
   node = htemp;   //Point to the current node
   htemp = htemp->nextNode;  //Point to the next node
  } 
 } 
  return 0;     //Delete failed
} 
int CLLength(CLType *head)
{
 CLType *htemp;
 int Len = 0;
 htemp = head;
 while(htemp)     //Iterate through the entire array
 {
  Len++;     //Add up the number of nodes
  htemp = htemp->nextNode;    //We're dealing with the next node
 } 
 return Len;
} 
void CLAllNode(CLType *head) 
{
 CLType *htemp;
 Data nodeData; 
 htemp = head;
 cout<<" The length of the linked list is: "<<CLLength(head)<<endl;
 while(htemp)     //Iterate through the entire array
 {
  nodeData = htemp->nodeData;   //Get node data
  cout<<"key:"<<nodeData.key<<",name:"<<nodeData.name<<",age:"<<nodeData.age<<endl; 
  htemp = htemp->nextNode;    //We're dealing with the next node
 } 
}
int main()
{
 CLType *node,*head = NULL;
 Data nodeData;
 string name;
 int k;
 cout<<" Please enter the data in the linked list first, the format is: student number, name, age (age is 0 Stop input when) "<<endl;
 while(1)
 {
  cin>>nodeData.key>>nodeData.name>>nodeData.age;
  if(nodeData.age==0)break;
  head=CLAddEnd(head,nodeData);  //Add a node to the end of the list
 }
 CLAllNode(head);     //Show all the nodes
 //Demonstrates inserting data in the header
 cout<<" Please enter a node and insert it at the head of the list "<<endl;
 cin>>nodeData.key>>nodeData.name>>nodeData.age;
 head=CLAddFirst(head,nodeData);
 CLAllNode(head);
 //Demonstrates inserting a data in the middle
 cout<<" Please enter a node inserted in the linked list: "<<endl; 
 cin>>nodeData.key>>nodeData.name>>nodeData.age;
 cout<<" Please enter the position of the insertion point: ";
 cin>>k;
 head=CLInsertNode(head,k,nodeData);
 CLAllNode(head); 
 //Demonstrate querying data by sequence number
 cout<<" Please enter the serial number of a node queried by the node: ";
 cin>>k;
 node=CLFindNodeNum(head,k);
 cout<<" The node you are querying is: "<<endl;
 cout<<"key:"<<node->nodeData.key<<",name:"<<node->nodeData.name<<",age:"<<node->nodeData.age<<endl;
 //Demonstrates querying data by name
 cout<<" Please enter the name of a student by name: ";
 cin>>name;
 node=CLFindNodeName(head,name); 
 cout<<" The node you are querying is: "<<endl;
 cout<<"key:"<<node->nodeData.key<<",name:"<<node->nodeData.name<<",age:"<<node->nodeData.age<<endl;
 //Demonstrates deleting data information
 cout<<" Please enter the name of a classmate in the node, the system will delete his information: ";
 cin>>name;
 if(CLDeleteNode(head,name))cout<<" Data deleted successfully! "<<endl;
 CLAllNode(head);
 return 0; 
}

Example of program running result:

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201310/20130926205115265.png ">
Related articles: