Browse Prior Art Database

Reduction of Link List Searching Time by using Sort and Searched Pointers

IP.com Disclosure Number: IPCOM000109027D
Original Publication Date: 1992-Jul-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 4 page(s) / 117K

IBM

Related People

Medero, JL: AUTHOR

Abstract

Searching has been a topic that has been studied for many years and different solutions have been presented. One of the obvious solutions is to use binary trees to reduce the searching time from a time of O(n) to O(logn). If m items are to be searched, then the time will be O(mlogn).

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

Reduction of Link List Searching Time by using Sort and Searched Pointers

Searching has been a topic that has been studied for many
years and different solutions have been presented.  One of the
obvious solutions is to use binary trees to reduce the searching time
from a time of O(n) to O(logn).  If m items are to be searched, then
the time will be O(mlogn).

For linklists, the search time for a single item will also be
O(n) using the trivial algorithm.  When m items are to be searched,
the time will be O(mn).

In applications such as VLSI, these searches are common.  Items
in one list need to point to items in another list.  An example of
this is the relationship between circuits and pins.  Each circuit
contains multiple pins, and each pin has to point to the circuit that
contains it.  Since the number of circuits and pins is normally in
the tens of thousands and growing, an efficient algorithm needs to be
used to do the searches and interconnections between pins and
circuits in as short a time as possible.

A solution that has been used in a graphical placement program
is presented here.  The search time has been reduced from the trivial
solution square time, to a solution that is limited by the time of
the sorting algorithm used.

The trivial search time for an item in a linklist is of the
order O(n), when m items are to be searched, then the search takes
time O(mn).  If two lists exist, one with n items and another with m
items (n>m), the search time can be reduced to a time in the order of
the sorting algorithm to have the lists ordered by the same key.

An algorithm to do this is presented below.  The algorithm can
ones.
SORT (m_list by key field in n_list)
m_item = (first item in m_list)
last_searched = (first item in n_list).
WHILE (last_searched < > NULL and m_item < > NULL)
IF (m_item->search_key < = last_searched->search_key) THEN
m_item->n_list_ptr = last_searched
ELSE
m_item->n_list_ptr = NULL
m_item = (next item in m_list)
END
ELSE
last_searched = (next item in n_list)
ENDIF
ENDWHILE

First, to save time, the smaller list is sorted.  Then the
first item is picked from the li...