What is a quad linked list?

Question

I'm currently working on implementing a list-type structure at work, and I need it to be crazy effective. In my search for effective data structures I stumbled across a patent for a quad liked list, and this sparked my interest enough to make me forget about my current task and start investigating the quad list instead. Unfortunately, internet was very secretive about the whole thing, and google didn't produce much in terms of usable results. The only explanation I got was the patent description that stated:

A quad linked data structure that provides bidirectional search capability for multiple related fields within a single record. The data base is searched by providing sets of pointers at intervals of N data entries to accommodate a binary search of the pointers followed by a linear search of the resultant range to locate an item of interest and its related field.

This, unfortunately, just makes me more puzzled, as I cannot wrap my head around the non-layman explanation. So therefore I turn to you all in hope that you can explain to me what this quad linked history really is, as I know not knowing will drive me up and over the walls pretty quickly.

Do you know what a quad linked list is?

Thanks a bundle!

Answer 1

I can't be sure, but it sounds a bit like a skip list.

Even if that's not what it is, you might find skip lists handy. (To the best of my knowledge they are unidirectional, however.)

Answer 2

The description isn't particularly good, but as best I can gather, it sounds like a less-efficient skip list.

Answer 3

I don't know if this is exactly a "quad-linked list", but it sounds like something like this:

struct Person {
    // Normal doubly-linked list.
    Customer *nextCustomer;
    Customer *prevCustomer;

    std::string firstName;

    Customer *nextByFirstName;
    Customer *prevByFirstName;

    std::string lastName;

    Customer *nextByLastName;
    Customer *prevByLastName;
};

That is: you maintain several orderings through your collection. You can easily navigate in firstName order, or in lastName order. It's expensive to keep the links up to date, but it makes navigation quite quick.

Of course, this could be something completely different.

Answer 4

My reading of it is that a quad linked list is one which can be traversed (backwards or forwards) in O(n) in two different ways, ie sorted according to FieldX or FieldY:

(a) generating first and second sets of link pointers, wherein the first set of link pointers points to successor elements of the set of related records when the records are ordered with respect to the fixed ID field, and the second set of link pointers points to predecessor elements of the set of related records when the records are ordered with respect to the fixed ID field;

(b) generating third and fourth sets of link pointers, wherein the third set of link pointers points to successor elements of the set of related records when the records are ordered with respect to the variable ID field, and the fourth set of link pointers points to predecessor elements of the set of related records when the records are ordered with respect to the variable ID field;

So if you had a quad linked list of employees you could store it sorted by name AND sorted by age, and enumerate either in O(n).

Answer 5

I've not come across the term formally before, but from the patent description, I can make an educated guess.

A linked list is one where each node has a link to the next...

a -->-- b -->-- c -->-- d -->-- null

A doubly linked list means each node holds a link to it's predecesor as well.

  --<--   --<--   --<--  
|       |       |       |
a -->-- b -->-- c -->-- d -->-- null

Let's assume the list is sorted. If I want to perform binary search, I'd normally go half way down the list to find the middle node, then go into the appropriate interval and repeat. However, linked list traversal is always O(n) - I have to follow all the links. From the description, I think they're just adding additional links from a node to "skip" a fixed number of nodes ahead in the list. Something like...

  --<--   --<--   --<--  
|       |       |       |
a -->-- b -->-- c -->-- d -->-- null
|                       |
|----------->-----------|
 -----------<-----------

Now I can traverse the list more rapidly, especially if I chose the extra link targets carefully (i.e. ensure they always go back/forward half of the offset of the item they point from in the list length). I then find the rough interval I want with these links, and use the normal links to find the item.

This is a good example of why I hate software patents. It's eminently obvious stuff, wrapped in florid prose to confuse people.

Answer 6

One source of the patent is this. There are, it appears, two claims, the second of which is more nearly relevant:

A computer implemented method for organizing and searching a set of related records, wherein each record includes:

i) a fixed ID field; and

ii) a variable ID field; the method comprising the steps of:

(a) generating first and second sets of link pointers, wherein the first set of link pointers points to successor elements of the set of related records when the records are ordered with respect to the fixed ID field, and the second set of link pointers points to predecessor elements of the set of related records when the records are ordered with respect to the fixed ID field;

(b) generating third and fourth sets of link pointers, wherein the third set of link pointers points to successor elements of the set of related records when the records are ordered with respect to the variable ID field, and the fourth set of link pointers points to predecessor elements of the set of related records when the records are ordered with respect to the variable ID field;

(c) generating first and second sets of field pointers, wherein the first set of field pointers includes an ordered set of pointers that point to every Nth fixed ID field when the records are ordered with respect to the fixed ID field, and the second set of pointers includes an ordered set of pointers that point to every Nth variable ID field when the records are ordered with respect to the variable ID field;

(d) when searching for a particular record by reference to its fixed ID field, conducting a binary search of the first set of field pointers to determine an initial pointer and a final pointer defining a range within which the particular record is located;

(e) examining by linear scarch, the fixed ID fields within the range determined in step (d) to locate the particular record;

(f) when searching for a particular record by reference to its variable ID field, conducting a binary search of the second set of field pointers to determine an initial pointer and a final pointer defining a range within which the particular record is located;

(g) examining, by linear search, the variable ID fields within the range determined in step (f) to locate the particular record.

When you work through the patent gobbledegook, I think it means approximately the same as having two skip lists (one for forward search, one for backwards search) on each of two keys (hence 4 lists in total, and the name 'quad-list'). I don't think it is a very good patent - it looks to be an obvious application of skip lists to a data set where you have two keys to search on.

Answer 7

woah XD this is unbelievable... XD i am also working on 4 dimensional linked list XD

and i was amazed because of my ignorance that it was already made by someone and patented it XD

some answers here are conceptually true.

quad linked list are list which you can traverse backward and forward XD

but i did not used binary search or any searches whatsoever

i did use hash mapping and a search relying on some algebraic equations XD

actually i found something strange with quad linked list so i didn't used it in my project

so i developed a new one using 8 links and a link for itself i know this will sound crazy but i am developing searching without sorting for this data structure

just commenting...