·       Linked Data Structures – A dynamically allocated group of nodes that each contain node pointers and are linked together.  The manner in which they are linked together defines the kind of data structure.

o      Node – A C++ Node is an object that is an instantiation of a C++ class that has one or more member variables that are pointers to nodes of the same type.

o      Some kinds of Data Structures

§       Singly Linked List – A data structure that starts from a head node and has nodes connected in a serial fashion to the last node in the list.

§       Doubly Linked List – A data structure that has nodes connected in a serial fashion that can go from head to last and last to head.  It uses two pointers to accomplish this.

§       Singly Circular Linked List – A data structure that is serially connected in a circular fashion and goes in one direction only, connecting the head node with the last node.

§       Doubly Circular Linked list – A data structure that is serially connected in a circular fashion that is bi-directional, connecting the head node with the last node.  It uses two pointers to accomplish this.

§       Binary Tree – A data structure that is structured like a tree in which nodes branch off to the left and right.  It uses two pointers to accomplish this.

§       Etc ...

o      For this class (C++ Programming), we will only use the Singly Linked List.  For the interested programmer, I recommend taking a course in Data Structures or Advanced C++ for more class work pertaining to data structures.

 

 

 

// Example

// Suppose we had the following class definition:

 

class Person

{

public:

   Person(string fName, string lName, int age, Person* next)

: _fname(fname), _lName(lName), _age(age), _next(next) {}

   ~Person() {}

 

      // Accessor and Mutator functions go here ...

 

private:

   string _fName;

   string _lName;

   int _age;

   Person *_next;

};

 

// We could have a linked list that looks like the following:

 

 

// Example

#include <iostream>

#include <string>

using namespace std;

 

class Person

{

public:

      Person(string fName, string lName, int age, Person* next)

            : _fName(fName), _lName(lName), _age(age), _next(next) {}

      ~Person() {}

 

      void setFirstName(string fName) { _fName = fName; }

      string getFirstName() const { return _fName; }

 

      void setLastName(string lName) { _lName = lName; }

      string getLastName() const { return _lName; }

 

      void setAge(int age) { _age = age; }

      int getAge() const { return _age; }

 

      void setNext(Person *next) { _next = next; }

      Person *getNext() const { return _next; }

 

private:

      string _fName;

      string _lName;

      int _age;

      Person *_next;

};

 

typedef Person* pPerson;

 

// Function for inserting node at head of list

void headInsert(pPerson& head, string fName, string lName, int age)

{

      head = new Person(fName, lName, age, head);

}

 

// Function for deleting node at head of list

void headDelete(pPerson& head)

{

      pPerson pDiscard = head;

 

      head = head->getNext();

      delete pDiscard;

}

 

// Function for inserting in the middle or end of the list

void insertNode(pPerson pPutAfterMe, string fName, string lName, int age)

{

   pPutAfterMe->setNext(new Person(fName, lName, age, pPutAfterMe->getNext()));

}

 

 

 

// Function for deleting in the middle or end of the list

void discardNode(pPerson pDiscardMe, pPerson& head)

{

      if(pDiscardMe == head)

      {

            headDelete(head);

            return;

      }

 

      pPerson pBeforeNode = head;

 

       while((pBeforeNode->getNext() != pDiscardMe) && (pBeforeNode->getNext() != NULL))

            pBeforeNode = pBeforeNode->getNext();

 

      if(pBeforeNode->getNext() == NULL)

      {

            cout << "\nCannot find node to discard\n";

            return;

      }

 

      pBeforeNode->setNext(pDiscardMe->getNext());

      delete pDiscardMe;

}

 

// Function to search through the linked list

pPerson search(pPerson found, string lName)

{

      if(found == NULL) // Empty list case

      {

              cout << "\n*****************************************************\n";

            cout << "Cannot find the person due to empty list.";

              cout << "\n*****************************************************\n";

            return NULL;

      }

 

       while((found->getLastName() != lName) && (found->getNext() != NULL))

            found = found->getNext();

 

      if(found->getLastName() == lName)

            return found;

      else

      {

              cout << "\n*****************************************************\n";

            cout << "Cannot find the person.";

              cout << "\n*****************************************************\n";

            return NULL;

      }

}

 

// Function to display one person of the linked list

void displayPerson(pPerson current)

{

       cout << "\n*****************************************************\n";

      if(current == NULL) // Empty list case

      {

            cout << "List is Empty.";

              cout << "\n*****************************************************\n";

            return;

      }

 

       cout << "\nName: " << current->getFirstName() << " " << current->getLastName()

               << endl << "Age:  " << current->getAge() << endl;

 

       cout << "\n*****************************************************\n";

}

 

// Function to display the current contents of the linked list

void displayList(pPerson current)

{

       cout << "\n*****************************************************\n";

      if(current == NULL) // Empty list case

      {

            cout << "List is Empty.";

              cout << "\n*****************************************************\n";

            return;

      }

 

      do

      {

            cout << "\nName: " << current->getFirstName() << " "

<< current->getLastName() << endl << "Age:  "

<< current->getAge() << endl;

 

            current = current->getNext();

      } while (current != NULL);

 

       cout << "\n*****************************************************\n";

}

 

void deleteList(pPerson& head)

{

      if(head == NULL)

            return;

 

      pPerson current = NULL;

 

      while(head != NULL)

      {

            current = head->getNext();

            delete head;

            head = current;

      }

}

 

// Test Driver Program

int main()

