The Structure of a Linked List

Each entry in a linked list is called a node . Think of a node as an entry that has three subentries. One subentry contains the data, which may be one attribute or many attributes. Another points to the previous node, and the last points to the next node. When you enter a new item on a linked list, you allocate the new node and then set the pointers to previous and next nodes.

Programmers create a node in C++ by using either a structure or a class object; our example uses a structure. As you ll recall from your C++ programming course, a structure is a user -defined data type. The following example is a structure used to define a node. Figure 6-2 shows a node.

Figure 6-2: A node contains reference to the next node and the previous node in the linked list and contains data that is associated with the current node.

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

The structure might look a bit strange even if you are familiar with structures because this example uses a pointer to the structure itself as two of its attributes. We ll clear up any confusion by taking apart this example. The structure is called Node . The name of the structure creates an instance of the structure similar to how you use a constructor to create an instance of a class and data type.

For now, let s skip the second definition of the structure and turn our attention to the last three statements within the structure. The first statement declares an integer that stores the current data of the node. The next two statements declare pointers to the previous and next nodes in the linked list.

The constructor initializes elements of the node when an instance of the node is created. This works in a similar manner as a class constructor. As you ll see in LinkedList Constructor Destructor, you provide the current data to the structure when you create a new node. This data is assigned to data in the argument list. The value of data is then assigned to the data element of the instance of the structure. Also, reference to the previous and next nodes are initialized to NULL, which tells the program that there are no other elements of the linked list. The NULL is replaced with reference to a node when a new node is added to the linked list.

Single Linked List vs. Doubly Linked List

Programmers call this a doubly linked list or bidirectional (Figure 6-3) because each node contains reference to the previous and next node on the linked list. This enables the programmer to traverse the linked list in both directions by referencing the previous and next nodes. The node can be transformed into a single linked list (Figure 6-3) by only having one pointer in the structure that contains the address of the next node. Typically, a node in a single linked list references the next node and not the previous node, although nothing stops you from creating a backward reference by using only the previous node reference.

Figure 6-3: A doubly linked list contains next and previous members , and a single linked list contains only a next member.

The following example is nearly the same as the previous example except this is a single direction node. You ll notice that reference to the previous node is missing. This means a programmer can only move down the linked list and not in both directions.

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

The Linked List Class

Programmers use a LinkedList class to create and manage a linked list. C++ programmers define their own LinkedList class while Java programmers use the LinkedList collection class. You ll learn about the LinkedList collection class in the Linked Lists Using Java section of this chapter. For now, we ll focus on defining a LinkedList class in C++.

The LinkedList class definition consists of two data members and six function members, as shown in the example in this section. The two data members are pointers to instances of the Node structure that was defined previously in this chapter. The first pointer, front , references the first node on the linked list. The second pointer, back , references the last node on the linked list.

The six member functions manipulate the linked list. The first member function is the constructor of the LinkedList class and is called when an instance of the class is declared. Following the constructor is the destructor. When you return memory to the operating system by using the delete operator, the destructor is called. If you don t call the delete operator, then the destructor never gets called and the application causes a memory leak.

The appendNode() member function places a new node at the end of the linked list. The appendNode() requires an integer representing the current data of the node.

The next two member functions display the contents of the linked list. The displayNodes() method displays the linked list in natural order (first to last). The displayNodesReverse() member function displays the linked list in reverse order.

The last member function is destroyList() and is called to remove the instance of the LinkedList from memory.

The LinkedList class specification is defined in the header file, and the implementation is defined in the source file. We ll take a closer look at the implementation of these member functions in the next few sections of this chapter.

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

LinkedList Constructor Destructor

The LinkedList constructor is a member function that is called when an instance of the LinkedList is declared. The purpose of the constructor in the linked list example is to initialize the front and back pointers as shown in the following definition. Both the front and back pointers are assigned a NULL value, which is used by the appendNode() member function to determine if the linked list is empty. You ll see how this is done in the next section.

 LinkedList() {  front = NULL;  back = NULL; } 

The destructor is a member function called when the instance of the LinkedList class is deleted using the delete operator. In the example shown next, the destructor contains one statement that calls the destroyList() member function.

The destroyList() member function deletes the contents of the linked list but does not delete the linked list itself. That is, it removes all the nodes from the linked list. You ll see how this is done later in this chapter. The destroyList() also resets the front and back pointers to NULL, signifying the linked list is empty of nodes.  The destructor is responsible for deallocating all the memory that was allocated for the linked list. In this case, it would be all the nodes.

You might be wondering why we defined two member functions to perform basically the same task. We do so to enable the programmer to empty the linked list. This way you can reset the contents of the linked list without destroying the instance of the LinkedList class.

 ~LinkedList() {  destroyList(); } 

Appending a Node to a Linked List

The appendNode() member function places a new node at the end of the linked list. There are several steps that must be performed in order to add the node to the list. These are shown in the following definition of the appendNode() member function:

 void appendNode(int data) {  NODE* n = new NODE(data);  if(back == NULL)  {  back = n;  front = n;  }  else  {  back->next = n;  n->previous = back;  back = n;  } } 

The appendNode() member function requires one argument called data , which is the current data for the node. The argument is passed to the instance of the NODE structure. As you ll recall from previous sections of this chapter, the value passed to the NODE structure is assigned to the data element of the node.

