The Linked List Queue

Conceptually, a linked list queue is the same as a queue built using an array. Both store data. Both place data at the front of the queue and remove data from the front of the queue. However, in an array queue, data is stored in an array element. In a linked list queue, data is stored in a node of a linked list. The linked list queue consists of three major components : the node, the LinkedList class definition, and the QueueLinkedList class definition. Collectively, they are assembled to organized data into a queue.

As you ll recall from Chapter 6, a node is created in C++ as a user -defined data type structure that contains three elements. These are the data and pointers to the previous node and the next node on the linked list (Figure 8-1). The next code snippet is the user-defined data type structure node that we used in Chapter 6. You ll be using the following user-defined data type structure in this chapter to create the linked list queue.

Figure 8-1: Each node points to the previous node and the next node.

The name of the user-defined data structure is called Node in this example and is used within the LinkedList class definition to declare instances of the node. The last three statements in the structure declare an integer that stores the current data and declares two pointers to reference the previous node and the next node on the linked list.

Each time a node is created, the user-defined structure is passed data for the node. Pointers to the previous node and to the next node are assigned NULL, which indicates there isn t a previous node or next node. NULL is replaced with reference to a node once the new node is added to the linked list.

 typedef struct Node {  struct Node(int data)  {  this->data = data;  previous = NULL;  next = NULL;  }  int data;  struct Node* previous;  struct Node* next; } NODE; 

The LinkedList class creates and manages the linked list. As you ll remember from Chapter 6, the LinkedList class identifies the node that is the front of the linked list and the node that is at the back of the linked list.

In addition, the LinkedList class defines member functions that manage the linked list. These are the same member functions described in Chapter 6, a constructor and destructor, appendNode() , displayNodes() , displayNodesReverse() , and destroyList() .Here is the LinkedList class definition that you ll use to create the linked list queue:

 class LinkedList {  protected:  NODE* front;  NODE* back;  public:  LinkedList();  ~LinkedList();  void appendNode(int);  void displayNodes();  void displayNodesReverse();  void destroyList(); }; 

Programmers usually place the node structure and the LinkedList class definition in the same header file, LinkedList.h . Placing the code needed to create a linked list in one file like this helps keep it organized. Programmers then use the preprocessor directive #include to include LinkedList.h in any program that uses a linked list.

The last component of the linked list queue is the QueueLinkedList class definition. The QueueLinkedList class inherits the LinkedList class and then defines member functions that are specifically designed to manage a queue.

You might wonder why you don t simply define one class that combines the LinkedList class and the QueueLinkedList class. Intuitively, this seems to be a good idea because everything needed to create a linked list queue is contained in one file. However, doing so repeats code, which is something programmers avoid if possible.

For example, definitions of a node and the LinkedList class would be located in two places. If you needed to upgrade either definition, you d need to remember all the places where they are defined in your code. A better approach is to place each definition in its own file (for example, LinkedList.h , QueueLinkedList.h ) so code won t be repeated.

Here is the definition of the QueueLinkedList class that you ll use to create a queue. Programmers save this definition in a file called QueueLinkedList.h . The QueueLinkedList class has five member functions:  a constructor and destructor, enqueue() , dequeue() , and isEmpty() .

 //QueueLinkedList.h #include "LinkedList.h" class QueueLinkedList : public LinkedList  {  public:  QueueLinkedList();  virtual ~QueueLinkedList();  void enqueue(int);  int dequeue();  bool isEmpty(); }; 

The constructor and destructor of the QueueLinkedList class are empty, as shown in the next code snippet. The constructor typically initializes data members of an instance of the class. In the case of the linked list queue, initialization is performed by the constructor of the LinkedList class, which is called before the constructor of the QueueLinkedList class. This means there isn t anything for the constructor of the QueueLinkedList class to do.

The destructor typically frees memory used by an instance of a class. The linked list used for the queue is removed by the destructor of the LinkedList class, which is also called before the destructor of the QueueLinkedList class. Therefore, there isn t anything for the destructor of the QueueLinkedList to do either.

 QueueLinkedList::QueueLinkedList() { } QueueLinkedList::~QueueLinkedList() { } 

Enqueue

