Browse Prior Art Database

Detecting Element Reversal Between Two Linked Lists

IP.com Disclosure Number: IPCOM000120305D
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 3 page(s) / 99K

Publishing Venue

IBM

Related People

Koren, DD: AUTHOR

Abstract

Disclosed is a method for scanning two disjoint linked lists, each of arbitrary length (or two arrays with elements arranged in non-sequential order), and determining if there is at least one instance where elements in the first list, exist, and are reversed in order in the second list. Reversed in order means that some element "Y" appears after some element "X" in the first list, but that element "X" appears after element "Y" in the second list. The number of elements (if any) that separate "X" and "Y" in either list is not important and need not be the same in both lists.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Detecting Element Reversal Between Two Linked Lists

      Disclosed is a method for scanning two disjoint linked
lists, each of arbitrary length (or two arrays with elements arranged
in non-sequential order), and determining if there is at least one
instance where elements in the first list, exist, and are reversed in
order in the second list. Reversed in order means that some element
"Y" appears after some element "X" in the first list, but that
element "X" appears after element "Y" in the second list.  The number
of elements (if any) that separate "X" and "Y" in either list is not
important and need not be the same in both lists.

      This technique is useful, among other uses, in cases of system
locking functions that serialize on two instances of a resource
represented by elements in a linked list, arranged in some order.  In
these cases, it is necessary to know when two or more elements in the
first list, exist, and are reversed in order in the second list.
This knowledge is necessary to avoid possible deadlocks in
serializing on the resources represented by the elements in the two
lists.  In many cases, performance considerations require that this
determination be made as quickly as possible.  The disclosed method
has an execution speed of Order N squared / 4 in the usual case and
Order N squared in the worst case.

      The program method works in the following manner:
      Scans each element in the first linked list.  For each element
processed, the following is performed:
      1.   Scans each element in the second linked list looking for
the element whose data matches the data contained in the element
being processed in the first list.
      2.   If no match is found for any of the elements in the second
list, processing continues with the next sequential list entry in the
first list.
      3.   If a match is found, then the relative position of the
matching element is determined (i.e., how many elements were chained
through to reach the current element).  Then, the relative position
is compared with the relative position of the previous matching entry
(or zero if there was no previous matchi...