Traverse a doubly Linked List to a given index

Question

I'm working on a doubly linked list and want to implement an insert() function at a given index. Right now I am able to traverse through the linked list with a for loop. However, I want execute the traversing with a while loop but I cant figure it out.

The for loop I am running is

   for (int i = 0; i < index - 1; i++) {
           //move the temp pointer down the list 
           temp = temp->next; 
       }

The full insert() function:

template<typename Data>
void Link<Data>::insert(int index, Data value) {

    if (head == nullptr) {
        Link<Data>::push2Front(value);
    }
    else if (index >= size) {
        Link<Data>::add2Rear(value);
    }
    else {
        Node* temp = head;
        for (int i = 0; i < index - 1; i++) {
            temp = temp->next; 
        } 
        Node* nn = new Node;
        nn->value = value; 
        nn->next = temp->next;
        nn->prev = temp->prev;
        temp->next->prev = nn;
        temp->next = nn;
        size++;
    }
}

Suggestions are much appreciated.

You're not checking to see if next is a null value. Search for "c++ convert for loop to while loop" — Kenny Ostrom, Dec 24 '21 at 01:02
whats the problem with the `while` loop? `while( i < index - 1) { .... ; i++; }` — 463035818_is_not_an_ai, Dec 24 '21 at 01:02
*"I want execute the traversing with a while loop"* -- why? What benefit do you hope to gain? — JaMiT, Dec 24 '21 at 01:42
Why wouldn't `nn->prev = temp;` if you are inserting `nn` after `temp`? Take out a piece of paper and a pencil. Draw out the `temp` and `temp->next` nodes with the pointers drawn as lines with arrows between them. Now break the pointer lines with the eraser and draw `nn` above and between the two node. Now draw in what the new pointer connections need to be -- then write your code to make that happen. — David C. Rankin, Dec 24 '21 at 01:45
@ouet.hands In the pursuit of knowledge, there are many resources to read, such as [how to convert an for loop to while loop](https://stackoverflow.com/questions/47611375/), [for loop to while conversion](https://stackoverflow.com/questions/52236270/), [for loop converted to a while loop](https://stackoverflow.com/questions/9795898/), and of course [cppreference.com](https://en.cppreference.com/w/cpp/language/for), which describes what a `for` loop does in terms of an equivalent `while` loop. — JaMiT, Dec 24 '21 at 05:17

score 0 · Answer 1 · answered Dec 24 '21 at 01:32

0

You can do it like this

int i=0;

while(i<index-1){

  temp=temp->next;
  ++i;

}

answered Dec 24 '21 at 01:32

kronos

11
1
3

That is unsafe. There is no `nullptr` check. – sweenish Dec 24 '21 at 01:33
2

It could be safe, if you knew with 100% certainty that first `index` pointers are non-NULL (i.e. if you are keeping a list-length field separately and you validate that `index` is smaller than that beforehand) – Jeremy Friesner Dec 24 '21 at 01:45

Remy Lebeau · Answer 2 · 2021-12-24T03:05:54.607

Using a while loop instead is very easy, just decrement index until it reaches 0, eg:

template<typename Data>
void Link<Data>::insert(int index, Data value) {
    if (index <= 0) {
        Link<Data>::push2Front(value);
    }
    else if (index >= count) {
        Link<Data>::add2Rear(value);
    }
    else {
        Node* temp = head;
        while (--index > 0) {
            temp = temp->next; 
        } 
        Node* nn = new Node;
        nn->value = value; 
        nn->next = temp->next;
        nn->prev = temp;
        if (temp->next) temp->next->prev = nn;
        temp->next = nn;
        ++size;
    }
}

That being said, the insert() code can be simplified a bit further:

template<typename Data>
void Link<Data>::insert(int index, Data value) {
    if (index < 0 || index > size) {
        throw std::out_of_range("");
    }
    Node** temp = &head;
    Node* prev = nullptr;
    while (index-- > 0) {
        prev = *temp;
        temp = &(prev->next);
    }    
    Node* nn = new Node;
    nn->value = value; 
    nn->next = *temp;
    nn->prev = prev;
    if (*temp) (*temp)->prev = nn;
    *temp = nn;
    ++size;
}

Traverse a doubly Linked List to a given index

2 Answers2