The first statement in the appendNode() member function declares an instance of the NODE structure by using the new operator, which returns a pointer to the instance, which in turn is assigned to a pointer variable called n .

Once the new node is created, the appendNode() member function positions the new node in the linked list. First, it determines if the linked list is empty by comparing the back node to NULL. As you ll recall, the back node is assigned a NULL when an instance of the LinkedList class is declared and when the destroyList() member function removes all the nodes from the list.

If the linked list is empty, then the new node is assigned to both the back and front pointers. This means that the linked list contains one node after the appendNode() member function is called, which is the new node.

However, if there is at least one node on the linked list, then a little shifting of pointers must be performed. The else statement contains three statements that perform this shifting. The first statement assigns the pointer to the new node to the next pointer of the last node on the linked list. The back pointer is then assigned to the previous pointer of the new node. The new node is then assigned to the back pointer, making the new node the first node on the linked list.

This can be a little confusing, so take a look at Figure 6-4. Figure 6-4 shows nodes of the linked list. Assume that the linked list has two nodes before the new node is appended to the list. This is represented in the top block.

Figure 6-4: The appendNode() member function changes what nodes are pointed to in the linked list.

The first step assigns the memory address of the new node to the next member of the back node, which is shown in the second block of memory in Figure 6-4.

The second step assigns the memory address of the back node to the previous member of the new node. This links both nodes.

The third step replaces the memory address of the back node on the linked list with the memory address of the new node. This places the new node at the beginning of the linked list.

Display the Linked List

The displayNodes() member function displays each node of the linked list, beginning with the node at the front of the list and ending with the node at the back of the list. This is shown in the next example:

 void displayNodes() {  cout << "Nodes:";  NODE* temp = front;  while(temp != NULL)  {  cout << " " << temp->data;  temp = temp->next;  } } 

The displayNodes() member function begins by displaying the word Nodes: on the screen and then declares a pointer to a node, which is initialized with the node that appears at the back of the linked list.

Before attempting to display data assigned to the node, displayNodes() determines if there is a node at the back of the linked list. It does so by determining if the node pointed to by the temp pointer is NULL. If so, the linked list is empty and there is nothing to display. If not, the member function proceeds and displays the data assigned to the node located at the back of the linked list.

A space is then displayed, followed by the data assigned the node. The displayNode() member function uses the node s next member to assign the pointer to the next node to the temp pointer. The process continues by first determining if the node isn t NULL before displaying the data assigned to the node.

This process ends after the node at the back of the linked list is displayed because the next member of the node at the back of the list is NULL.

Transverse the Linked List

The displayNodesReverse() member function displays the contents of a linked list in reverse order, beginning with the node at the back of the linked list and continuing until the first node is displayed. The following example shows the how this is done:

 void displayNodesReverse() {  cout << "Nodes in reverse order:";  NODE* temp = back;  while(temp != NULL)  {  cout << " " << temp->data;  temp = temp->previous;  } } 

You ll notice that the displayNodesReverse() member function is nearly the same as the displayNodes() member function described in the previous section. However, there are two important differences between the two member functions. The displayNodesReverse() member function assigns the pointer to the node at the back of the list to the temp pointer, causing the node at the back of the linked list to be displayed first. The displayNodes() member function assigns the back pointer to the temp pointer, causing the last node on the linked list to be displayed.

The other difference between the displayNodesReverse() member function and the displayNodes() member function is that in the displayNodesReverse() member function the previous member of the node is used to determine the next node to display. This enables nodes to be displayed in reverse order. Figure 6-5 illustrates how the linked list is transversed.

Figure 6-5: The previous member of each node transverses the linked list.

Destroying a Linked List

The destroyList() member function removes nodes from the linked list without removing the linked list itself, as shown in the following example. Each node is declared dynamically using the new operator, as you learned previously in this chapter. This enables you to remove the node by using the delete operator.

 void destroyList() {  NODE* temp = back;  while(temp != NULL)  {  NODE* temp2 = temp;  temp = temp->previous;  delete temp2;  }  back = NULL;  front = NULL; } 

The destroyList() member function begins by declaring a temporary pointer that is assigned the pointer to the node that is at the back of the linked list. However, before the node is removed, the member function determines if there is a node at the back of the linked list by testing whether the temp pointer is NULL. If so, then the destroyList() member function assumes there are no nodes on the linked list. If the temp pointer isn t NULL, then the member function proceeds to delete the node.

Another temporary node is declared and assigned reference to the node pointed to by the temp node. This is done because the temp pointer is assigned the next node that is to be deleted from the linked list in the next statement.

The pointer to the next node is in the next member of the temp node, which is then assigned to the temp pointer. This means that temp2 points to the node at the back of the linked list and temp now points to the node that is immediately previous to the node at the back of the linked list. The node pointed to by temp2 is then deleted, as illustrated in Figure 6-6.

Figure 6-6: The destroyList() member function removes nodes beginning with the last node on the linked list and works its way to the beginning of the linked list.

This process continues until all the nodes are removed from the linked list. The final step in the destroyList() member function is to assign NULL values to the front and back of the linked list, which indicates that the linked list is empty of any nodes.