CODEWITHSUNDEEP
c++singly-linked-listforward-list
Samaursa
Samaursa

Reputation: 17197

Splice_after implementation of forward_list

In forward_list there is a function splice_after (for reference), specifically, function #3 in the link given. How would one go about implementing that considering the list is singly linked.

As an exercise, when I implemented it, I had to iterate the list until I reached the node before first (so that I can connect first to last) and again until I reached the node before last (so that I can connect the current list's node to the node before last). This does not seem terrible efficient to me and was wondering whether there is a better way to do it without iteration?

Upvotes: 3

Views: 546

Answers (2)

Dietmar Kühl
Dietmar Kühl

Reputation: 153820

I suspect you misread the somewhat subtle range specification which says that "(first, last)" is moved, not "[first, last)" (note the opening parenthesis/bracket). That is, as the name indicates, the splice operation only starts after the first object.

The implementation of the function is actually quite simple (if you ignore constness of the iterators and the fact that it might need to deal with allocators being different):

void splice_after(const_iterator pos, forward_list& other,
                  const_iterator first, const_iterator last) {
    node* f = first._Node->_Next;
    node* p = f;
    while (p->_Next != last._Node) { // last is not included: find its predecessor
        p = p->_Next;
    }
    first._Node->Next = last._Node;  // remove nodes from this
    p->_Next = pos._Node->_Next;     // hook the tail of the other list onto last
    pos._Node->_Next = f;            // hook the spliced elements onto pos
}

This operation has linear complexity because it needs to find the predecessor of last.

Upvotes: 3

Aaron McDaid
Aaron McDaid

Reputation: 27133

(community-wiki, please contribute)

 A -> B -> C -> D -> E
           ^
           ^ pos points to C

In the other list

 U -> V -> W -> X -> Y -> Z
      ^              ^
      ^ first        ^ last

Call .splice(pos, other, first, last)

We are to move W and X into the top list. i.e. everything between, but not including, first and last. To end up with A->B->C->W->X->D->E at the top, and U->V->Y->Z at the bottom.

auto copy_of_first_next = first->next;
first->next = last;
// the `other` list has now been emptied

auto copy_of_pos_next = pos->next;
pos -> next = first;
while(first->next != last) ++first;
// `first` now points just before `last`
first->next = copy_of_pos_next

Upvotes: 2

Related Questions