Concatenate two linked lists in reverse order

Question

I have two lists, for which I am currently using std::list < size_t >. Let's call them list A and list B. Let list A have elements [1, 2, 3, 4] and list B have elements [5, 6, 7, 8].

I want to concatenate the two list. However, in my application, there are eight ways to concatenate. I will describe two ways to keep it minimal:

Concatenate A and B directly. So list C = [1, 2, 3, 4, 5, 6, 7, 8].
Reverse lists A and B and then concatenate. So list C = [4, 3, 2, 1, 8, 7, 6, 5].

For the first case, I could use the following code (source: cppreference):

std::list <size_t> C; 
C.splice(C.begin(), A); 
C.splice(C.end(), B);

This gives a nice constant time implementation.

For the second case, where I have to reverse the lists, I could use reverse() for the purpose (source: cppreference):

A.reverse();
B.reverse();
C_reversed.splice(C_reversed.begin(), A);
C_reversed.splice(C_reversed.end(), B);
std::cout << "C_reversed: " << C_reversed << std::endl;

This works nicely, however, it has a linear time complexity. Is there a better way to do this? I read through Stack Overflow: Why does std::list::reverse have O(n) complexity?, and understood that it cannot be done using reverse(). Is there some other way to accomplish this in constant time?

My fallback option is to maintain four lists, two for each of A and B, so that I can concatenate in constant time. However, this results in additional space complexity. Example given below:

std::list <size_t> A1 = {1, 2, 3, 4};
std::list <size_t> A1_reversed = {4, 3, 2, 1};
std::list <size_t> B1 = {5, 6, 7, 8};
std::list <size_t> B1_reversed = {8, 7, 6, 5};
std::list <size_t> C1;
C1.splice(C1.begin(), A1);
C1.splice(C1.end(), B1);
std::list <size_t> C1_reversed;
std::cout << "C1: "<< C1 <<std::endl;
C1_reversed.splice(C1_reversed.begin(), A1_reversed);
C1_reversed.splice(C1_reversed.end(), B1_reversed);
std::cout << "C1_reversed: "<< C1_reversed <<std::endl;

Code for experimentation is given below:

  /** Concatenation of two lists **/
#include <iostream>
#include <list>

std::ostream& operator<<(std::ostream& ostr, const std::list< size_t >& list) {
    for (auto &i : list) {
        ostr << " " << i;
    }
    return ostr;
}

int main(int argc, char **argv) {

    /** Initialize **/
    std::list < size_t > A = {1, 2, 3, 4};
    std::list < size_t > B = {5, 6, 7, 8};

    /** A + B **/
    std::list < size_t > C;
    C.splice(C.begin(), A);
    C.splice(C.end(), B);
    std::cout << C << std::endl;

    /** Reverse A + reverse B **/
    A = {1, 2, 3, 4};
    B = {5, 6, 7, 8};
    std::list < size_t > C_reversed;
    A.reverse();
    B.reverse();
    C_reversed.splice(C_reversed.begin(), A);
    C_reversed.splice(C_reversed.end(), B);
    std::cout << C_reversed << std::endl;

    /** Maintaining four lists **/
    std::list <size_t> A1 = {1, 2, 3, 4};
    std::list <size_t> A1_reversed = {4, 3, 2, 1};
    std::list <size_t> B1 = {5, 6, 7, 8};
    std::list <size_t> B1_reversed = {8, 7, 6, 5};
    std::list <size_t> C1;
    C1.splice(C1.begin(), A1);
    C1.splice(C1.end(), B1);
    std::list <size_t> C1_reversed;
    std::cout << "C1: "<< C1 <<std::endl;
    C1_reversed.splice(C1_reversed.begin(), A1_reversed);
    C1_reversed.splice(C1_reversed.end(), B1_reversed);
    std::cout << "C1_reversed: "<< C1_reversed <<std::endl;

    return 0;
}

You could use rbegin and rend to iterate a list backward and as such avoid actual reversing. — Phil1970
– Phil1970, Commented Sep 5, 2019 at 3:48
Iterating would result in linear time complexity, and splice() does not take reverse_iterators, i.e., rbegin and rend. — Marvin
– Marvin, Commented Sep 5, 2019 at 3:57
When you print the list, it is already O(n)... You could minimize the number of reversing. And if the list is short, it really does not matters much. — Phil1970
– Phil1970, Commented Sep 5, 2019 at 12:34

v78 · Accepted Answer · 2019-09-09 04:21:28Z

To make it O(1), We can extend the stl::list class or otherwise implement a similar interface. Below is a starting example. Claim: Every function of stl::list can be implemented for ReversedConCatList keeping the complexity same or even better compared to that of the original stl::list.

template <typename T> 
class ReversedConCatList {  
  public:
    typedef value_type& reference;
    typedef /*implementation-defined: special_iterator*/ iterator; // special_iterator(l1, l2);
    void push_back(T value) {
      b_.emplace_front(value);
    }
    void push_front(T value) {
      a_.push_back(value);
    }
    reference front() {
      return a_.empty() ? b_.back(): a_.back();
    }
    reference back() {
      return b_.empty() ? a_.front() : b_.front();
    }
    iterator begin() noexcept {
      return special_iterator(a_, b_);
    }
    iterator end() noexcept {
      return a.begin().base(); // end of special iterator
    }
    size_type size() const noexcept {
      return a_.size() + b_.size();
    }
    bool empty() const noexcept {
      return a_.empty() && b_.empty();
    }
    // ...
  private:
    std::list<T> a_; // Takes ownership
    std::list<T> b_; // Takes ownership
};

Basically, all operations of the lists can be implemented with ReversedConCatList in other cases like A + reversed(B) or reversed(A) + B by just keeping boolean flags for whether a list is reversed or not. Even better use templates to get rid of flags at compile time.

Insight is that list API has same power from the head and tails, hence we are able to do this, std::list could have implemented reverse() with O(1) complexity, but that would have created merging list complexity non trivial(currently its O(1)).

It would really help if you can add some description. I am confused, in particular how do I get other combinations of merge (e.g., A + reverse(B) or reverse(B) + reverse(A)). As mentioned there are 8 such combinations.

Collectives™ on Stack Overflow

Concatenate two linked lists in reverse order

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related