C++: Need help to write overload [] operator for a link list?

Question

I am looking for sample code which can impress an interviewer.

Answer 1

Following is the code

template< typename T >
T LinkedList<T>::operator[](int pos) {
    node<T> *current = new node<T>;
    int i = 0;

    for(current = first;current != NULL;current = current->link) {
        if(i == pos) {
            return current->data;
        }
        i++;
    }
}

/**
* This header file was designed to make creation and modification of linked lists easier.
**/

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
using std::cout;
using std::endl;

// Begin linklist namespace.
namespace linklist
{
    // Begin node structure.
    template< typename T >
    struct node {
        T data; // Contains data of specified type.
        node<T> *link; // Contains link to next node. NULL if this node is last in the list.
    };
    // End node structure.

    // Begin LinkedList class declaration.
    template< typename T >
    class LinkedList {
        public:
            LinkedList(); // Creates a new blank list.
            LinkedList(node<T> *start); // Creates a new list with a specified first node.
            ~LinkedList();

            // Delete functions.
            void destroy();
            void remove(int pos);

            // Functions for appending the list.
            void add(node<T> *next); // Adds a node to the list.
            void add(T nextData); // Adds a new node to the list.

            // Get and Set functions for the list.
            T get(int pos);
            void set(int pos, T newData);

            // Size-based functions.
            int length();
            bool isEmpty();

            // Position-based functions.
            T begin(); // Returns the data of the first node in the list.
            T end(); // Returns the data of the last node in the list.
            T operator[](int pos);

            // Sort function/s.
            void sort(bool asc);
            void swap(node<T> *i, node<T> *j);

            // Print functions.
            void printList();
            void printElem(int pos);
        private:
            node<T> *first; // The first node in the list.
            node<T> *last; // The last node in the list.
            int size; // Size of the list.
    };
    // End LinkedList class declaration.

    // Begin LinkedList class definitions.
    // Begin Constructors & Destructors
    template< typename T >
    LinkedList<T>::LinkedList() {
        first = NULL;
        last = NULL;
        size = 0;
    }
    template< typename T >
    LinkedList<T>::LinkedList(node<T> *start) {
        if(start->link != NULL) {
            first = start;
            node<T> *current = start;
            int count = 0;

            for(current = start;current != NULL;current = current->link) {
                count++;
                if(current->link == NULL) {
                    last = current;
                    size = count;
                }
            }
        } else {
            first = start;
            last = start;
            size = 1;
        }
    }
    template< typename T >
    LinkedList<T>::~LinkedList() {
        destroy();
    }
    // End Constructors & Destructors

    // Begin delete functions.
    template< typename T >
    void LinkedList<T>::destroy() {
        node<T> *current = new node<T>;

        while(first != NULL) {
            current = first;
            first = first->link;
            delete current;
        }

        last = NULL;

        size = 0;
    }
    template< typename T >
    void LinkedList<T>::remove(int pos) {
        if(pos > (size - 1)) {
            cout << "That position is out of bounds.";
        } else {
            node<T> *current = new node<T>;
            int i = 0;

            for(current = first;current != NULL;current = current->link) {
                if(i == (pos - 1)) {
                    node<T> *temp = current->link;
                    current->link = current->link->link;
                    delete temp;
                    size--;
                    break;
                }
                i++;
            }
        }
    }
    // End delete functions.

    // Begin list modifying functions.
    template< typename T >
    void LinkedList<T>::add(node<T> *next) {
        if(first == NULL) {
            first = next;
            last = next;
            last->link = NULL;
            size++;
        } else {
            last->link = next;
            last = next;
            last->link = NULL;
            size++;
        }
    }
    template< typename T >
    void LinkedList<T>::add(T nextData) {
        node<T> *next = new node<T>;
        next->data = nextData;
        next->link = NULL;

        if(first == NULL) {
            first = next;
            last = next;
            last->link = NULL;
            size++;
        } else {
            last->link = next;
            last = next;
            last->link = NULL;
            size++;
        }
    }
    // End list modifying functions.

