Chapter 9: Stacks and Queues: Insert, Delete, Peek, Find


When you began learning about programming, you probably started with a bare-bones computer and then, once you learned how to program, you probably traded up for a system that had all the bells and whistles. Learning how to use the LinkedList class works in a similar way. The LinkedList class has basic functionality that is useful when working with stacks and queues. However, it lacks powerful features that are required to build industrial-strength applications. Now it is time to learn how to use those features and upgrade the LinkedList class. We ll teach you how to do that in this chapter by introducing insert, peek, delete, and find functionality to the LinkedList class and showing you how to use them in your stack and queue applications.

The Enhanced LinkedList Class

You might wonder why you need to enhance the LinkedList class that was defined in previously chapters. The simple answer is that you can increase the efficiency of the LinkedList class and make it easier to use if you increase the functionality of the class.

As you ll recall, the LinkedList class creates an instance of the structure Node that is defined in LinkedList.h . The Node structure has three elements: the data stored in the node, a reference to the next node, and the previous node on the linked list.

The LinkedList class that you used in previous chapters contains two data members and six member functions. The data members are references to the node that is at the front of the linked list and reference to the node that is at the back of the linked list.

The LinkedList class has member functions that append a node to the linked list and display data assigned to nodes in forward or reverse order, as well as a function to destroy the linked list. In addition, the LinkedList class has a constructor and destructor.

These data members and member functions are the barebones that are necessary for the LinkedList class to operate . Now you ll take a few steps forward and increase the functionality of the LinkedList class to make it more useful when working with a linked list application.

The first enhancement is to define a new data member called size . The size data member is an integer that represents the number of nodes that are in the linked list. (The index is used, but size determines whether the list is empty or you passed an invalid index.) It can be used any time the application needs to know the size of the linked list.

Next, you need to define additional member functions, the first of which is the removeNode() function. The removeNode() function enables you to easily remove a node from the linked list by specifying a reference to the node. The removeNode() function then removes the node and relinks the link list. This function is protected because it s only used internally. The user of this class would not know the pointers to the individual nodes. This is a convenient function to remove nodes.

Another useful function that you ll define is removeNodeAt() , which removes a node at a particular location in the linked list. The order in which nodes appear on the list is referred to as the index order . The position of a node on the linked list is referred to as the node s index . The index is passed to the removeNodeAt() function to specify the node that is to be removed from the linked list. The removeNodeAt() function then removes the node and relinks the linked list. The node on the front of the list is index 0; it then increments by one, moving toward the back of the list. The appendNode() function adds nodes to the back of the linked list, so you can think of this as a dynamic array moving from front to back.

Sometimes you may not know the index of the node that you want to remove from the linked list. In that case, you need to define another function that removes a node based on the data of the node, not the node s index. You can call this function deleteNode() . The deleteNode() differs from the removeNodeAt() function by the way the function identifies the node to remove from the linked list. The removeNodeAt() function locates the node to remove by using the node s index value. The deleteNode() locates the node to remove by using the value of the data of the node, which is passed to the deleteNode() function.

So far in this book, you ve accessed nodes on a linked list in sequential order. However, nodes are accessed randomly in some real-world applications. The next new function that you ll define for the LinkedList class enables you to access a specific node. This function is called findNode() , and it is used when you know the data contained in the node but you don t know the position of the node on the linked list. To locate the node, you provide the function with the data stored in the node. The findNode() function returns the index of the node.

The original LinkedList class is capable of appending a new node to the linked list. There will be situations when you ll want to insert a new mode somewhere in the middle of the linked list. To do this, you need to define the insertNodeAt() function. The insertNodeAt() function will require two parameters. The first parameter is the index of the node that will be moved in the linked list to make room for the new node. This becomes the index of the new node. The second parameter is the data that will be assigned to the new node. The insertNodeAt() function creates the new node and adjusts references within the linked list to link the new node to other nodes in the linked list.

Another major enhancement to the LinkedList class is to retrieve data that is stored at a specific node. Previously, two display functions were the only functions that you could use to see the data in the linked list (these function didn t return anything, they just count all the nodes). Both functions print out all the data stored in a linked list. Call the new function peek() . The peek() function requires that you pass it the index of the node that contains the data you want to retrieve. It then returns the data stored at that node.

The last enhancement that you ll make to the LinkedList class is to define a function that returns the number of nodes contained on the linked list. Call this function getSize() and use it whenever you need to determine the size of the linked list.

