lookup data structure that returns the previous element as well

P

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
 
J

James Hu

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_container *container;
};

struct foo_node *
find_foo_node(struct foo *foo_instance, const void *key)
{
struct foo_node *node_of_interest;

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

return foo_instance->last = node_of_interest;
}

-- James
 
E

Eric Sosman

Peter said:
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.
 
J

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
 
B

Ben Pfaff

Jan Engelhardt said:
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.
 
J

Jan Engelhardt

Define 'previous'. If I suggested you a binary tree, 'previous' would be
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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top