    // Begin get/set functions.
    template< typename T >
    T LinkedList<T>::get(int pos) {
        if(pos > (size - 1)) {
            cout << "That position is out of bounds." << endl;
        } else {
            int i = 0;
            node<T> *current;

            for(current = first;current != NULL;current = current->link) {
                if(i == pos) {
                    return current->data;
                }
                i++;
            }
        }
        return 0;
    }
    template< typename T >
    void LinkedList<T>::set(int pos, T newData) {
        if(pos > (size - 1)) {
            cout << "That position is out of bounds." << endl;
        } else {
            int i = 0;
            node<T> *current;

            for(current = first;current != NULL;current = current->link) {
                if(i == pos) {
                    current->data = newData;
                }
                i++;
            }
        }
    }
    // End get/set functions.

    // Begin size-based functions.
    template< typename T >
    int LinkedList<T>::length() {
        return size;
    }
    template< typename T >
    bool LinkedList<T>::isEmpty() {
        return (first == NULL);
    }
    // End size-based functions.

    // Begin position-based functions.
    template< typename T >
    T LinkedList<T>::begin() {
        if(!isEmpty()) {
            return first->data;
        } else {
            return NULL;
        }
    }
    template< typename T >
    T LinkedList<T>::end() {
        if(!isEmpty()) {
            return last->data;
        } else {
            return NULL;
        }
    }
    template< typename T >
    T LinkedList<T>::operator[](int pos) {
        node<T> *current = new node<T>;
        int i = 0;

        for(current = first;current != NULL;current = current->link) {
            if(i == pos) {
                return current->data;
            }
            i++;
        }
    }
    // End position-based functions.

    // Begin sort function/s.
    template< typename T >
    void LinkedList<T>::sort(bool asc) {
        if(!isEmpty()) {
            node<T> *i;
            node<T> *j;

            for(i = first;i != NULL;i = i->link) {
                for(j = i->link;j != NULL;j = j->link) {
                    if(asc) {
                        if(j->data < i->data) {
                            swap(i, j);
                        }
                    } else {
                        if(j->data > i->data) {
                            swap(i,j);
                        }
                    }
                }
            }
        }
    }
    template< typename T >
    void LinkedList<T>::swap(node<T> *i, node<T> *j) {
        T tempData = i->data;
        i->data = j->data;
        j->data = tempData;
    }
    // End sort function/s.

    // Begin print functions.
    template< typename T >
    void LinkedList<T>::printList() {
        if(!isEmpty()) {
            node<T> *current;

            for(current = first;current != NULL;current = current->link) {
                cout << current->data << " ";
            }
            cout << endl;
        } else {
            cout << "The list is empty." << endl;
        }
    }
    template< typename T >
    void LinkedList<T>::printElem(int pos) {
        if(pos > (size - 1)) {
            cout << "That position is out of bounds." << endl;
        } else {
            int i = 0;
            node<T> *current;

            for(current = first;current != NULL;current = current->link) {
                if(i == pos) {
                    cout << current->data << endl;
                    break;
                }
                i++;
            }
        }
    }
    // End print functions.
    // End LinkedList class definitions.
}
// End linklist namespace.

#endif 

And here's the main.cpp:

/**
* This file is to test the LinkedList header file.
* Author - packetpirate
* Last Update - 05/18/2011  11:19 PM
**/

#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <ctime>
using std::rand;
using std::srand;
#include "LinkedList.h"
using linklist::LinkedList;
using linklist::node;

int main(int argc, char** argv) {
    srand((unsigned)time(0));

    LinkedList<int> *myList = new LinkedList<int>();

    int num = 0;

    for(int i = 0;i < 10;i++) {
        num = rand()%10 + 1;
        myList->add(num);
    }
    myList->printList();

    myList->sort(true);
    myList->printList();
    cout << "List Length: " << myList->length() << endl;

    myList->remove(4);
    myList->printList();
    cout << "List Length: " << myList->length() << endl;

    cout << myList[3] << endl;

    myList->destroy();
    myList->printList();
    cout << "List Length: " << myList->length() << endl;

    cin.sync();
    cout << "Press any key to continue...";
    cin.get();
    return 0;
}