Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-09-15
2004-02-03
Rones, Charles (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C709S218000, C709S213000
Reexamination Certificate
active
06687699
ABSTRACT:
The present invention generally relates to a system and method for tracking computer data. More particularly, it relates to a system and method that tracks computer data using at least one table having all the node entries for each data set, wherein each node entry has a linked list identification, a previous pointer, and a next pointer.
Linked lists are commonly used to keep reference positions for a computer data set. Nodes entries are generally found in the linked lists, and they are reference points of data elements. Nodes entries are updated as data structure changes, which allows the computer to track the various positioning points of the elements as the data structure changes. Under a doubly-linked list implementation, each node entry has both a previous pointer and a next pointer. The previous pointer indicates the previous linked position of the node entry, and the next pointer indicates the next linked position. Two doubly linked list methods are known in the art.
Referring to
FIG. 1
, a prior method for implementing doubly linked lists is shown. A node entry
10
generally includes a next pointer
14
and a previous pointer
16
. Under this method, the node entry
10
is typically placed in the first few bytes of the data structure of the actual data set
12
. The general order of the data structure begins with a next pointer
14
, a previous pointer
16
, and data set
12
respectively, which will all be referred to as a data element
19
. Data elements A, B, and C are shown in
FIG. 1
as an example, and all the data elements
19
are kept in a single linked list
18
. For each data set
12
, a node entry
10
of a next pointer
14
and a previous pointer
16
is located at the beginning of the data structure. The start of the node entry
10
and the start of the data set
12
share the same address in memory. The tracking of the data is straight forward. For example, as indicated by the arrows, the next pointer
14
of data element A refers to data element B, and next pointer of data element B refers to data element C. Similarly, in the reverse direction, the previous pointer
16
of data element C refers to data element B, and the previous pointer of data element B refers to data element A.
Because of this given arrangement, a node entry
10
can be easily deleted by redefining the node entries. For example, to delete data element B from the linked list
18
involves only two steps. The next pointer of data element A must be redefined to refer to the data element C. Similarly, the previous pointer of data element C must also be redefined to refer to data element A. More specifically, the program notations are “B.prev.next=B.next” and “B.next.prev=B.prev”. This arrangement provides a constant time delete O(1), meaning that the time it takes to delete a node entry
10
is independent of how many nodes are in a single linked list
18
. The time remains constant regardless of the number of data elements
19
in a linked list
18
. As a result, the node entries
10
can be updated more easily and efficiently.
One problem with this method is that it allows the data element
19
to exist only in one linked list
18
at a time. Although the module processing speed is faster, it is less preferred for more complex data implementations because data elements cannot exist in multiple linked lists.
Turning to
FIG. 2
, another prior method for implementing doubly linked lists using multiple lists is shown. Rather than having the node entry
10
be embedded in the actual data set
12
, this method uses a data pointer
20
, which basically makes the node entry point to the actual data set. Unlike the node entry
10
in the previous method having both a next pointer
14
and a previous pointer
16
, the node entry in this method has a next pointer, a previous pointer and a data pointer
20
. As shown, multiple linked lists
18
can be used and a particular data set
12
can belong to multiple lists at the same time. Two linked lists L and M are shown as an example. In practice, thousands of linked lists
18
may be used.
However, a problem with this method is that in order to delete a data set
12
from a linked list
18
, all the node entries in the linked list must be searched, which can be time consuming when hundreds of node entries in a single linked list must be searched to find the data set's corresponding node entry
10
. For example, to delete data set B from linked list L, all the node entries must be searched in linked list L in order to find and delete the node entry with a data pointer to data set B. This method uses a O(n) delete time, wherein n is the number of node entries in a single linked list. In other words, the delete time factor of a node entry
10
is dependent upon the number of node entries in a linked list.
One problem with this method is that it is extremely inefficient and greater processing resources are needed to complete the same tasks as the previous method. As a result, the module processing speed is sacrificed because of the complexity.
Accordingly, a primary object of the present invention is to provide an improved system and method for tracking computer data that allows a data element to belong to multiple linked lists while the processing time is independent of number of data elements in any of the linked lists.
Another object of the present invention is to provide an improved system and method for tracking computer data that can update node entries more easily.
Still another object of the present invention is to provide an improved system and method for tracking computer data that is more efficient in terms of processing speed.
Yet another object of the present invention is to provide an improved system and method for tracking computer data that allows for data to belong to multiple linked lists without sacrificing processing speed.
BRIEF SUMMARY OF THE INVENTION
The present invention generally relates to a system and a method for tracking computer data. More particularly, it relates to a system and method that tracks computer data that uses at least one table having all the node entries. Each node entry has a linked list identification, a previous pointer, and a next pointer. With the use of the table and node entries having a linked list identification, the present invention is able to provide an improved system and method for tracking computer data that allows data to belong to multiple linked lists but without sacrificing processing speed.
The present invention includes a system having at least one data set and at least one node table for each data set. Furthermore, it includes at least one node entry for each node table, wherein each node entry having a linked list identification, a previous pointer, and a next pointer. Lastly, at least one linked list referencing said at least one node entry is also included.
The present invention further includes a method including steps of creating at least one node entry designating a previous pointer and a next pointer for each data set, maintaining at least one node table having all the node entries for each data set, assigning said linked list identification to each said node entry, and maintaining at least one linked list for each said linked list identification.
REFERENCES:
patent: 5295261 (1994-03-01), Simonetti
patent: 5390318 (1995-02-01), Ramakrishnan et al.
patent: 5488717 (1996-01-01), Gibson et al.
patent: 5664179 (1997-09-01), Tucker
patent: 5717916 (1998-02-01), Verma
patent: 5737732 (1998-04-01), Gibson et al.
patent: 5875352 (1999-02-01), Gentry et al.
patent: 6003033 (1999-12-01), Amano et al.
patent: 6185569 (2001-02-01), East et al.
patent: 6243783 (2001-06-01), Smyers et al.
Rones Charles
Veillard Jacques
LandOfFree
System and method for tracking computer data 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 tracking computer data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for tracking computer data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3302859