The following example is the revised LinkedList.h file that contains the definitions of the node structure and the enhanced LinkedList class. Notice that the size data member and the removeNode() member function are placed within the protected access specifier area of the class definition. This is because neither is directly used by the application. Instead, they are used by member functions of the LinkedList class and by member functions that inherit from the LinkedList class.

All the other member functions are placed in the public access specifier area of the LinkedList class definition and are available for direct use by the application. You ll learn how each new member function works in forthcoming sections of this chapter.

 //LinkedList.h typedef struct Node {  struct Node(int data)  {  this->data = data;  previous = NULL;  next = NULL;  }  int data;  struct Node* previous;  struct Node* next; } NODE; class LinkedList {  protected:  NODE* front;  NODE* back;  int size;  void removeNode(NODE* node);  public:  LinkedList();  virtual ~LinkedList();  void appendNode(int);  void displayNodes();  void displayNodesReverse();  void destroyList();  void removeNodeAt(int);  int findNode(int);  void deleteNode(int);  void insertNodeAt(int,int);  int peek(int);  int getSize();  }; 

removeNode(), removeNodeAt(), and  deleteRemove()

Removing a node from a linked list is a tricky operation. First, you must disconnect the node from the linked list. However, doing so breaks the link. There is no longer anything connecting the previous node and the next node because the node you removed was the link between them. This means that after removing a node, you must link together the previous node and the next node.

You can enhance the LinkedList class to include three member functions that remove a node from a linked list and then connect the previous node and next node to each other. These functions are removeNode() , removeNodeAt() , and deleteNode() .

The removeNode() function is passed a reference to the node that is to be removed from the linked list and is called by the removeNodeAt() function and the deleteNode() function. You cannot call the removeNode() function directly from the application because it is a protected member of the class.

The removeNodeAt() function uses the index of a node to locate the node that is to be removed. Once the node is found, its reference is passed to the removeNode() function. Similarly, the deleteNode() uses the data value of a node to locate the node. Once found, the deleteNode() retrieves the reference of the node, which is then passed to the removeNode() function.

For examples in this section, you ll use the linked list, shown in Figure 9-1, which has five nodes, NodeA through NodeE, respectively. Each node holds a position in the linked list, and each position is identified by an index value. Index values begin with zero and are shown above the name of each node in Figure 9-1.

click to expand
Figure 9-1: A linked list containing five nodes with each node identified by an index value

Begin by defining the removeNode() function, which is illustrated in the next code listing. Reference to the node being removed is passed to the removeNode() function. The removeNode() function must determine which of four processes to use to remove the node.

The first process is for the removeNode() to determine if the node is the only node on the linked list. It makes this determination by evaluating if the previous and the next node are NULL. If so, the node being deleted is the only node on the list. The node is then removed by assigning NULL to the back and front data members of the LinkedList class. As you ll recall from previous chapters, functions that retrieve data from a linked list always examine the front and back data members to determine if each is NULL. If so, then the function knows the linked list does not contain any nodes.

If the node is not the only node on the linked list, the removeNode() function must next determine if the node being removed is at the front of the linked list. It determines this by examining the previous member of the node. If the node is at the front of the linked list, then the previous member is NULL, and the removeNode() function takes the following steps to remove the node:

  1. The node pointed to by the deleted node s next member is assigned to the front data member of the LinkedList class. This makes it the front of the linked list.

  2. The previous member of the node that is now at the front of the linked list is assigned a NULL value, indicating there is no previous node because you removed its previous node. Here s how this is done. It might look a little confusing, but it s easy to understand if you take apart this statement:

     node->next->previous = NULL; 
  3. Say that you re removing Node D. The next node is Node E. Now substitute the numbers for the terms in this statement:

     Node D->Node E->previous = NULL; 

It s clear that the previous member belongs to Node E.

In the third process, the removeNode() function determines if the node being removed is at the back of the linked list. It does this by comparing the value of the next member of the node to NULL. If the next member is NULL, then the node being removed is the last node on the linked list.

The value of the previous member of the node is then assigned to the back member of the LinkedList class. This moves the previous node to the back of the list and in effect removes the node that is passed to the removeNode() function from the linked list.

