removeNode(), removeNodeAt(), anddeleteRemove()

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.

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.

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.

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;
 }

Enhanced LinkedList Class Using C++

You’ve seen how enhancements to the LinkedList class individually work; now we’ll take a look at the entire application. I’ve divided the following application into three files: the demo.cpp file, the LinkedList.h file, and the LinkedList. file. All three files are shown in the following code listing. You can use the LinkedList.h file and the LinkedList.cpp file, along with the specific files for queues and stacks that you learned about in Chapter 7 and Chapter 8.

The demo.cpp file contains the C++ application that uses the enhanced LinkedList class to create and manipulate a linked list. The LinkedList.h file contains definitions of the node and of the LinkedList class. The LinkedList.cpp file contains the definitions of member functions of the LinkedList class. All three files are shown next.

The demo.cpp file is where all the action takes place. As you’ll see in the following example, the application begins by declaring an instance of the LinkedList class and then assigning the instance to a reference call list.

Next, the appendNode() function is called five times. The appendNode() function is an original member function of the LinkedList class and appends a new node to the linked list. The linked list shown at the top of Figure 9-4 is the linked list after the last appendNode() function is called.

Figure 9-4: The top is the linked list before the node is removed, the middle is after removeNodeAt(3) is called, and the bottom is after deleteNode(2) is called.

Once the linked list is created, the application calls the removeNodeAt(3) function to remove the node located at index 3. The middle linked list in Figure 9-4 shows the status of the linked list after the removeNodeAt(3) function executes.

The application then calls the findNode(20) function to locate the index of the node that contains 20 as its data element. Based on the linked list shown at the bottom of Figure 9-4, the findNode(20) function returns the index value 1.

The deleteNode(20) function is then called and removes the node from the linked list that has 20 as the value of its data element. The linked list shown at the bottom of Figure 9-4 illustrates the linked list after the deleteNode(20) function is called.

A new node is then inserted into the linked list by calling the insertNodeAt(1, 35) function. This function inserts a new node at index 1 in the linked list and assigns 35 to the data element of the node. Figure 9-5 is the linked list after the insertNodeAt(1, 35) function is called.

The peek(3) function is called to retrieve the value of the node in the third index position of the linked list. Based on the linked list shown in Figure 9-5, the peek(3) function returns 50 as the data value of the node in index position 3.

Figure 9-5: The linked list after the insertNodeAt(1) is called

The last function called is getSize(), which returns the size of the linked list. As seen in Figure 9-5, the linked list has four nodes; therefore, the getSize() function returns the value 4.

The last statement in the demo application uses the delete operator to remove the instance of the LinkedList class from memory.

//demo.cpp
 #include <iostream>
 using namespace std;
 void main(){
  LinkedList* list = new LinkedList();
  list->appendNode(10);
  list->appendNode(20);
  list->appendNode(30);
  list->appendNode(40);
  list->appendNode(50);
  list->removeNodeAt(3);
  int index = list->findNode(20);
  list->deleteNode(20);
  list->insertNodeAt(1, 35);
  int data = list->peek(3);
  int size = list->getSize();
  delete list;
 }
 //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();
 };
 //LinkedList.cpp
 #include "LinkedList.h"
 CLinkedList::CLinkedList()
 {
  front = NULL;
  back = NULL;
  size = 0;
 }
 
 CLinkedList::~CLinkedList()
 {
  destroyList();
 }
 
 void CLinkedList::appendNode(int data)
 {
  NODE* n = new NODE(data);
 
  if(back == NULL)
  {
  back = n;
  front = n;
  }
  else
  {
  back->next = n;
  n->previous = back;
  back = n;
  }
 
  size++;
 }
 
 void CLinkedList::displayNodes()
 {
  cout << "Elements: ";
  NODE* temp = front;
  while(temp != NULL)
  {
  cout << temp->data << " ";
  temp = temp->next;
  }
 
  cout << endl;
 
 }
 
 void CLinkedList::displayNodesReverse()
 {
  cout << "Elements: ";
  NODE* temp = back;
  while(temp != NULL)
  {
  cout << temp->data << " ";
  temp = temp->previous;
  }
 
  cout << endl;
 }
 
 void CLinkedList::destroyList()
 {
  NODE* temp = back;
  while(temp != NULL)
  {
  NODE* temp2 = temp;
  temp = temp->previous;
  delete temp2;
  }
 
  back = NULL;
  front = NULL;
 }
 
 void CLinkedList::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--;
 }
 
 void CLinkedList::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);
 }
 
 int CLinkedList::findNode(int data)
 {
  int index = 0;
  NODE* temp_node = front;
 
  while(temp_node != NULL)
  {
  if(temp_node->data == data)
  {
  // return the index of the node
  return index;
  }
  else
  {
  temp_node = temp_node->next;
  index++;
  }
  }
 
  return -1;
 }
 
 void CLinkedList::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;
  }
  }
 }
 
 void CLinkedList::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++;
 }
 
 int CLinkedList::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;
 
 }
 
 int CLinkedList::getSize()
 {
  return size;
 }

Оставьте свой комментарий !
Ваше имя: Комментарий: Оба поля являются обязательными  Автор   Комментарий к данной статье benjie this is very helpfull.. 2012-02-18 10:33:17 benjie this is very helpfull.. from philippines.. 2012-02-18 10:34:40 Яковлев Сергей >> from philippines.. Wow ! 2012-02-18 11:58:40