lookup data structure that returns the previous element as well

[Peter]

I am looking for a data structure that I need to use as follows.
Suppose I am looking for node A. When I perform a lookup for node A I
also want information about the node previous to node A( as per the
lookup data structure ordering scheme). Is there anything that I could
use for this. Using a doubly linked list is not looking good as I can
have a large number of elements in my linked list.

Thanks in advance,
Peter

[James Hu]

On 2003-12-09, Peter <pe************ **@yahoo.com> wrote:

I am looking for a data structure that I need to use as follows.
Suppose I am looking for node A. When I perform a lookup for node A I
also want information about the node previous to node A( as per the
lookup data structure ordering scheme). Is there anything that I could
use for this. Using a doubly linked list is not looking good as I can
have a large number of elements in my linked list.

One common trick is to stash the previous node someplace in your lookup
datastructure.

struct foo {
struct foo_node *last;
struct foo_node_contai ner *container;
};

struct foo_node *
find_foo_node(s truct foo *foo_instance, const void *key)
{
struct foo_node *node_of_intere st;

node_of_interes t = container->find(container , key);
if (foo_instance->last) {
/*
* ...
* do something to node_of_interes t with info from last
* ...
*/
}

return foo_instance->last = node_of_interes t;
}

-- James

[Eric Sosman]

Peter wrote:

I am looking for a data structure that I need to use as follows.
Suppose I am looking for node A. When I perform a lookup for node A I
also want information about the node previous to node A( as per the
lookup data structure ordering scheme). Is there anything that I could
use for this. Using a doubly linked list is not looking good as I can
have a large number of elements in my linked list.

If there's a C question here, I'm failing to see it.
Well, maybe there is: If "previous" is a relation defined
by a key value in the node, you can maintain the collection
of nodes as a sorted array and look things up with bsearch().

Other algorithms certainly exist, and may be more
appropriate (you really haven't explained your problem in
any detail) -- but this is a language newsgroup, not an
algorithms newsgroup. Once you've settled on an approach,
come back here for help if you're having trouble implementing
it in C.

--
Er*********@sun .com

[Jan Engelhardt]

>Subject: lookup data structure that returns the previous element as well

I am looking for a data structure that I need to use as follows.
Suppose I am looking for node A. When I perform a lookup for node A I
also want information about the node previous to node A( as per the
lookup data structure ordering scheme). Is there anything that I could
use for this. Using a doubly linked list is not looking good as I can
have a large number of elements in my linked list.

Define 'previous'. If I suggested you a binary tree, 'previous' would be
ambiguous (previous in-order node -- or the node's parent).
I assume you mean the former, as you mention linked lists. Getting the previous
in-order element with a btree is a bit more complicated, but the Btree gives
you an all-around better performance than a linked list when having lots of
elements.


Jan Engelhardt

[Ben Pfaff]

Jan Engelhardt <je*****@linux0 1.gwdg.de> writes:

Define 'previous'. If I suggested you a binary tree, 'previous' would be
ambiguous (previous in-order node -- or the node's parent).

I have never heard the word "previous" used to refer to a binary
tree node's parent.

[Jan Engelhardt]

>> Define 'previous'. If I suggested you a binary tree, 'previous' would be

ambiguous (previous in-order node -- or the node's parent).

I have never heard the word "previous" used to refer to a binary
tree node's parent.

When you run along a path, the previous [path] node is obviously the parent.