Linked List Demo Program

[qingquan-li]

LList.h

#ifndef LLIST_H
#define LLIST_H

/**
 * Node structure for linked list
 */
template <class T>
struct node
{
    T info;
    node<T> *next;
};

/**
 * Linked list class
 */
template <class T>
class LList
{
private:
    // Pointer to first node
    node<T> *first;
    int length;
public:
    //Constructor
    LList();

    // Destructor
    ~LList();

    //Copy constructor
    LList ( const LList<T> & other);

    //Overload the assignment operator
    const LList<T> & operator= (const LList<T> & other);

    //Returns current length of list
    int getLength();

    // Returns true if list is empty, false otherwise
    bool isEmpty();

    // Inserts parameter item
    void insertItem(T item);

    //If list is not empty and parameter item is in the list,
    //removes item from the list and decrements length.
    //If list is empty or item is not in the list, prints error
    void deleteItem(T item);

    //Returns true if parameter item is in the list, false otherwise
    bool searchItem(T item);

    //Print all items in the list. Print message if list is empty.
    void printList();

    // function to copy a list
    void copy (const LList<T> & other);

    // Destroy list function
    void destroy();
};
#endif

LList.cpp

#include "LList.h"
#include <iostream>
using namespace std;

/**
 * Constructor
 */
template <class T>
LList<T> :: LList()
{
    length = 0;
    first = NULL;
}

/**
 * Destructor
 */
template <class T>
LList<T> :: ~LList()
{
    destroy();
}

/**
 * Copy constructor
 */
template <class T>
LList<T> :: LList ( const LList<T> & other)
{
    copy (other);
}

/**
 * Overload the assignment operator
 * @tparam T
 * @param other
 * @return LList<T>
 */
template <class T>
const LList<T> & LList<T> :: operator= (const LList<T> & other)
{
    if ( this != &other )
    {
        destroy ();
        copy (other);
    }
    return *this;
}

/**
 * Returns true if list is empty, false otherwise
 */
template <class T>
bool LList<T> :: isEmpty()
{
    return first == NULL;
}

/**
 * Inserts parameter item into the list in ascending order
 */
template <class T>
void LList<T> :: insertItem(T item)
{
    length++;

    node<T> * p = new node<T>;
    p->info = item;

    if ( first == NULL || item < first-> info )
    {
        p->next = first;
        first = p;
    }
    else
    {
        node<T> *r = NULL;
        node<T> *q = first;

        while ( q!= NULL && item > q->info )
        {
            r = q;
            q = q->next;
        }

        p->next = q;
        r->next = p;
    }
}

/**
 * If list is not empty and parameter item is in the list,
 * removes item from the list and decrements length.
 * If list is empty or item is not in the list, prints error
 */
template <class T>
void LList<T> :: deleteItem(T item)
{
    if ( first == NULL || item < first->info )
        cout<<"\nLIST EMPTY OR ITEM NOT IN THE LIST\n";
    else
    {
        node<T> *p = first;

        // item is contained in the first node
        if ( item == first->info )
        {
            first = first->next;
            delete p;
            length--;
        }
        // item is contained in some other node
        else
        {
            node<T> *q = p;
            p = p->next;

            while ( p != NULL && item > p->info )
            {
                q = p;
                p = p->next;
            }

            if ( p == NULL || item < p->info )
                cout<<"\nITEM NOT IN THE LIST\n";
            else
            {
                q->next = p->next;
                delete p;
                length--;
            }
        }
    }
}

/**
 * Destroy the list
 */
template <class T>
void LList<T> :: destroy()
{
    node<T> *p;

    while ( first != NULL )
    {
        p = first;
        first = first->next;
        delete p;
    }

    length = 0;
}

/**
 * function to copy a list
 */
template <class T>
void LList<T> :: copy ( const LList<T> & other )
{
    length = other.length;
    if ( other.first == NULL )
        first = NULL;
    else
    {
        first = new node<T>;
        first->info = other.first->info;
        node<T> *p = other.first->next;
        node<T> *q = first;

        while ( p != NULL )
        {
            q->next = new node<T>;
            q = q->next;
            q->info = p->info;
            p = p->next;
        }
        q->next = NULL;
    }
}

/**
 * Returns current length of list
 */
