Linked Lists Using C | Data Structures Demystified (Demystified)

Linked Lists Using C++

Now that you know the parts of a linked list and how to create and manipulate the linked list using a class, we ll put those parts together and create a real-world C++ application that uses a linked list.

Professional programmers organized a linked list C++ application into three files. The first file is the header file that contains the definition of the NODE structure and the LinkedList class definition. The second file is a source code file containing the implementation of member functions of the LinkedList class. The last file is the application file that contains code that creates and uses the LinkedList class.

Let s begin with the header file. LinkedList.h , shown in the code in this section, is the header file for the C++ linked list example. This file contains two components , the definition of the NODE structure and the definition of the LinkedList class, which programmers called a class specification.

You ll notice that both components were discussed in detail previously in this chapter. You ll also notice that the LinkedList class definition does not contain the implementation of member functions. Instead, it contains prototypes of member functions that are implemented in the source file. Keeping the specifications and implementation in separate header and source files is common practice. Parts of the program that use the class only care about the interface functions defined in the header file; they don t care about the implementation. This also allows you to precompile your source code into library modules so the users of this class need only the headers and modules.

 //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  {  private:  NODE* front;  NODE* back;  public:  LinkedList();  ~LinkedList();  void appendNode(int);  void displayNodes();  void displayNodesReverse();  void destroyList(); };

Definitions of member functions for the LinkedList class are contained in the LinkedList.cpp file as shown in the next code in this section. The file begins with a preprocessor statement that tells the preprocessor to reference the contents of the LinkedList.h file during preprocessing. The LinkedList.h file contains the LinkedList class definition and the NODE structure definition, both of which are required to resolve statements in the LinkedList.cpp that refer to the class and node.

Each member function definition is this example is practically the same definition as those discussed in the last several sections of this chapter. The only exception is that reference is made to the LinkedList class in the name of each member function definition. This associates each definition with the LinkedList class for the compiler.

 //LinkedList.cpp #include "LinkedList.h" LinkedList::LinkedList() {  front = NULL;  back = NULL; } LinkedList::~LinkedList() {  destroyList(); } void LinkedList::appendNode(int data) {  NODE* n = new NODE(data);  if(back == NULL)  {  back = n;  front = n;  }  else  {  back->next = n;  n->previous = back;  back = n;  } } void LinkedList::displayNodes() {  cout << "Nodes:";  NODE* temp = front;  while(temp != NULL)  {  cout << " " << temp->data;  temp = temp->next;  } } void LinkedList::displayNodesReverse() {  cout << "Nodes in reverse order:";  NODE* temp = back;  while(temp != NULL)  {  cout << " " << temp->data;  temp = temp->previous;  } } void LinkedList::destroyList() {  NODE* temp = back;  while(temp != NULL)  {  NODE* temp2 = temp;  temp = temp->previous;  delete temp2;  }  back = NULL;  front = NULL; }

The last file is the C++ application that uses the linked list. We call the file LinkedListDemo.cpp , which is shown next. It is amazing that the application itself is so small when compared to all the code used to define the NODE structure and the LinkedList class.

 //LinkedListDemo.cpp #include <iostream> using namespace std; void main(){  LinkedList * list = new LinkedList();  list->appendNode(10);  list->appendNode(20);  list->appendNode(30);  list->displayNodes();  list->displayNodesReverse();  delete list;}

The application begins by declaring an instance of the LinkedList class. As you recall from earlier in this chapter, the constructor initializes the front and back pointers.

The instance is declared using the new operator. The new operator returns a reference to the memory location of the instance. The same statement declares a pointer to reference a LinkedList . You call this pointer list and assign it the reference to the instance of the LinkedList class.

Next, the appendNode() member function is called three times. The appendNode() member function appends a new node at the back of the linked list and assigns the value passed to the appendNode() member function to the data member of the node.

The last two statements in this example display the data member of each node on the linked list. First, the displayNodes() member function is called to display nodes in natural order, starting with the front of the linked list and ending with the node at the back of the linked list.

Next, the displayNodesReverse() member function is called to do the same as the displayNodes() member function, except it starts with the back node and ends with the front node. The delete operator is then called to delete the instances of the LinkedList class from memory.

Here is the output of the code example: