Deleting by Index?

Question

I created a linked-list program using the following source code,

#include <iostream>

using namespace std;

struct Node
{
    int data;
    Node *next;
};

struct HeadNode
{
    int count;
    Node *headPtr;
};

class LinkedList
{
    public:
            LinkedList();
            ~LinkedList();

            void addToHead( int );
            bool removeFromHead();

//          bool addToTail ( int );
//          bool removeFromTail();

            void addNode ( int );
            bool deleteNode ( int );
            void deleteAllNodes();

            bool isEmpty();
            int getNoOfNodes();

            void displayAllNodes();

    private:
        int dataCmp ( int, int );
        void displayNode ( Node* );

        HeadNode head;
};

LinkedList::LinkedList()
{
    head.count = 0;
    head.headPtr = NULL;
    return;
}

LinkedList::~LinkedList()
{
    deleteAllNodes();
    return;
}

void LinkedList::addToHead ( int newData )
{
    Node *pNew = new Node;
    pNew -> data = newData;
    pNew -> next = head.headPtr;
    head.headPtr = pNew;
    head.count++;
}

bool LinkedList::removeFromHead()
{
    bool exit;
    Node *temp;

    if ( head.headPtr )
    {
        temp = head.headPtr;
        head.headPtr = head.headPtr -> next;
        delete temp;
        head.count--;
        exit = true;        // returns true if it's successful
    }
    else
        exit = false;       // returns false if it's not successful
    return exit;
}

/*
bool LinkedList::addToTail( int )
{

}
bool Linked::removeFromTail();
{

}
*/

void LinkedList::addNode ( int newData )
{
    Node *pNew = new Node,
         *pPre = NULL,
         *pCur = head.headPtr;
    pNew -> data = newData;

    while ( pCur && dataCmp( pNew -> data, pCur -> data ) >= 0 )
        {
            pPre = pCur;
            pCur = pCur -> next;
        }

    if ( pPre )
    {
        pNew -> next = pPre -> next;
        pPre -> next = pNew;
        head.count++;
    }
    else
    {
        pNew -> next = head.headPtr;
        head.headPtr = pNew;
        head.count++;
    }
}

bool LinkedList::deleteNode( int data )
{
    bool exit;
    Node *pPre = NULL,
         *pCur = head.headPtr;

    while ( pCur && dataCmp( pCur -> data, data ) < 0 )
    {
        pPre = pCur;
        pCur = pCur -> next;
    }

    if ( pCur && dataCmp( pCur -> data, data ) == 0 )
    {
        if ( pPre )
        {
            pPre -> next = pCur -> next;
            delete pCur;
            head.count--;
            exit = true; // return true if successful
        }
        else
        {
            head.headPtr = pCur -> next;
            delete pCur;
            head.count--;
            exit = true; // return true if successful
        }
    }
    else
        exit = false; // return false if unsuccessful

    return exit;
}

void LinkedList::deleteAllNodes()
{
    Node *temp;

    while ( head.headPtr )
    {
        temp = head.headPtr;
        head.headPtr = head.headPtr -> next;
        delete temp;
        head.count--;
    }

    return;
}

bool LinkedList::isEmpty()
{
    return head.count == 0;
}


int LinkedList::getNoOfNodes()
{
    return head.count;
}

void LinkedList::displayAllNodes()
{
    Node *pCur = head.headPtr;
    int nodeCount = 1;

    while ( pCur )
    {
        cout << "Node " << nodeCount << ": ";
        displayNode( pCur );
        cout << endl;

        nodeCount++;
        pCur = pCur -> next;
    }

    return;
}

int LinkedList::dataCmp( int value0, int value1 )
{
    int exit = 0;

    if ( value0 < value1 )
        exit = -1;
    else if ( value0 > value1 )
        exit = 1;

    return exit;
}

void LinkedList::displayNode( Node *node )
{
    cout << node -> data;
    return;
}

void printMenu()
{
    cout << "1. Add to head" << endl;
    cout << "2. Remove from head" << endl;
    cout << "3. Add node " << endl;
    cout << "4. Delete node" << endl;
    cout << "5. Delete all nodes" << endl;
    cout << "6. Is the list empty?" << endl;
    cout << "7. Get number of nodes" << endl;
    cout << "8. Display all nodes" << endl;
    cout << "9. Quit" << endl;
}

