linked list

[serendipity]

how can i add and delete nodes at the middle of the linked list??

[r035198x]

how can i add and delete nodes at the middle of the linked list??

What do you so far?
Do you have the LinkedList and the Nodes already?

[JosAH]

how can i add and delete nodes at the middle of the linked list??

Think a bit: suppose you know how to reach the previous node and the current
node; you can reach the next node then. There are two possibilities: there is
no previous node or there is. In the first case the current node is the first node
in the list, otherwise it isn't. You're not really interested whether or not the next
node exists.

kind regards,

Jos

[Nepomuk]

how can i add and delete nodes at the middle of the linked list??

If you want to add/delete a node at the middle position, you have an annoying task infront of you:

You first have to count, how many elements are in the list (if no such function is preimplemented), then you have to find the middle position (Spoiler: number of elements divided by 2) and add/delete the element there.

If you have the choice, use a different type of list (e.g. ArrayList), as this makes life much easier.

[JosAH]

If you want to add/delete a node at the middle position, you have an annoying task infront of you:

You first have to count, how many elements are in the list (if no such function is preimplemented), then you have to find the middle position (Spoiler: number of elements divided by 2) and add/delete the element there.

If you have the choice, use a different type of list (e.g. ArrayList), as this makes life much easier.

I didn't understand 'in the middle' that literally ;-)
But even if you do take it that way you don't have to count: take two pointers;
make them point at the start of the list. Then let them run: the first pointer runs
twice as fast as the second pointer so when the first pointer runs off the list,
the second pointer points to the middle element of the list (if present).

kind regards,

Jos

[Nepomuk]

take two pointers;
make them point at the start of the list. Then let them run: the first pointer runs
twice as fast as the second pointer so when the first pointer runs off the list,
the second pointer points to the middle element of the list (if present).

Hm, nice trick! I'll have to remember that one! ^^

[JosAH]

Hm, nice trick! I'll have to remember that one! ^^

I'm just an old bag full of (old) tricks ;-) You have to take care of the details if
you want to make use of this trick, e.g. if you let the 'fast' pointer run first,
don't run the second pointer if the first one falls of the list in one of its two jumps.
That way you either end up at the middle element (with the slow pointer) when
there are an odd number of elements in the list, or you end up at element n/2
(integer division) when there are an even number n elements in the list.

kind regards,

Jos