Data Structures Demystified (Demystified)

Although we discuss data as being stacked like a stack of dishes, it isn t physically stacked at all. Instead, data is linked together sequentially in a list, where the last data always appears at the front of the list. Data is removed only from the front of the list.

You create this sequential list by using a linked list. In Chapter 6, you learned that a linked list contains entries called nodes. A node has three subentries, data and two pointers. The data subentry is the data stored on the stack. Pointers point to the previous node and the next node (Figure 7-1). When you enter a new item on a linked list, you allocate the new node and then set the pointers to the previous and next nodes.

Figure 7-1: A node contains references to the previous node and the next node in the linked list and contains data that is associated with the current node.

A node is defined in C++ by using a structure, which is a user -defined data type. The following structure defines a 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 is called Node. The name of the structure creates an instance of the structure similar to the way a constructor creates an instance of a class and data type. Let s skip the second definition of the structure and look at the last three statements within the structure because statements at the beginning of the structure actually create an instance of the structure and don t define 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 the node is created, which is similar to the way constructors work in a class definition. You provide the current data to the structure when you create a new node. This data is assigned to data in the argument list, which is then assigned to the data element of the instance of the structure. The previous and next nodes are initialized to NULL , which indicates there are no other elements of the linked list. The NULL is replaced with a reference to a node when a new node is added to the linked list.

As you ll recall from Chapter 6, a LinkedList class is defined to create and manage a linked list. There are two data members and six function members defined in the LinkedList class. Data members are pointers to instances of the Node structure. The first pointer is called front , and it references the first node on the linked list. The second pointer is called back , and it references the last node on the linked list.

Both the front and back pointers are declared in the protected access specifier area of the class definition because the LinkedList class is inherited by the StackLinkedList class, which you ll learn about in the The StackLinkedList Class section of this chapter. The StackLinkedList class uses the front and back pointers.

The six member functions manipulate the linked list. These function members are the constructor, destructor, appendNode() , displayNodes() , displayReverseNodes() , and destroyNodes() . You learned about them in Chapter 6.

Here is the LinkedList class definition. You ll notice that this is nearly the same as the LinkedList class definition you saw in Chapter 6, but there is a subtle difference. In Chapter 6, the front and back pointers were declared in the private access specifier area of the class definition. Here they are defined in the protected access specifier area because the StackLinkedList class will use them:

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