Can we merge two unsorted lists in constant time?

[evinda]

Hello! (Wave)

I want to write an algorithm, that merges two unsorted lists and returns a pointer to the first list, that should then contain both the elements of the first and the second list.
The algorithm should have a constant time complexity.

To do that, shouldn't we traverse the first list and then make the pointer of the last element to show to the first element of the second list? But wouldn't the complexity be, in this case, $O(n)$ ?

How could we merge two unsorted lists with a constant time complexity? (Worried)

 

[I like Serena]

Hello! (Wave)

I want to write an algorithm, that merges two unsorted lists and returns a pointer to the first list, that should then contain both the elements of the first and the second list.
The algorithm should have a constant time complexity.

To do that, shouldn't we traverse the first list and then make the pointer of the last element to show to the first element of the second list? But wouldn't the complexity be, in this case, $O(n)$ ?

How could we merge two unsorted lists with a constant time complexity? (Worried)

Hey! (Blush)

Suppose we keep track of a pointer to the end of the first list... (Thinking)

 

[evinda]

Hey! (Blush)

Suppose we keep track of a pointer to the end of the first list... (Thinking)

Could you explain it further to me? I haven't understood it... (Sweating)

 

[I like Serena]

Could you explain it further to me? I haven't understood it... (Sweating)

When maintaining a list, it's pretty normal to keep a pointer to the beginning of the list (aka the head), and a pointer to the end of the list (aka the tail).
When we add an element, we add it to the tail, and then update the tail.
Otherwise it would be pretty expensive to add an element.
And when we want to iterate through the list, we start at the head. (Nerd)

If you append two such lists, the only thing you need is that the tail of the first list gets to point to the head of the second list.
And also that the new tail is the tail of the second list.

In other words: $\mathcal O(1)$. (Mmm)

 

[evinda]

When maintaining a list, it's pretty normal to keep a pointer to the beginning of the list (aka the head), and a pointer to the end of the list (aka the tail).

When we have a list, are the pointers head and tail at the first and last position of the list, respectively? Or do we have to put them at the right position? (Thinking)

 

[I like Serena]

When we have a list, are the pointers head and tail at the first and last position of the list, respectively? Or do we have to put them at the right position? (Thinking)

I don't understand you. (Worried)

The pointers are not values in the list.
They are maintained next to the list.

 

[evinda]

I don't understand you. (Worried)

The pointers are not values in the list.
They are maintained next to the list.

Can we use them, considering that head points to the first element of the list, and tail to the last one? (Thinking)

Or do we have to put them in the right position, so that the pointer head points at the first position and tail at the last one? (Thinking)

 

[alyafey22]

Basically , it depends on the list is implemented. If the list has an information about the last element then it should take a constant time. Otherwise , we must traverse all elements to get the last element.

 

[evinda]

The only information, that is given about the lists, is that they are singled linked.

So, can we use the pointers head and tail, without having to place them at the right position? (Thinking)

 

[I like Serena]

Can we use them, considering that head points to the first element of the list, and tail to the last one? (Thinking)

Yes. (Nod)

Or do we have to put them in the right position, so that the pointer head points at the first position and tail at the last one? (Thinking)

We can assume they are in the right position.
For instance, adding an element to the list means:
$$
\begin{cases}
tail.next &\gets \text{new list element} \\
tail &\gets tail.next \\
tail.value &\gets \textit{new value} \\
\end{cases}
$$

The only information, that is given about the lists, is that they are singled linked.

So, can we use the pointers head and tail, without having to place them at the right position? (Thinking)

Yes.
Singly linked means that each element has a pointer to the next element, but not to the previous element. (Nerd)

 

[evinda]

Yes. (Nod)
We can assume they are in the right position.
For instance, adding an element to the list means:
$$
\begin{cases}
tail.next &\gets \text{new list element} \\
tail &\gets tail.next \\
tail.value &\gets \textit{new value} \\
\end{cases}
$$
Yes.
Singly linked means that each element has a pointer to the next element, but not to the previous element. (Nerd)

A ok.. (Nod) So, before we merge the two lists, does tail point to NULL? (Thinking)

Also, do we have to define these two poiters? (Thinking)

 

[I like Serena]

A ok.. (Nod) So, before we merge the two lists, does tail point to NULL? (Thinking)

No. A tail of NULL means that the list is empty. (Wasntme)

Also, do we have to define these two poiters? (Thinking)

We have to keep track of the head, otherwise we cannot do anything with the list.
However, we don't have to keep track of the tail.
But if we don't, it takes O(n) to figure out where it is if we need it.
And keeping track of the tail doesn't increase the order of any algorithm. (Nerd)

 

[alyafey22]

No. A tail of NULL means that the list is empty. (Wasntme)

I think the OP said that the tail points to NULL , which is true.

 

[I like Serena]

I think the OP said that the tail points to NULL , which is true.

But if a tail points to NULL, there is nothing you can do with that tail.

 

[evinda]

No. A tail of NULL means that the list is empty. (Wasntme)

I think the OP said that the tail points to NULL , which is true.

tail.next points to NULL, right? (Thinking)

We have to keep track of the head, otherwise we cannot do anything with the list.
However, we don't have to keep track of the tail.
But if we don't, it takes O(n) to figure out where it is if we need it.
And keeping track of the tail doesn't increase the order of any algorithm. (Nerd)

So, do I have to say, before writing the algorithm, that we suppose that head points to the first element of the list and tail to the last one? (Thinking)

