473,236 Members | 1,771 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,236 software developers and data experts.

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.

Thanks in advance,
Peter
Nov 14 '05 #1
5 1783
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
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
>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
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
>> 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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
by: Neal D. Becker | last post by:
I need a fairly small lookup table, and I'm wondering which data python data structure would be fastest. I could use a list, tuple, dictionary, numeric array, or maybe plain python array. The...
0
by: Fabian Kr?ger | last post by:
Hello, I got a weird problem and need your help and ideas... Ive written an php application which imports data in XML format and writes this data to a MySQL database to have a faster access....
9
by: Koen | last post by:
Hi all, My application uses a lot of lookup tables. I've splitted the frontend (forms, reports, etc) from the backend (data). The database has around 10 different users. The values in the...
4
by: Thomas Paul Diffenbach | last post by:
Can anyone point me to an open source library of /statically allocated/ data structures? I'm writing some code that would benefit from trees, preferably self balancing, but on an embedded system...
26
by: Brett | last post by:
I have created a structure with five fields. I then create an array of this type of structure and place the structure into an array element. Say index one. I want to assign a value to field3 of...
6
by: Paul Delhanty | last post by:
Hi, I am converting an existing native C++ program making heavy use of STL to C#2.0 with STL usage replaced by the new generic collections. The conversion has gone well to the point where I am...
9
by: MR | last post by:
I get the following Exception "The data at the root level is invalid. Line 1, position 642" whenever I try to deserialize an incoming SOAP message. The incoming message is formed well and its...
3
by: dancole42 | last post by:
I'm self-taught in Access, and as such I'm missing large chunks of knowledge, so I'm hoping someone here with some training can help me. Right now I have an Invoice form with a Customer subform....
3
by: jacob navia | last post by:
Abstract: Continuing the discussion about abstract data types, in this discussion group, a string collection data type is presented, patterned after the collection in C# and similar languages...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, youll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.