Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2003-01-17
2004-08-31
Rones, Charles (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06785674
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to methods and systems for structuring data, and more particularly to a method and system for accessing and storing data of a centralized linked list data structure in a computer system.
BACKGROUND OF THE INVENTION
There are many different forms of electronic data structures and each different data structure can have a myriad of implementations. One such data structure is in the form of a “list”—i.e., a grouping of ordered items that can be sequenced. A list that contains respective items and information to reach a prior or a subsequent item is referred to as a “linked list.” With a “single linked list,” each item only has a reference to the next list item. More sophisticated forms of electronic data structures are configured as a “double linked list” or “circular linked list” which consist of a chain of records (called nodes) in which the list is implemented by having a link to an adjacent data item.
FIG. 1
illustrates a double linked list. Each node
1
,
2
,
3
of the linked list includes content
10
,
14
,
18
, and forward/backward pointers
12
,
16
to the next node in the linked list. The last node
3
in the double linked list has a null pointer
20
, i.e., it does not point to another node. A circular linked list is similar to the double linked list illustrated in
FIG. 1
, but differs from the double linked list in that the last node of the linked list has a pointer back to the first node.
The nodes of a linked list are connected like links of a chain; in the case of a circular linked list, the first pointer
12
is connected to last pointer
20
of the list illustrated in FIG.
1
. Unlike the double linked list, in the case of a circular linked list, last pointer
20
points to the first node of the list. A linked list has a head pointer
8
for accessing that specific list. Head pointer
8
has linear links to subsequent nodes
2
,
3
,
4
. The entire list is referenced from head
8
.
Prior art linked list data structures, such as a double linked list and a circular linked list, operate systematically in the following manner. The beginning of the linked list is stored at head
8
, which points to the first node
1
. The first node
1
then points to the second node
2
, and so forth, until reaching the last node
3
. Though the linked list shown in
FIG. 1
illustrates a list with head
8
and three nodes, it will be appreciated that additional nodes may be placed between head
8
and last node
3
. This means that any node
1
,
2
,
3
can be accessed with a start at head
8
and follows the next pointer
12
to get to the queried pointer (
12
or
16
). While this may be systematic, it also means that there is a linear cost of operation—i.e., data is searched one item by item, starting from the beginning of the list and moving toward the end of the list. Thus, operations that rely on data towards the front of a linked list are fast, while operations that rely on data toward the end of a linked list will be slower.
In addition, prior art linked lists are typically implemented in databases, and are therefore stored in permanent memory devices. While such permanent memory devices, such as disk drives and tape drives, can provide large amounts of memory storage, they have proved to be slow in storing and accessing data when large linked lists, or large sets of linked lists, are used. In addition, such linked lists are structured with one or more layers of lists requiring large amounts of sequential data processing time.
An example of a prior art linked list data structures is disclosed in U.S. Pat. No. 6,249,788, entitled “Structure for a Database.” The data structure described therein stores different data within an associated linked list in order to reduce the amount of sequential information searched. The described link list relates to a hierarchy of nodes consisting of a tree-structure which includes a root node, intermediate nodes and leaf nodes. An element of the root node establishes a link to a first intermediate node and then to subsequent intermediate node(s), which in turn link to a plurality of link nodes. Thus, such associated linked lists include sequential layers of data storage and therefore often require a great deal of processing time to search data of the linked list.
Prior art linked list data structures, such as that disclosed in U.S. Patent Application Publication No. 2002/0004793, entitled “Method and Apparatus for Organizing Data by Overlaying a Searchable Database with a Directory Tree Structure,” assign multiple links between nodes. Pointers are used to link related data items. However, searching related data items still follows a branched path across several child nodes before returning to a parent node. Each step in the process requires added processing time. Moreover, when pointer bugs occur, it is often difficult to identify where the crash has occurred. Each linked must be sequentially tested until the bug is found. Thus, the debugging process can be both time and labor intensive.
Accordingly, there remains an unmet need in data structures for a fast, efficient and reliable data structure which does not suffer from the drawbacks described above.
SUMMARY OF THE INVENTION
In accordance with an embodiment of the invention, a central linked list comprises a parent node which is situated at the center of a plurality of child nodes. Each child node has two double linked list pointers. One pointer points to the next child node, and the other pointer points to the parent node. Thus, matched data obtained at several child nodes moves back to the parent simultaneously.
In accordance with another embodiment of the invention, the parent node contains the memory address and name of central linked list, a description of central linked list, and a description of the relationship between other parent nodes, as well as the relationship between each child node to its specific parent node. Each child node contains a node address, an attribute comprised of some or all of the stored data field and a link to the full data content that may reside on a file or in a database.
In accordance with yet another embodiment of the invention, memory storage of the structure information is stored in system memory, such as, random access memory (RAM). Thus, searching and comparison operations may be accomplished without the need to access data stored by a hard disk.
REFERENCES:
patent: 5488717 (1996-01-01), Gibson et al.
patent: 6249788 (2001-06-01), Ronstrom
patent: 6480849 (2002-11-01), Lee et al.
patent: 6581063 (2003-06-01), Kirkman
DeWitt Timothy R.
DeWitt Roggin, PLLC
InteliTrac, Inc.
Rones Charles
Wu Yicun
LandOfFree
System and method for structuring data in a computer system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for structuring data in a computer system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for structuring data in a computer system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3294397