C++ example of Linked List implementation

It is debatable if Linked lists are needed in C++, especially because STL can do a very good job for the same functionality for which Linked Lists are required. Nevertheless sometimes it maybe convenient to know linked lists.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include <iostream>
#include <string>
#include <istream>
#include <limits>

using namespace std;

class Node
{
public:
  Node() : next(NULL) {}; //default constructor
  Node(const string& s1) : info(s1), next(NULL) {};
  string info;
  Node* next;
};

Node* getNewNode()
{
  //Lets flush the input buffer first 
  istream& in(cin);
  in.ignore( numeric_limits<std::streamsize>::max(), '\n' );

  //Read the String from console
  cout<<"\tEnter a string: ";
  istreambuf_iterator<char> eos; // end-of-range iterator
  istreambuf_iterator<char> iit (cin.rdbuf()); // stdin iterator
  string s2;
  while (iit!=eos && *iit!='\n') s2+=*iit++;

  //Call the constructor with the input string
  Node* newNode = new Node(s2);

  return newNode;
}

int main()
{
  Node* head = NULL;
  bool contFlag = true;
  char c;

  while(contFlag)
  {
    cout<<"\n\n";
    cout<<"0. Quit"<<endl;
    cout<<"1. Traverse and Print"<<endl;
    cout<<"2. Insert node at the start"<<endl;
    cout<<"3. Insert node at the end"<<endl;
    cout<<"4. Insert after specified number of nodes"<<endl;
    cout<<"5. Remove node from the start"<<endl;
    cout<<"6. Remove node from the end"<<endl;
    cout<<"7. Remove node from a specified number"<<endl;

    cout<<"\nEnter your choice: ";
    cin>>c;

    switch(c)
    {
    case '0':
      contFlag = false;
      break;
    case '1':
      {
        Node* tempNode = head;
        int count = 0;
        while(tempNode)
        {
          cout<<"\tItem "<<count<<" = "<<tempNode->info<<endl;
          tempNode = tempNode->next;
          count++;
        }
      }
      break;
    case '2':
      {
        Node* newNode = getNewNode();
        newNode->next = head;
        head = newNode;
      }
      break;
    case '3':
      {
        Node* newNode = getNewNode();

        Node* endNode = head;
        if(endNode)
        {
          while(endNode->next)
            endNode = endNode->next;
          endNode->next = newNode;
        }
        else //In case its the first element
        {
          head = newNode;
        }
      }
      break;
    case '4':
      {
        Node* tempNode = head;
        if(tempNode)
        {
          unsigned num;
          cout<<"\tInsert after how many nodes? : ";
          cin>>num;
          Node* newNode = getNewNode();

          unsigned count = 1;
          //If less elements are present then insert at the end
          while(tempNode->next && (count < num))
          {
            tempNode = tempNode->next;
            count++;
          }
          newNode->next = tempNode->next;
          tempNode->next = newNode;
        }
        else
        {
          cout<<"\tNo nodes present yet"<<endl;
        }
      }
      break;
    case '5':
      {
        Node* firstNode = head;
        if(firstNode)
        {
          head = firstNode->next;
          delete firstNode;
        }
      }
      break;
    case '6':
      {
        Node* endNode = head;
        if(endNode) //Atleast one element
        {
          Node* endEndNode = endNode->next;
          if(endEndNode) //Atleast 2 elements
          {
            while(endEndNode->next)
            {
              endNode = endEndNode;
              endEndNode = endEndNode->next;
            }
            endNode->next = NULL;
            delete endEndNode;
          }
          else //Only one element
          {
            head = NULL;
            delete endNode;
          }
        }
      }
      break;
    case '7':
      {
        Node* tempNode = head;
        if(tempNode)
        {
          unsigned num;
          cout<<"\tRemove after how many nodes? : ";
          cin>>num;

          unsigned count = 1;
          //If less elements are present then return
          while(tempNode->next && (count < num))
          {
            tempNode = tempNode->next;
            count++;
          }
          if(count == num && tempNode->next && tempNode->next->next)
          {
            Node* nodeToRemove = tempNode->next;
            tempNode->next = nodeToRemove->next;
            delete nodeToRemove;
          }
        }
        else
        {
          cout<<"\tNo nodes present yet"<<endl;
        }
      }
      break;
    default:
      cout<<"Incorrect selection."<<endl;
    }
  }

  return 0;
}

