By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,301 Members | 1,366 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,301 IT Pros & Developers. It's quick & easy.

lookup data structure that returns the previous element as well

P: n/a
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
Nov 14 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
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_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
Nov 14 '05 #2

P: n/a
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
Nov 14 '05 #3

P: n/a
>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
Nov 14 '05 #4

P: n/a
Jan Engelhardt <je*****@linux01.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.
Nov 14 '05 #5

P: n/a
>> 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.
Nov 14 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.