The value of the next member of the previous node is then set to NULL, indicating there isn t another node because it is at the back of the list. The statement that performs this operator might seem confusing, but replacing references to node and previous with the node number should clear up any confusion. Here s the statement:

 node->previous->next = NULL; 

Say that you re removing NodeC. The previous node is NodeB. Now substitute the numbers for the terms in this statement:

 NodeC->NodeB->next = NULL; 

If the node being deleted isn t the only node on the linked list and isn t the node at the front or back of the linked list, the only other possibility is that the node is somewhere in the middle of the linked list.

The fourth process is to remove a node in the middle of the linked list and then link together the previous and next nodes. I ll illustrate this with an example because this operation can be confusing.

Say that you re removing NodeC. The previous node is NodeB and the next node is NodeD. First, link NodeB to NodeD by using the following statement:

 node->previous->next = node->next; 

Replace node, previous, and next with the name of the actual node to better understand this operation:

 NodeC->NodeB->next = NodeC->NodeD; 

Now that NodeB is linked to NodeD, you need to link NodeD to NodeB:

 node->next->previous = node->previous; 

Again, replace the node, shown next, and previous with names of nodes to see how this operation works:

 NodeC->NodeD->previous = NodeC->NodeB; 

Both NodeB and NodeD are linked to each other, and NodeC is removed from the linked list.

Although the node passed to the removeNode() function is no longer on the linked list, it remains in memory. Therefore, you need to remove the node from memory by calling delete . The final step is to adjust the value of the size member of the LinkedList class to reflect one less node on the linked list. You do this by decrementing the value of the size.

Figure 9-2 shows the linked list after the removeNode() function executes. Notice that NodeC is no longer on the linked list, and the index values are adjusted to reflect the new number of nodes on the linked list.

click to expand
Figure 9-2: The linked list after NodeC is removed
 void removeNode(NODE* node) {  if(node->previous == NULL && node->next == NULL)  {  back = NULL;  front = NULL;  }  else if(node->previous == NULL)  {  front = node->next;  node->next->previous = NULL;  }  else if(node->next == NULL)  {  back = node->previous;  node->previous->next = NULL;  }  else  {  node->previous->next = node->next;  node->next->previous = node->previous;  }  delete node;  size--; } 

removeNodeAt()

The removeNodeAt() function removes a node by using the node s index rather than the reference to the node in memory. Remember, the index is the position of the node on the linked list. Say you want to remove the third node of the linked list. You simply pass the index 2 to the removeNodeAt() function, and removeNode() performs the operation internally. You can t call removeNode() directly, partly because it s protected, but also because outside this class you don t have any knowledge of the actual pointer values. Remember that the index begins with zero. Therefore, you don t need to know the actual reference of the node you want removed. This is illustrated in the next code.

The first step in the removeNodeAt() function is to determine if the index is valid. To do that, the removeNodeAt() function determines if the index is less than zero or greater than one less than the size of the linked list. It uses the value of the size member of the LinkedList class to determine the size of the linked list. If either is true, then the index is invalid and no attempt is made to remove the node.

However, if both are false, the removeNodeAt() function begins the process of removing the node from the list. This process has two steps. First, the index locates a reference to the corresponding node, and second, the removeNode() function is called and passed the reference.

The removeNodeAt() function begins searching for reference to the node by declaring a temporary pointer to a node called temp_node and assigning it the reference to the node at the front of the linked list. Next, a for loop iterates through each node on the linked list until the node represented by the index is found. During each iteration, the temp_node is assigned the node referenced by the next member of the current temp_node.

When the index is reached, the value of the temp_node is reference to the node that corresponds to the index that is passed to the removeNodeAt() function. The removeNode() function is called and passed the temp_node.

 void removeNodeAt(int index) {  if(index < 0  index > size-1)  {  return;  }  NODE* temp_node = front;  for(int i=0; i<index; i++)  {  temp_node = temp_node->next;  }  removeNode(temp_node); } 

deleteNode()

The deleteNode() function uses data stored in a node to find and remove a corresponding node from the linked list. The deleteNode() function then searches the linked list to locate and remove the node.

Here s how this process works. First, a temporary node called temp_node is declared and assigned reference to the node that is located at the front of the linked list. If the temp_node is not NULL, then the list is not empty and the function determines if the data matches the data member of the current node.

