Abstract

A linked list of items in a sorted order is created and stored in memory. In addition to the linked list of items, an auxiliary array is also created and stored in memory. The auxiliary array contains pointers to a subset of items from the linked list. When a request is received to locate a particular item in the linked list, a binary search is first performed on the pointers stored in the auxiliary array. The result of this search provides a pointer for accessing an entry-point item on the linked list. The entry-point item is either the particular item or is an item that precedes the particular item in the linked list. The linked list is then traversed from the entry-point item rather than from a starting pointer (i.e., head) until the particular item is accessed.