The output is as follows:

You can try more combinations and if you have ideas for improvements please add in the comments section.

Few things to note:

1. This program is for reference and I have not accounted for memory leaks after pressing '0'.

2. For simplicity, getNewNode() is shown as a seperate function. In a real program, it may be better as a method of class Node

3. General Linked Lists use Struct's but in C++, Structs and Classes are nearly the same so its better to use Class.

4. In C++ there is rarely a need to use Linked Lists. Its better to use the STL which already have vectors, stacks, lists, etc.

5. There should be check for memory allocation and try catch blocks that have been ignored for simplicity

Reading string via cin and flushing input buffers

The following program shows three different approaches to read string via Cin. It also shows two different approaches for flushing input buffer.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//Program to read input string and to flush input buffer
#include<iostream>
#include<string>
#include <istream>
#include <limits>

using namespace std;

int main()
{
  string s1;
  cout << "\nAPPROACH 1" <<endl;
  cout << "Input a string : ";
  cin >> s1;
  cout << "Entered string = " <<s1.c_str()<<endl;

  //Lets flush the buffer from Approach 1 here
  istream& in(cin);
  in.ignore( numeric_limits<std::streamsize>::max(), '\n' );

  cout << "\nAPPROACH 2" <<endl;
  cout << "Input a string : ";
  istreambuf_iterator<char> eos;  // end-of-range iterator
  istreambuf_iterator<char> iit (cin.rdbuf()); // stdin iterator
  string s2; 
  while (iit!=eos && *iit!='\n') s2+=*iit++;
  cout << "Entered string = " << s2 << endl;

  //Another approach for flushing the input
  int ch;
  while ((ch = cin.get()) != '\n' && ch != EOF);

  cout << "\nAPPROACH 3" <<endl;
  cout << "Input a string : ";
  char buf[BUFSIZ];
  if (cin.getline(buf, sizeof(buf)))
  {
    cout << "Entered string = " << buf << endl;
  }

  cout << endl;
  return 0;
}

The output is as follows:



More information:

• FAQ: How Do I flush input buffer
• How do I flush input stream
• istreambuf_iterator

A Word and Letter Counter program example

This is a very simple program but people can sometime get lost in writing them. I have not taken into account all the different error scenarios but this program is quite robust.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//In this program we will count the total number of words, letters
//and the frequency of each letter. For simplicity we will end the
//program when enter is pressed.
#include<iostream>

using namespace std;

void wordLetterCounter(int &numWords, int &numLetters, int letterCount[]);

int main()
{
  int numWords = 0, numLetters = 0;
  int letterCount[26]={0}; //each letter count init to 0

  cout<<"\n\nPlease enter some words and finish by pressing enter : ";

  wordLetterCounter(numWords, numLetters, letterCount);

  cout<<"\n\nNumber of Words = "<<numWords<<"     Number of Letters = "<<numLetters<<endl;
  cout<<"\nFrequency of letters as follows:"<<endl;
  for(int i = 0; i < 26; i++)
  {
    cout<<char('a'+i)<<" = "<<letterCount[i]<<endl;
  }

  return 0;
}

void wordLetterCounter(int &numWords, int &numLetters, int letterCount[])
{
  char c;
  char lastLetter=' ';

  //Remember 'A'=65, 'Z'=90 and 'a'=97, 'z'=122 in Ascii
  while(cin.get(c))
  {
    //Converting upper to lower case to make it case insensitive
    if(c >= 'A' && c <= 'Z')
      c+=char(32);

    //Increase Letter Count and number of letters
    if(c >= 'a' && c <= 'z')
    {
      letterCount[c - 'a']++;
      numLetters++;
    }

    //Increase number of words
    if(c == ' ' && lastLetter != ' ')
      numWords++;

    //If new line then break;
    if(c == '\n')
    {
      //Before you exit, the numWords should be increased if there was atleast 1 letter
      if(numLetters)
        numWords++;
      break;
    }
    lastLetter = c;
  }
}

The Output is as follows. Note that there is a '.' and many spaces between Dr. and Spock but the wordcount is correct.