If it does, the temp_node is passed to the removeNode() function, and the function is completed. If the data doesn t match, the next node is assigned to the temp_node, and the process continues until either the node containing the data is found or the deleteNode() function reaches the end of the linked list.

 void deleteNode(int data) {  NODE* temp_node = front;  while(temp_node != NULL)  {  if(temp_node->data == data)  {  removeNode(temp_node);  return;  }  else  {  temp_node = temp_node->next;  }  } } 

findNode()

Let s say that you need to access a particular node on a linked list, but you don t know the reference to the node or the position the node has on the linked list, although you do know the data is stored in the node. You can locate the node by calling the findNode() function.

The findNode() function requires that you pass it the data stored in the node. It then uses the data to locate the node and return to you the index of the node, as shown in the following example.

The process of finding a node begins when you declare an index variable that will eventually be assigned the index of the node if the node is found. A temporary node is also declared and assigned a reference to the node at the front of the linked list.

As long as the temp_node isn t NULL, the findNode() function iterates through the linked list. With each iteration, the data member of the current node is compared to the data passed as an argument to the findNode() function.

If both are equal, then the current value of the index is returned, which is the index of the node. If they are not equal, then the value of the next member of the current node is assigned to temp_node and the index is incremented. A “1 is returned if the data isn t found in the linked list because the value “1 can never be a valid return value.

 int findNode(int data) {  int index = 0;  NODE* temp_node = front;  while(temp_node != NULL)  {  if(temp_node->data == data)  {  return index;  }  else  {  temp_node = temp_node->next;  index++;  }  }  return -1; } int findNode(int data) 

insertNodeAt()

The insertNodeAt() function places a new node at a specific location in the linked list. Previously in this chapter, you learned that each position in a linked list is identified by an index. The first location has the index value of 0, the second location is index 1, and so on. You use the index to specify the location within the linked list where you want to insert the new node.

The insertNodeAt() function requires two arguments, the location where the node will be inserted within the linked list, and the data that will be stored in the node. The following example shows how the new node is placed within the linked list.

The first step is for the insertNodeAt() function to determine if the index passed to the function is valid. It does so by determining if the index is less than zero or greater than the size of the linked list (this information is contained in the size member of the LinkedList class). If the index is invalid, then the insertNodeAt() terminates and returns to the statement that called it. There s a subtle difference in the index checking here compared to removeNodeAt() . If the index were equal to size , this would append a node onto the linked list. The index is out of range by 1, but that s okay because you re going to add a new node onto the linked list, whereas removeNodeAt() needs a valid index so it checks ( size “1 ), which is the last node in the linked list.

Once the insertNodeAt() knows that that index is valid, it proceeds to create the new node and then insert the node in the linked list. This process begins by creating an instance of the node structure and assigning it the data passed to the function as an argument. The instance is then assigned to the new_node pointer.

Next, it must be determined if there are any nodes in the linked list. You do this by evaluating the value of the size member of the LinkedList class. If the value is zero, then the linked list is empty and the new node will become the only node in the list.

You place the new node in the list by assigning the new_node pointer to both the front member of the LinkedList class and to the back member of the LinkedList class. The previous and next members of the node are already set to NULL by default, so you don t have to do anything to the new node.

 front = new_node; back = new_node; 

If the linked list has one or more nodes, then the insertNodeAt() function determines if the new node is to be inserted into the first position in the linked list by evaluating the value of the index passed to the function. If the index value is zero, then the new node will become the first node on the linked list.

Here s how this is done. The new_node is assigned to the previous member of the node assigned to the front member of the LinkedList class. Next, the next member of new_node is assigned the node assigned to the front member of the LinkedList class. Finally, the new_node is assigned the front member.

 front->previous = new_node; new_node->next = front; front = new_node; 

If the new node isn t going to become the first node on the linked list, the insertNodeAt() function decides if the node will become the last node on the linked list by comparing the index to the size member of the LinkedList class. If these values are equal, then the new node is placed at the back of the linked list. Remember that index 0 is the front of the list and index ( size “1 ) is the back of the list.

Here s how this is done. The new_node is assigned to the next member of the node that is currently the back of the linked list. Next, the node at the back is assigned to the previous member of the new_node . Finally, the new_node is assigned to the back member of the LinkedList class.

 back->next = new_node; new_node->previous = back; back = new_node; 

At this point, if the new node hasn t been inserted in either the front or back of the linked list, then the insertNodeAt() function assumes that the new node is to be inserted into the middle of the linked list.

