Что такое мультисписок?

Самый простой способ реализовать такое в C++ - использовать shared_ptr для хранения данных A,B,C,D (shared_ptr - это указатель с подсчетом ссылок), и связывать их обычным списком:

  std::forward_list<std::shared_ptr<char>> list1;
  std::forward_list<std::shared_ptr<char>> list2;
  {
    auto A = std::make_shared<char>('A');
    auto B = std::make_shared<char>('B');
    auto C = std::make_shared<char>('C');
    auto D = std::make_shared<char>('D');
    list1 = {A, B, C, D};
    list2 = {D, B, C};
  }
  assert(*list1.front() == 'A');
  assert(*list2.front() == 'D'); 

При этом все ресурсы будут корректно освобождаться, когда списки будут удаляться, а списков может быть любое количество (в общем случае, можно построить граф).

Но при этом память под сами данные выделяется динамически, и при этом динамически выделяется память под каждый узел. Счетчик ссылок также может быть создан в динамической памяти, если не использовать make_shared.

Можно попытаться упростить подсчет ссылок (по сути, достаточно булева флага - является ли узел элементом сразу двух списков, или только одного), но возникает вопрос, как удалять узлы, чтобы не удалить два раза один и тот же, и как добавить один узел в оба списка.

У меня получился такой список (c++14):

#include<memory>
#include<forward_list>
#include<cassert>
#include<iostream>
template<class T>
class BinaryList{
  class Node{
  public:
    friend class BinaryList;
    T value;
    Node(T v): value{std::move(v)}, inList1{false}, inList2{false}{
    }
    Node* getNext1(){
      return next1.get();
    }
    Node* getNext2(){
      return next2.get();
    }
    ~Node(){
      std::cout << "~" << value <<std::endl;
      value = T{}; // Чтобы заметить, если один узел два раза удалится
    }
  private:
    struct Deleter{ // Функциональный объект для удаления узла
      void operator() (Node* ptr){
        if(ptr){
          std::cout << "deleter: " << ptr->value <<std::endl;
          if(ptr->inList1){ // Если узел в списке 1, удаляем из него
            if(!ptr->inList2){
              delete(ptr);
            }else{
              ptr->inList1 = false;
              auto tmp = std::move(ptr->next1);
              tmp.reset(); // удаляем следующие в списке 1, если есть
            }
          }
          else{
            // Если нет в списке1, можно его спокойно удалять
            // - он есть в списке 2 (или еще не внесён в список из-за исключения).
            delete(ptr);
          }
        }
      }
    }; // deleter
    bool inList1;
    bool inList2;
    std::unique_ptr<Node, Deleter> next1;
    std::unique_ptr<Node, Deleter> next2; // Сначала должен удалиться список 1, потому он ниже
  }; // Node
  using node_ptr_t = decltype(Node::next1);
  node_ptr_t head2;
  node_ptr_t head1;
  public:
  Node* add1(T value){
    node_ptr_t newHead {new Node(std::move(value))};
    newHead->inList1 = true;
    newHead->next1 = std::move(head1);
    head1 = std::move(newHead);
    return getHead1();
  }
  Node* add1(Node* node){
    node_ptr_t newHead{ node};
    newHead->inList1 = true;
    newHead->next1 = std::move(head1);
    head1 = std::move(newHead);
    return getHead1();
  }
  Node* add2(T value){
    node_ptr_t newHead { new Node(std::move(value))};
    newHead->inList2 = true;
    newHead->next2 = std::move(head2);
    head2 = std::move(newHead);
    return getHead2();
  }
  Node* add2(Node* node){
    node_ptr_t newHead{ node};
    newHead->inList2 = true;
    newHead->next2 = std::move(head2);
    head2 = std::move(newHead);
    return getHead2();
  }
  Node* getHead1(){
    return head1.get();
  }
  Node* getHead2(){
    return head2.get();
  }
};
int main()
{
  BinaryList<char> bl;
  auto* A = bl.add1('A'); //[A] / []
  auto* D = bl.add2('D'); //[A] / [D]
  auto* B = bl.add2('B'); //[A] / [D, B]
            bl.add1(B);   //[A, B] / [D, B]
  auto* C = bl.add1('C'); //[A, B, C] / [D, B]
            bl.add2(C);   //[A, B, C] / [D, B, C]
            bl.add1(D);   //[A, B, C, D] / [D, B, C]
  std::cout<<"list1: ";
  for(auto* node = bl.getHead1(); node != nullptr; node = node->getNext1())
    std::cout << node->value << ", ";
  std::cout<<std::endl;
  std::cout<<"list2: ";
  for(auto* node = bl.getHead2(); node != nullptr; node = node->getNext2())
    std::cout << node->value << ", ";
  std::cout<<std::endl;
  return 0;
}

Вывод:

list1: D, C, B, A, 
list2: C, B, D, 
deleter: D
deleter: C
deleter: B
deleter: A
~A
deleter: C
~C
deleter: B
~B
deleter: D
~D

Узлы добавляются в начало списка, т.к. он однонаправленный, не реализована вставка в произвольное место и удаление произвольного узла (для удаления нужно вызывать next1.release() и next2.release(), что обнуляет указатель, но не удаляет объект, но сначала нужно найти предыдущие элементы в обоих списках)

EDIT: Удаление списка изначально сделано неправильно, судя по всему. Теперь должно нормально работать.