The enqueue() member function of the QueueLinkedList class is called whenever a new node is placed on the queue. As you see from the function definition in the next code snippet, the enqueue() member function is sparse because it contains only one statement, which calls the appendNode() member function of the LinkedList class.

You don t have to include additional statements in the enqueue() member function because placing a node on the queue is the same process as appending a node to the linked list. Each new node is placed at the back of the linked list. Therefore, the appendNode() member function is all you need.

You may wonder why the new node is being placed on the back of the queue, but it s just because you re reusing the same code in the LinkedList class. The new node will be placed on the back of the queue like a line at the grocery store.  Nodes will be pulled off the front.

The enqueue() member function has one argument, which is the data that is being assigned to the new node. In this example, the node is used to store an integer. However, you can store any type of data in a node. In fact, the data can be a pointer to a set of data such as student information. To change this example from integer data to another type of data, you d need to change the data element in the Node structure to reflect the type of data you want to store in the node.

Data received by the enqueue() member function is passed to the appendNode() member function. Figure 8-2 illustrates how the appendNode() member function places a new node at the back of the linked list. At the top of the illustration is a linked list that contains two nodes. The appendNode() is then called to add a new node to the back of this linked list.

Figure 8-2: A new node is added to the queue at the back of the linked list.

The first step in this process assigns a reference to the new node to the next member of the front node. The front node is Node 2 and is assigned the reference Node 3 as the value of the next node in the linked list. This makes Node 3 the back of the linked list.

The second step assigns reference to Node 2 as the value of the previous node in Node 3. This means the program looks at the value of the previous node of Node 3 to know which node comes before Node 3 in the linked list.

The last step is to assign Node 3 as the new value of the back data member of the LinkedList class.

 void enqueue(int x) {  appendNode(x); } 

Dequeue

The dequeue() member function of the QueueLinkedList class removes a node from the front of the queue. Unfortunately, there aren t any member functions in the LinkedList class that remove a node from the back of the linked list. Therefore, the dequeue() member function must do the job.

The dequeue() function begins by determining if there are any nodes on the queue by calling the isEmpty() . The isEmpty() member function returns a Boolean true if the queue is empty, in which case the dequeue() returns a “1. A Boolean false is returned if there is at least one node on the queue.

Figure 8-3 shows how the dequeue() member function works. You ll notice there are three nodes on the queue, so the isEmpty() member function returns a Boolean false , causing the program to remove the front node from the queue.

Figure 8-3: Node 1 is removed from the back of the queue by the dequeue() member function.

The removal process starts by assigning the data of the node at the front of the queue to a variable called retVal . The value of the retVal is returned by the dequeue() member function in the last statement of the function.

Next, reference to the front node is assigned to the temp variable pointer. The delete operator later in the function uses the temp variable to remove the back node from memory.

Next, the function determines if there is another node on the queue by examining the value of the next member of the front node. If the value of the next member is NULL, there aren t any other nodes on the queue. In this case, the front and back members of the LinkedList class are set to NULL, indicating that the queue is empty.

However, if the next member of the front node is not NULL, the value of the next member of the front node is assigned to the front member of the LinkedList class. In this example, Node 2 is the next node following Node 1. Node 2 becomes the new front of the queue.

Notice that the previous member of Node 2 is set to Node 1. However, Node 1 no longer exists. Therefore, the previous member must be set to NULL because there isn t a previous node. Node 2 is the front of the queue.

The temp node is then deleted from memory. Remember that the temp node is a pointer that points to Node 1, and Node 1 no longer exists in memory. The final statement returns the value of the retVal variable, which is the data that was stored in Node 1.

 int dequeue() {  if(isEmpty())  {  return -1;  }  int retVal = front->data;  NODE* temp = front;  if(front->next == NULL)  {  back = NULL;  front = NULL;  }  else  {  front = front->next;  front->previous = NULL;  }  delete temp;  return retVal; } 

The isEmpty() member function determines if there are any nodes on the queue, which is called by the dequeue() member function. The isEmpty() member function examines the value of the front data member of the LinkedList class. If the value of front is NULL, then the queue is empty; otherwise , the queue has at least one node.

The isEmpty() member function returns a Boolean true if the value of front is NULL, otherwise a Boolean false is returned as shown in the definition of the isEmpty() here:

 bool isEmpty() {  if(front == NULL)  {  return true;  }  else  {  return false;  } }