{

      pPerson start = NULL;

      pPerson temp  = NULL;

      displayList(start);

 

      // Create a linked list by adding to the head

      headInsert(start, "Neil", "Wendell", 27);

      headInsert(start, "Bob", "Phillips", 51);

      headInsert(start, "Mary", "Smith", 35);

      headInsert(start, "John", "Doe", 35);

      displayList(start);

 

      // Delete Mary Smith

      temp = search(start, "Smith");

      if(temp)

            discardNode(temp, start);

      displayList(start);

 

            // Add Fred Flintstone after Bob Phillips

      temp = search(start, "Phillips");

      if(temp)

            insertNode(temp, "Fred", "Flintstone", 39);

      displayList(start);

 

 

      // Delete the head node

      headDelete(start);

      displayList(start);

 

      deleteList(start);

      return 0;

}

 

// Output

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

// Here is an example that will allow the user to create the linked

// list within a session by performing add/delete/search/display

// operations.  To do this, I am replacing the main test driver with

// the following.  Note, the linked list does not get saved for the

// next session. That is, all information is destroyed when the

// program exits.

 

// Test Driver Program that allows user to create and manipulate

// the linked list in a session.

int main()

{

      pPerson start = NULL;

      pPerson temp  = NULL;

      string lastName, firstName;

      int age;

      int choice;

 

      do

      {

            do

            {

                  cout << "\n\nThe ABC People Registry\n\n";

                     cout << "1= Add, 2= Delete, 3= Find, 4= Display List, 5= Quit\n\n";

                  cout << "Choice> ";

                  cin >> choice;

            } while ((choice < 1) || (choice > 5));

 

            switch(choice)

            {

            case 1:

                  cout << "Last Name: ";

                  cin >> lastName;

                  cout << "First Name: ";

                  cin >> firstName;

                  cout << "Age: ";

                  cin >> age;

 

                  headInsert(start, firstName, lastName, age);

                  break;

 

            case 2:

                  cout << "Last Name: ";

                  cin >> lastName;

 

                  temp = search(start, lastName);

                  if(temp)

                        discardNode(temp, start);

                  break;

 

            case 3:

                  cout << "Last Name: ";

                  cin >> lastName;

 

                  temp = search(start, lastName);

                  if(temp)

                        displayPerson(temp);

                  break;

 

            case 4:

                  displayList(start);

                  break;

 

            case 5:

                  deleteList(start);

                  return 0;

                  break;

            }

      } while (1);

 

      deleteList(start);

      return 0;

}

 

// Sample Session Output

 

// Here is an example that will allow the user to create the linked

// list within a session by performing add/delete/search/display

// operations.  If data already exists in the data file, it will be

// a part of the initial linked list.  The user can add, delete, search

// and display the contents of the linked list.  Any changes made

// during the session are saved to the data file so that the changes

// will be reflected in the next session.  To do this, I am adding

// two new functions and replacing the main test driver with the

// following. 

 

#include <fstream>

 

int getLinkedList(pPerson& start)

{

      ifstream inFile;

      string lastName, firstName;

      int age;

 

 

      // Open the data file to read in the linked list

      inFile.open("people.txt");

      if(inFile.fail())

      {

            cout << "\nCould not open the data file for reading.\n";

            return 1;

      }

 

      // Read in the linked list from the data file

       while((inFile >> firstName) && (inFile >> lastName) && (inFile >> age))

            headInsert(start, firstName, lastName, age);

 

      inFile.close();

      return 0;

}

 

void saveLinkedList(pPerson current)

{

      ofstream outFile;

 

      // Open the data file to write out the linked list

      outFile.open("people.txt");

      if(outFile.fail())

      {

            cout << "\nCould not open the data file for writing.\n";

            return;

      }

 

      if(current == NULL)

      {

            cout << "\nWriting an empty list.\n";

            outFile.close();  // Makes an empty list

            return;

      }

 

      // Write the linked list to the data file

      while(current != NULL)

      {

            outFile << current->getFirstName() << " ";

            outFile << current->getLastName() << endl;

            outFile << current->getAge() << endl;

 

            current = current->getNext();

      }

 

      outFile.close();

      return;

}

 

 

 

int main()

{

      pPerson start = NULL;

      pPerson temp  = NULL;

      string lastName, firstName;

      int age;

      int choice;

 

      if(getLinkedList(start))

            return 1;

 

      do

      {

            do

            {

                  cout << "\n\nThe ABC People Registry\n\n";

                     cout << "1= Add, 2= Delete, 3= Find, 4= Display List, 5= Quit\n\n";

                  cout << "Choice> ";

                  cin >> choice;

            } while ((choice < 1) || (choice > 5));

 

            switch(choice)

            {

            case 1:

                  cout << "Last Name: ";

                  cin >> lastName;

                  cout << "First Name: ";

                  cin >> firstName;

                  cout << "Age: ";

                  cin >> age;

 

                  headInsert(start, firstName, lastName, age);

                  break;

 

            case 2:

                  cout << "Last Name: ";

                  cin >> lastName;

 

                  temp = search(start, lastName);

                  if(temp)

                        discardNode(temp, start);

                  break;

 

            case 3:

                  cout << "Last Name: ";

                  cin >> lastName;

 

                  temp = search(start, lastName);

                  if(temp)

                        displayPerson(temp);

                  break;

 

            case 4:

                  displayList(start);

                  break;

 

            case 5:

                  saveLinkedList(start);

                  deleteList(start);

                  return 0;

                  break;

            }

      } while (1);

 

      saveLinkedList(start);

      deleteList(start);

      return 0;

}

 

// Sample Session Output.  Note:  In this session, I already have

// created a data file that has people listed in it.  This will be

// shown the first time I use the display option.

 

// Sample Session #2.  Note that the changes made in the first session

// are reflected in the second session.  The list order is reversed

// because I am creating the linked list by using headInsert() which

// will create the linked list in the reverse order of how it was

// saved in the data file.