Insert a linked list inside another linked list

Question

I have a doubly linked list with these int 5->6->8->10 and I am creating another doubly linked list with int 1->7->3.

What I want to do is link the int 5 in the first list with int 1 in the second list. In other I want the first node inside one list to point to the first node in the other list.

Here is a rough diagram of everything

I was thinking about storing the list as data inside the other list but unsure how to do that, if possible.

Hey This Is Not A Doubly Linked List?It Is Chained Double Linked List ? — Shankar Shastri, Sep 16 '16 at 16:27
Please clarify your question, your diagram is not consistent with your description. Where is your 1->7->3 list? — very hit, Sep 16 '16 at 16:33

score 1 · Answer 1 · answered Sep 16 '16 at 16:31

1

Well I don't really understand your wording, but based on the picture:

struct Data {
    int value;
    std::list<int> list;
};

std::list<Data> data = {
    {5, {1}},
    {6, {7, 8, 5}},
    {8, {4, 3}},
    {10, {8, 4}}
};

answered Sep 16 '16 at 16:31

David

27,652
18
89
138

2

Brilliant replication of the diagram in code! – πάντα ῥεῖ Sep 16 '16 at 16:32
Nice, though I bet the task is about redoing STL by hand. – iksemyonov Sep 16 '16 at 18:38

score 0 · Answer 2 · answered Sep 16 '16 at 16:35

What this is actually called is a binary tree or a node system what you want to do is make a structure with a data holder (your int value) then have three pointers one for the father and two for the children it's not really a linked list but it is used in data structure. so in your example 5 is the root and it has a null pointer to it's father and one pointer at the 1 value and another at the 6 value and both the six and the one have the father pointer at 5 then 1 has two null pointers for children and the 6 has a pointer at 7 and another one at 8 and so on and so on.

You definitely could store his data as a binary tree, but in general the same data _can_ be stored in many different data structures. You'd really have to know more about the data and its usage to make an intelligent data structure choice. — David, Sep 16 '16 at 16:49

score 0 · Answer 3 · edited May 23 '17 at 12:16

I was thinking about storing the list as data inside the other list but unsure how to do that, if possible.

Possible with templates. Easy if you allow the 1,7,3 list to be 5,1,7,3

I'm just going to stick to the data structure and ignore the linked list logic since OP already has that written.

template<class TYPE>
class LinkedList
{
private:
    struct Node
    {
        TYPE data;
        Node * next;
        Node * prev;
    };

    Node * head;
public:
    LinkedList():head(nullptr)
    {

    }
    ~LinkedList()
    {
        while (head != nullptr)
        {
            Node *temp = head;
            head = head->next;
            delete temp;
        }
    }
    // methods go here
};

This is the bare minimum. It needs insert, remove, and an iterator or other means of traversal to work with the list. To be Rule of Three compliant, it also needs a copy constructor and an assignment operator (operator=). I recommend against exposing Node to the user. With it they can wreak all sorts of unholy hell, so hide the Nodes behind iterators.

Declaration of the 5,1,7,3 variant list would look something like

LinkedList<LinkedList<int>> list;

list points to a Node. This Node contains another LinkedList that points to Nodes of ints as well as the next and previous node.

To preserve 5,6,8,10 and 1,7,3, you need an intermediary that stores a number and a linked list

struct Intermediary
{
    int data;
    LinkedList<int> sublist;
};

LinkedList<Intermediary> list;

std::pair would also work.

Insert a linked list inside another linked list

3 Answers3