Browse Prior Art Database

Removal of directional links based on direction filter from a collection that is a singly-linked list with O(n) performance

IP.com Disclosure Number: IPCOM000019906D
Original Publication Date: 2003-Oct-09
Included in the Prior Art Database: 2003-Oct-09
Document File: 2 page(s) / 31K

Publishing Venue

IBM

Abstract

Remove directional links based on a directional filter from a collection that is a singly-linked list with O(n) performance. Use a single pass, single iterator, and use only a single new object to minimize the use of memory.

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

Page 1 of 2

  Removal of directional links based on direction filter from a collection that is a singly-linked list with O(n) performance

  When a collection of links implemented as a singly-linked list that requires iterators to parse which become invalid after a single remove operation, the performance of removing 2based on a filtered criteria can require up to an O(n ) algorithm, which can become very costly for large collections. The problem defined is to remove directional link objects based on a directional filter from the collection held by the source. The direction link objects consist of a source and target, which imply direction of source to target, which is considered Outbound when considered from the source's point of view. This problem also has the constraints that the collection of these link objects is implemented as a singly-linked list which may only be stepped through by an iterator object that may only move forward, and once it is used to remove a link from the list, the iterator becomes completely invalid and a new one must be created and started from the beginning. Current algorithms for this 2particular scenario take are approximately O(n ). The solution outlined below shows a good solution in O(n) and most importantly, uses the minimum additional memory.

The solution to the problem is to step through the entire collection from beginning to end only once, O(n), using only one iterator, in one pass, using the following algorithm. This algorithm will use the minimum amount of additional memory that will fit the constraints of this problem.


1. Obtain the collection from the source. Collection coll = source.getLinkCollection();
2. Create one iterator to step through the collection. Iterator iter = coll.createIterator();
3. Start a loop to step through the collection until the end is reached. while(iter.more()){


...

}

4. Within the while loop, step through one at a time, obtaining the next link. Link link = (Link) iter.next(); // Obtain the current element
and move pointer to next.
5. The trick here is to create a...