METHOD AND APPARATUS FOR MAINTAINING A LINKED LIST

A linked list has an associated auxiliary data structure, containing external references to the linked list which are used by updating tasks. The auxiliary data structure is used to block subsets of the linked list from being altered by other tasks. Preferably, the linked list is doubly-linked, and list maintenance is accomplished using object-oriented programming techniques. The auxiliary data structure is an object, which comprises iterator objects, including inspector objects and mutator objects, blocker objects and view objects. Iterator objects are used by clients to access the linked list externally. An inspector object traverses the list without changing it; while a mutator alters the list, and may traverse it as well. Both inspectors and mutators have associated view objects, which contain the pointers to the actual list elements. Mutators also have associated blocker objects, which block access to selected list elements. In operation, a mutator object blocks off a portion of the linked list by altering pointers so that they point to the blocker object, the blocker object containing additional pointers by-passing the blocked list portion. Other inspectors may thereafter traverse the list through the by-passed portion. By blocking only a relatively small portion of a large linked list, multiple tasks may concurrently access different list elements and perform separate list updates.