Browse Prior Art Database

Non Dequeueable Dummy Chain Element

IP.com Disclosure Number: IPCOM000079283D
Original Publication Date: 1973-Jun-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 2 page(s) / 34K

Publishing Venue

IBM

Related People

Schulze, ES: AUTHOR

Abstract

With a double-threaded chain, each chain element contains at least two pointers. One, called the forward pointer, points to the "next element" in the chain and the other, called the backward pointer, points to the "previous element" in the chain. Characteristics of double-threaded chains are: 1. A dummy element at the end of the chain is used to facilitate manipulation of the chain.- The dummy element must always be present at the end of the chain. 2. Quick dequeueing of any given chain element, called the "subject element", is done by the following two step procedure: a) Set the forward pointer of the previous element equal to the forward pointer of the subject element. b) Set the backward pointer of the next element equal to the backward pointer of the subject element.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 90% of the total text.

Page 1 of 2

Non Dequeueable Dummy Chain Element

With a double-threaded chain, each chain element contains at least two pointers. One, called the forward pointer, points to the "next element" in the chain and the other, called the backward pointer, points to the "previous element" in the chain. Characteristics of double-threaded chains are: 1. A dummy element at the end of the chain is used to facilitate manipulation of the chain.- The dummy

element must always be present at the end of the

chain. 2. Quick dequeueing of any given chain element, called the "subject element", is done by the following two

step procedure: a) Set the forward pointer of the previous element equal to the forward pointer of the subject element. b) Set the backward pointer of the next element equal to the backward pointer of the subject

element.

Key to this algorithm is the locating of the "previous element" and "next element" directly from the backward and forward pointers, respectively, in the subject element.

To prevent the accidental dequeueing of the dummy element, the subject element, prior to any dequeue action, is usually first examined to ensure that it is not the dummy element.

The above dummy element check can be eliminated and improved by having the forward pointer of the dummy element point to itself. Thus, the double- threaded chain would appear as shown in the drawing.

With this arrangement, the aforementioned dequeueing algorithm can be executed even though the dummy element was acciden...