int getChoice()
{
    int choice;

    cout << "Select choice: ";
    cin >> choice;
    cin.clear();
    cin.ignore( 200, '\n' );
    return choice;
}

int getData()
{
    int data;

    cout << "Enter data: ";
    cin >> data;
    cin.clear();
    cin.ignore( 200, '\n' );

    return data;
}

void processChoice( int choice, LinkedList& list )
{
    int data;
    bool opStatus;

    switch ( choice )
    {
        case 1: data = getData();
            list.addToHead( data );
            break;
        case 2: if ( list.removeFromHead() )
            {
                cout << "Removed node from head" << endl;
            }
            else
                cerr << "List is empty" << endl;
            break;
        case 3: data = getData();
            list.addNode( data );
            cout << "Node " << data
                 << " added";
            cout << endl;
            break;
        case 4: if ( !list.isEmpty() )
            {
                data = getData();
                if ( list.deleteNode( data ) )
                {
                    cout << "Node " << data
                         << " deleted";
                    cout << endl;
                }
                else
                    cerr << "Node not found" << endl;
            }
            else
                cerr << "List is empty" << endl;
            break;
        case 5: list.deleteAllNodes();
            cout << "All nodes deleted" << endl;
            break;
        case 6: cout << ( list.isEmpty() ? 
                      "List is empty" : "List is not empty" );
            cout << endl;
            break;
        case 7: cout << "No. of nodes: "
                 << list.getNoOfNodes();
            cout << endl;
            break;
        case 8: list.displayAllNodes();
            break;
        default: cout << "Invalid choice" << endl;
    }

}

int main()
{
    LinkedList list;
    int choice;
    do
    {
        printMenu();
        choice = getChoice();

        if ( choice != 9 )
            processChoice( choice, list );

    } while ( choice != 9 );



    return 0;
}

Instead of deleting by Value, how can I modify my code so I can delete nodes by index?

Answer 1

It's the same method as delete by node except you need to also implement a indexing system.

For example....

increment the size and after every new value. Add a new index based off the size when you're adding.

You have to understand this will be an 0(n) operation. Versus a true link list O(1) but you're doing an O(n) operation with your deletes anyways so who cares !

just throwing this in here because it's some good info about indexing with link lists.

Link List info

Answer 2

add a deleteNodeByIndex function that takes in an index value, then you can perform the same delete operation except you delete the item at the given index instead of testing for value matches.

EDIT:

You're already deleting a node by its data, you are already half way there. The only difference is, instead of iterating through each item and testing the data value, you are just counting how many items you've iterated through until you reach the index you want to remove.

bool LinkedList::deleteNodeByIndex( int index )
{
    bool exit;
    Node *pPre = NULL,
         *pCur = head.headPtr;
    int currentIndex = 0;

    while ( pCur )
    {
        // Here we just loop until we reach our desired index.
        if (currentIndex == index)
        {
            break;
        }

        // Increment the current index and pCur to the next item.
        currentIndex++;
        pPre = pCur;
        pCur = pCur -> next;
    }

    // If pCur is still valid at this point, it means we broke at the
    // proper place and pCur should be at the proper index.
    if ( pCur )
    {
        if ( pPre )
        {
            pPre -> next = pCur -> next;
            delete pCur;
            head.count--;
            exit = true; // return true if successful
        }
        else
        {
            head.headPtr = pCur -> next;
            delete pCur;
            head.count--;
            exit = true; // return true if successful
        }
    }
    else
        exit = false; // return false if unsuccessful

    return exit;
}

Answer 3

how can I modify my code so I can delete nodes by index?

You can't know the index of a node in a linked list unless you count nodes starting from the head of the list. For example, if you want to delete the fifth node in a list, you need to start at the head and follow the next pointers until you get to the fourth node. Then you just need to save a pointer to the fifth node, set the next of the fourth node to the next of the fifth node, and then delete the fifth node using the pointer you just saved.