template <class T>
int LList<T> :: getLength()
{
    return length;
}

/**
 * Returns true if parameter item is in the list, false otherwise
 */
template <class T>
bool LList<T> :: searchItem(T item)
{
    node<T> *p = first;

    while ( p != NULL && p->info <= item )
    {
        if ( p->info == item )
            return true;
        p = p->next;
    }

    return false;
}

/**
 * Print all items in the list. Print message if list is empty.
 */
template <class T>
void LList<T> :: printList()
{
    if ( first == NULL)
        cout<<"\nEMPTY LIST\n";
    else
    {
        cout<<"\nLIST: ";

        node<T> *p = first;
        while ( p != NULL)
        {
            cout<<p->info<<"  ";
            p = p->next;
        }
    }
}

main.cpp

#include "LList.cpp"

using namespace std;

//******************** function prototypes ********************//
int printMenu();
void insertListItem ( LList<int> & );
void deleteListItem ( LList<int> & );
void searchListItem ( LList<int>  );

//******************** main function ********************//
int main()
{
    // Create an empty list of integers
    LList<int> l;
    int choice;

    cout <<"\nOperations allowed on the unsorted list of integers are below."
         <<"\nPlease enter the number of your choice and press return.\n\n";

    choice = printMenu();

    while ( choice != 6 )
    {

        switch ( choice )
        {

            case 1 : insertListItem( l );
                break;

            case 2 : deleteListItem ( l );
                break;

            case 3 : l.printList();
                break;

            case 4 : searchListItem ( l );
                break;

            case 5 : cout<<"\nThe list contains "<<l.getLength()
                         << " items\n\n";
                break;

            default :cout<<"\nNumber is not correct. Please look at "
                         <<"choices and reenter\n\n";
                break;
        }

        choice = printMenu();
    }

    LList<int> l2;

    l2 = l;

    cout<<"\nPrinting a new list with the same values as the old list \n";

    l2.printList();

    cout<<"\nProgram terminated\n\n";

    return 0;
}

//******************** functions implementation ********************//

/**
 * Prints the menu and returns the user's choice
 */
int printMenu ()
{
    int c;

    cout<<"\n1: Add an item to the list.";
    cout<<"\n2: Delete an item from the list.";
    cout<<"\n3: Print the list.";
    cout<<"\n4: Search the list for a given item";
    cout<<"\n5: Return the number of items in the list";
    cout<<"\n6: Quit.\n\n";
    cin>>c;

    return c;
}

/**
 * Inserts a number into the list
 */
void insertListItem ( LList<int> &l )
{
    int num;

    cout<<"\nEnter the number to insert : ";
    cin>>num;
    l.insertItem(num);
    cout<<"\nThe number has been inserted\n\n";


}

/**
 * Deletes a number from the list
 */
void deleteListItem ( LList<int> &l )
{
    int num;

    cout<<"\nEnter the number to delete : ";
    cin>>num;

    if ( l.searchItem (num))
    {
        l.deleteItem (num);
        cout<<"\nThe number has been deleted\n\n";
    }
    else  cout<<"\nThe number is NOT in the list\n\n";


}

/**
 * Searches for a number in the list
 */
void searchListItem ( LList<int> l )
{
    int num;

    cout<<"\nEnter the number to search for : ";
    cin>>num;

    if ( l.searchItem (num))

        cout<<"\nThe number is in the list\n\n";

    else cout<<"\nThe number is NOT in the list\n\n";
}

Compile and Run

$ g++ -std=c++11 LList.cpp main.cpp -o LinkedListDemo
$ ./LinkedListDemo

Operations allowed on the unsorted list of integers are below.
Please enter the number of your choice and press return.


1: Add an item to the list.
2: Delete an item from the list.
3: Print the list.
4: Search the list for a given item
5: Return the number of items in the list
6: Quit.

1

Enter the number to insert : 20

The number has been inserted


1: Add an item to the list.
2: Delete an item from the list.
3: Print the list.
4: Search the list for a given item
5: Return the number of items in the list
6: Quit.

1

Enter the number to insert : 10

The number has been inserted


1: Add an item to the list.
2: Delete an item from the list.
3: Print the list.
4: Search the list for a given item
5: Return the number of items in the list
6: Quit.

3

LIST: 10  20  

...