This process begins by declaring a pointer called temp and assigning it the node at the front of the linked list. Next, the function finds the node at the index. This node will be moved to the right. However, it s not set to the node previous, it s set to the index position and the node in that position is moved to the right. It does this by using a for loop. For each iteration, the node assigned to the next member of the temp node is assigned to the temp node. This sounds confusing, but will become clearer if you examine what is happening.

Say there are five nodes on the linked list, as shown in Figure 9-1. The front node is NodeA, and the initial value of temp is NodeA. Say you want to insert NodeN at index 2.

Before the first iteration, front = NodeE. During the first iteration, here s what happens:

 temp = temp->next temp = NodeA->NodeB temp = NodeB 

After the first iteration, temp is assigned NodeB and the value of i is 1, which is less than the value of the index, so another iteration executes. Here s what happens:

 temp = temp->next temp = NodeB->NodeC temp = NodeC 

The temp pointer now points to NodeC, and the value of i is 2, which is equal to the value of the index, so there are no additional iterations and the temp pointer points to NodeC.

Now that you re at the desired location within the linked list, it is time to switch pointers around to insert the new node into the list. Here s how to do it:

 new_node->next = temp; new_node->previous = temp->previous; temp->previous->next = new_node; temp->previous = new_node; 

Confused? If so, you re not alone, because what is happening isn t intuitive. I ll clarify the code by substituting nodes for pointers.

 new_node->next = NodeC; new_node->previous = NodeC->NodeB; NodeC->NodeB->next = new_node; NodeC->previous = new_node; 

Figure 9-3 shows the linked list after the new node is inserted into index 2 position of the list. I ve called the new node NodeN.

click to expand
Figure 9-3: A new node called NodeN is placed in index position 2 within the linked list.

The final step is to increment the size member of the LinkedList class to reflect the new node. Following is the complete definition of the insertNodeAt() function:

 void insertNodeAt(int index, int data) {  if(index < 0  index > size)  {  return;  }  NODE* new_node = new NODE(data);  if(size == 0)  {  front = new_node;  back = new_node;  }  else if(index == 0)  {  front->previous = new_node;  new_node->next = front;  front = new_node;  }  else if(index == size)  {  back->next = new_node;  new_node->previous = back;  back = new_node;  }  else  {  NODE* temp = front;    for(int i=0; i<index; i++)  {  temp = temp->next;  }  new_node->next = temp;  new_node->previous = temp->previous;  temp->previous->next = new_node;  temp->previous = new_node;  }  size++; } 

peek()

The peek() function retrieves data stored in a node specified by the index passed to the peek() function. The peek() function requires one argument, which is the index of the position within the linked list that contains the data you want to retrieve. The data is then returned by the peek() function. In the following example, you ll store and retrieve an integer, but you can also store and retrieve any kind of data by simply changing the data type in the node definition.

Let s take a closer look and see how the peek() function works. It begins by validating the index using the same validation procedures as discussed in the removeNodeAt() function section of this chapter, except peek() checks that the index is valid. If the index is invalid, then a zero is returned by the function.

If the index is valid, then a pointer called temp is declared and assigned the node that is at the front of the linked list. The peek() function then proceeds to step through the linked list, stopping at the node you re interested in. This search process is the same as in the insertNodeAt() function section.

When the peek() function exits the for loop, the temp pointer points to the node that contains the data that must be returned by peek() . You then point to the data member of the node in the return statement to return the data to the statement that called the peek() function.

Here is the complete definition of the peek() function:

 int peek(int index)  {  if(index < 0  index > size-1)  {  return 0;  }  NODE* temp = front;  for(int i=0; i<index; i++)  {  temp = temp->next;  }  return temp->data; } 

getSize()

The getSize() function retrieves the value of the size member of the LinkedList class. You ll notice that the getSize() function contains one statement that simply returns the value of the size member.

You might be wondering why you need the getSize() function since you could make the size member accessible to the application by placing it in the public access specifier of the LinkedList class.

As you ll recall from your programming classes, most data members of a class should be only accessible by a function member within the class or by a derived class. This way, you always control access to the data and thereby protect the data from inadvertent changes caused by the application. Allowing it to be changed externally by a user of this class could lead to errors.

 int getSize() {  return size; } 



Data Structures Demystified
Data Structures Demystified (Demystified)
ISBN: 0072253592
EAN: 2147483647
Year: 2006
Pages: 90

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net