Home > Software design >  Traverse a doubly Linked List to a given index
Traverse a doubly Linked List to a given index

Time:12-24

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.

CodePudding user response:

You can do it like this

int i=0;

while(i<index-1){

  temp=temp->next;
    i;

}

CodePudding user response:

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;
}
  •  Tags:  
  • c
  • Related