Re: Middle pointer for double linked list.


"Maarten Wiltink" <maarten@xxxxxxxxxxxxxxxxxx> wrote in message
news:47eb5f05$0$14346$e4fe514c@xxxxxxxxxxxxxxxxx
"Skybuck Flying" <spam@xxxxxxxxxxx> wrote in message
news:11dc5$47eb11fc$541983fa$3581@xxxxxxxxxxxxxxxxxxxxxxxxxxx

Little idea:

Keep track of a middle pointer for a double linked list.

Each time two nodes are added on the same side move the middle pointer
accordingly.

Do the same vice versa for removing twice from the same side.

Only problem is when removing nodes twice from the same side for uneven
sides, when only two nodes are left the middle pointer would not be
updated and would keep pointing to a non existing node.

How would you know on which side of the middle a modification is?

For example, my double linked list works with the following methods:

AddBegin( Node ); // left side
AddEnd( Node ); // right side

RemoveBegin( Node ); // left side
RemoveEnd( Node ); // right side

AddSorted( Node ); // could be anywhere... uses methods above and others.

Haven't really thought about other methods like AddBeforeCurrentNode,
AddAfterCurrentNode.

Maybe more info would need to be kept for that... if current node was set
manually, then it becomes nearly impossible to know...

The middle pointer is a crappy idea to begin with :)

If I need performance I'll use other data structures in combination with the
double linked lists lol.

However the middle pointer idea might be usefull for simple double linked
lists on systems where memory is too low for other data structures and
performance just needs to be increased by some 25% or so for adding sorted
from begin or end or from middle or whatever.

Bye,
Skybuck.


.