Also, at the beginning of the algorithm, do I have to define head and tail like that:

pointer *head, *tail;

or don't we have to define them? (Thinking)

 

[I like Serena]

tail.next points to NULL, right? (Thinking)

Yes. (Nod)

So, do I have to say, before writing the algorithm, that we suppose that head points to the first element of the list and tail to the last one? (Thinking)

Yes.
But since you have 2 lists, you will also need the head of the second list.
For this algorithm you won't need the tail of the second list though. (Wasntme)

Also, at the beginning of the algorithm, do I have to define head and tail like that:

pointer *head, *tail;

or don't we have to define them? (Thinking)

I'd expect something like:
[m]pointer L1_head, L1_tail, L2_head;[/m]. (Wasntme)

Note that [m]pointer[/m] is already a pointer, so there should not be another [m]*[/m]. (Nerd)If you're programming in C, you might also use:

typedef struct element* pointer;

struct element {
    int data;
    pointer next;
};

struct list {
    pointer head, tail;
};

list L1, L2;

 

[evinda]

Yes. (Nod)

Yes.
But since you have 2 lists, you will also need the head of the second list.
For this algorithm you won't need the tail of the second list though. (Wasntme)

I'd expect something like:
[m]pointer L1_head, L1_tail, L2_head;[/m]. (Wasntme)

Note that [m]pointer[/m] is already a pointer, so there should not be another [m]*[/m]. (Nerd)If you're programming in C, you might also use:

typedef struct element* pointer;

struct element {
    int data;
    pointer next;
};

struct list {
    pointer head, tail;
};

list L1, L2;

Could the function also have as parameters the lists L1, L2, and the pointers L1_head, L1_tail, L2_head ? (Thinking)

 

[evinda]

Also, in order the function to return a pointer to the list, do I have to write

 return L1

or

return  L1_head

? (Thinking)

 

[I like Serena]

Could the function also have as parameters the lists L1, L2, and the pointers L1_head, L1_tail, L2_head ? (Thinking)

Also, in order the function to return a pointer to the list, do I have to write

 return L1

or

return  L1_head

? (Thinking)

You can do it any way you like.
Writing an algorithm is free style. (Mmm)

 

[evinda]

You can do it any way you like.
Writing an algorithm is free style. (Mmm)

A ok! (Nod) After the commands

L1_tail.next=L2_head

and

L1_tail=L2_tail

when we return L1_HEAD or L1, do we return the elements of both the first and the second list? (Thinking)

 

[I like Serena]

A ok! (Nod) After the commands

L1_tail.next=L2_head

and

L1_tail=L2_tail

when we return L1_HEAD or L1, do we return the elements of both the first and the second list? (Thinking)

Since your problem statement asks for the return of a pointer to the first element of the list, you should return L1_head. (Mmm)

 

[evinda]

Since your problem statement asks for the return of a pointer to the first element of the list, you should return L1_head. (Mmm)

I am also asked to explain what kind of variables we have to keep for each list, so that we have the required complexity.
It is meant that we have to use the pointers head and tail for each list, right? (Thinking) But.. how could I explain it? (Thinking)

 

[I like Serena]

I am also asked to explain what kind of variables we have to keep for each list, so that we have the required complexity.
It is meant that we have to use the pointers head and tail for each list, right? (Thinking) But.. how could I explain it? (Thinking)

Perhaps you can give it a go to try and explain it? (Sweating)

 

[evinda]

Perhaps you can give it a go to try and explain it? (Sweating)

head is a pointer, that points to the first element of the list, while tail is a pointer, that points to the last element of the list.

What else could I say? (Blush)

 

[I like Serena]

head is a pointer, that points to the first element of the list, while tail is a pointer, that points to the last element of the list.

What else could I say? (Blush)

How does it explain that we get the required complexity? (Wondering)

 

[evinda]

How does it explain that we get the required complexity? (Wondering)

Since we have a pointer, that points to the last element, we don't have to traverse the list to get there, in order to add the other list.

Or couldn't we say it like that? (Thinking)

 

[I like Serena]

Since we have a pointer, that points to the last element, we don't have to traverse the list to get there, in order to add the other list.

Or couldn't we say it like that? (Thinking)

That sounds good. (Smile)

 

[evinda]

That sounds good. (Smile)

Nice! (Nod) Thank you very much! (Smile)

 

[evinda]

When maintaining a list, it's pretty normal to keep a pointer to the beginning of the list (aka the head), and a pointer to the end of the list (aka the tail).
When we add an element, we add it to the tail, and then update the tail.
Otherwise it would be pretty expensive to add an element.
And when we want to iterate through the list, we start at the head. (Nerd)

If you append two such lists, the only thing you need is that the tail of the first list gets to point to the head of the second list.
And also that the new tail is the tail of the second list.

In other words: $\mathcal O(1)$. (Mmm)

So, is it like that?

L1_tail.next=L2.head;
L1_tail=L2_tail;

Or do I have to add also an other command? (Thinking)

 

[I like Serena]

So, is it like that?

L1_tail.next=L2.head;
L1_tail=L2_tail;

Or do I have to add also an other command? (Thinking)

That's it. (Mmm)

 

[evinda]

That's it. (Mmm)

Great! Thank you! (Party)

 

[evinda]

L1_tail.next=L2.head;
L1_tail=L2_tail;

If we would have an array $A$ and we would use a sentinel node, would it be like that? (Thinking)

A[i].sentinel=A[j].list;
A[i].sentinel=A[j].sentinel