Linked List: issues finding index of node to remove at [index not incrementing correctly]

Question

I am creating a linked list program, and one of the functions is supposed to remove a node at a given index.

My idea is to locate the node one before the node at the index I wish to remove, then set it's next pointer to the ->next pointer of the node I wish to remove, therefore "skipping" it and removing it from the list.

At the moment my for loop does not seem to be working. After the the for loop has run, the value of temp->data is always the data of the second node in the list.

for example, with the list of nodes

15 14 13 12 11 10 (10 being the start of the list)

if I want to remove at the index of 4.

temp->data returns 11, instead of 14.

Here is the code I have:

NODE * removeAt(NODE * pList, int index)
{
    NODE * temp = pList; 

    for (int i = 0; i < index - 1; i++)
    {
        temp = temp->next;
    }

    NODE * next = temp->next->next;
    temp->next = next;

    return temp;
}

Any help is appreciated!

Unrelated to your (current) problem, but there are a few fatal flaws in your code, all of them with missing null-pointer checks. What if the user supplies an index out of bounds? What if there is no `temp->next`? — Some programmer dude, Apr 04 '18 at 05:56
Are you positive that 10 is that start of the list and not 15? Also this could blow up: `NODE * next = temp->next->next;` if you are removing the last node. (Or indeed inside the loop could blow up if index > list size) — AaronHolland, Apr 04 '18 at 05:56
@AaronHolland you are correct. I had the head/tail of the list reversed, I should have realized. And yes I have to add an exception case. Thanks for your help! — , Apr 04 '18 at 05:59
Helpful trick for removing an item from a singly linked list: https://stackoverflow.com/questions/12914917/using-pointers-to-remove-item-from-singly-linked-list [This linked answer](https://stackoverflow.com/a/48846270/4581301) goes into very good detail. — user4581301, Apr 04 '18 at 06:01

score 0 · Accepted Answer · answered Apr 04 '18 at 06:45

First of all, you have an indexing convention problem. If you say you expect the-next-after-removed to be 14, that means you want to remove the number 13. But it is a number 3 if you start from 0.

You say "My idea is to locate the node one before the node at the index I wish to remove". Imagine you want to remove the start node (data=10), will your idea work here? There is no any "one before" node in this case. Same about the last. There would be no the-next-after-removed.

Also, you need to check for null pointers everywhere. And you must destroy the removed node to avoid memory leaks.

And you need to check how do you insert nodes. Is the start one really 10?

I would improve your code like this:

#include <iostream>

#include <vector>

using namespace std;

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

NODE * removeAt(NODE * pList, int index)
{
    if (!pList)
        return nullptr;

    NODE * temp = pList;
    if (index == 0)
    {
        temp = pList->next;
        std::cout << "removing " << pList->data << endl;
        delete pList;
        return temp;
    }

        // after this loop temp points to the node before
    for (int i = 0; i < index -2; i++)
    {
        temp = temp->next;
        if (!temp || !temp->next)   // to guarantee both the-node-before and the-node-to-remove exist
            return nullptr;
    }

    NODE * next = temp->next->next;
    std::cout << "removing " << temp->next->data << endl;
    delete temp->next;
    temp->next = next;

    return next;
}

int main()
{
    std::vector<int> vec {15, 14, 13, 12, 11, 10};

    NODE * root = nullptr;
    for (const int v : vec)
    {
        std::cout << v << ' ' << endl;
        NODE * cur = new NODE;
        cur->data = v;
        cur->next = root;
        root = cur;
    }

    removeAt(root, 4);

    return 0;
}

Hi thanks for your answer. Most of your changes look good, (thank you for reminding me to look for memory leaks) but I see one issue. In the _if (index == 0)_ case, this removes the node from index 1, not 0. Any ideas as to why? — , Apr 04 '18 at 07:17
What I see in my tests, it removes index 0, which has data=10. — Ivan Strelets, Apr 04 '18 at 07:32
Then it returns a pointer to 11. Just try to call removeAt(root, 0); — Ivan Strelets, Apr 04 '18 at 07:33

Linked List: issues finding index of node to remove at [index not incrementing correctly]

1 Answers1