Linked-List

[dddx]

Hi again guys,

Unfortunately this term i am dealing with two of the things i never fully learned from my previous terms and courses. Recursion and Linked-List. Here, I'd like to ask your advise and comments on the following questions.

(Please know that i am not here only to get answers for my assignments and i do not expect you guys to waste your time on my assignment either. So any comment, guide or even better, detailed explanation on how i can do them myself step by step is welcome.) All related replies are appreciated.

Here are the problems and i also wrote what i could figure out:

a) Describe a method for inserting an element at the beginning of a singly linked list. Assume that the list does not have a sentinel header node, and instead uses a variable head to reference the first node in the list.

--> first add the new element, then head=reference to the new element. Then change the reference from the new element to the previous first element.


b) Describe a good algorithm for concatenating two singly linked lists L and M, with header sentinels, into a single list L ′ that contains all the nodes of L followed by all the nodes of M.

-->
L.getFirst() = L.getFirst() + M.getFirst()
for i=0; i<L.size() || i<M.size(); i++
{ L.next() = current L element + M.next() }




c) Describe in detail how to swap two nodes x and y in a singly linked list L given references only to x and y with the addition that ?not just their contents? should be swapped. Repeat this exercise for the case when L is a doubly linked list. Which algorithm takes more time?

--> i have no clue



d) Given a circularly linked list L containing an even number of nodes, describe how to split L into two circularly linked lists of half the size.

--> First create two linked lists with the size half of the L. Then loop for half the size L and put L the the first new linked list one by one. Then another loop with half the size of L to continue from the middle of L and put the reset of the elements one by one in the 2nd new linked list.



Guys i would like to thank you all in advance for any help
dddx

[Insectoid]

a) you've got the idea.

b) The important thing to remember is that you must duplicate the elements instead of just pointing them at each other. If you change the pointers you destroy the original lists, which we don't want to do. Just iterate over the first list, copy the contents into new nodes in a new list, then iterate over the 2nd list, duplicating each element and pushing it to the end of the list.

Alternatively, you can iterate backwards over the 1st list and add elements to the head of the new list, then iterate forwards over the 2nd list and append them to the back. Either way, you need to duplicate the elements.

c) I dunno how to do this in a singly-linked list without knowing what's pointing to x and y. I'd just swap the contents, but the question forbids it. Without direct memory management I don't know if it's possible (I hope it is, 'cause that would be cool).

In a double linked list you can easily just do
x->previous->next = y, y -> previous -> next = x. Assuming this is possible with a singly-linked list, the doubly-linked list is most likely faster (it's like, 4 operations vs magic and devilry, and magic and devilry are slow).

d) This is a slow, non-destructive algorithm. It will work and your teacher will likely accept it. A faster, destructive algorithm is as follows:

-Pick any node in the circle. We'll call it a
-Point it to the 'opposite' node. For a list of size n, this will be the node a+n/2+1th node.
-Point node a+n/2 to node a[i]+1.

Remember to include variable to temporarily store locations, or you'll lose them.

A visual example of this algorithm is to make a circle with your thumbs and forefingers touching. Bend your forefingers down to touch your thumbs to make 2 circles. The tip of your left finger represents node [i]a, the tip of your right finger represents node a+1, your left thumb is node a+n/2+1, and your right thumb is node a+n/2.

Hopefully this helps.

[DemonWasp]

a) I think you've got the idea.

b) You need to re-read the question carefully: you are trying to solve a very different problem than the one it asks for.

c) Try solving the doubly-linked-list case first, because that's a lot more obvious than the singly-linked-list case.

d) There's an easier way. You do NOT need to know the length of L to solve the problem, nor do you need to compute it.

[Insectoid]

Ah, there are some formatting errors in my post that may confuse you. Any instance of a[i] or similar, is meant to italicize a. I can't fix it since DemonWasp replied already.

As for an easier way to do d, in a double-linked circle you can just walk two pointers around the circle in opposite directions until they meet up. This is your 'break-point'.

[DemonWasp]

Insectoid, there is an even easier way to solve part D. Note that you do not care which elements end up in which sub-list. You can do it by walking the list exactly once.

[dddx]

Thanks guys for all your great and useful comments.

Regarding the part c, could you please explain a little more about the singly list and to how to do that? I was thinking that i could create a new node and copy x and it's reference then replace x and x.next with y and y.next then replace y with the new node. Does this makes any sense?

I could do the same thing for doubly, but what will be the time difference then? would doubly be still faster?

Thanks

[DemonWasp]

For part C:

In the singly-linked case, you will need to walk the list, because you need to find the node that come BEFORE each of X and Y. In the doubly-linked case, you already know that as X.prev and Y.prev . You should be able to figure out the time complexity based on that.

[dddx]

Thanks DemonWasp,

You are right, i missed the part that i need to find the x and y's previous. But how can i do that by going through the list? Quite confused. Should i use a variable to copy every node-1 during the loop, so if i reach for example x, then my variable is holding the previous node to x. Does it make any sense?

Thanks a lot

[Insectoid]

@Demonwasp- I thought that part C was impossible, because you are given *only* references to x and y. I took this as meaning you do not have the head of the list so you cannot walk down it.

[DemonWasp]

dddx: At each iteration through the loop, if current.next == x, set xPrev (local variable) to current; if current.next == y, set yPrev (another local variable) to current.

Insectoid: That's another reasonable interpretation of the question, and I'm not sure which I think is more likely to be what they wanted. It may make sense to list both. There's a third, less likely interpretation, where you don't have a head node, but you can do it anyway because L is circularly-linked.

[dddx]

That helps a lot.

Many thanks to both DemonWasp and Insectoid for helping me out. I really appreciate it