Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Recursively referenced linked lists

IP.com Disclosure Number: IPCOM000038321D
Original Publication Date: 2005-Jan-31
Included in the Prior Art Database: 2005-Jan-31
Document File: 2 page(s) / 111K

Publishing Venue

IBM

Abstract

A method is disclosed to efficiently store large amounts of data from an input stream without prior knowledge about its final size, while allowing fast access anywhere within the stored data. The storage structure is based on a particular form of linked lists, in which each link contains more than one element. Fast access of the data is achieved by storing references to each link of this list within another list, itself referenced by another, and so on until the last created list contains only one link.

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 57% of the total text.

Page 1 of 2

Recursively referenced linked lists

    We propose a solution to efficiently store data of unknown amounts, while requiring fast access to any element of this data. Since the use of a simple array of fixed size introduces risk of vastly unused memory and overflow, a linked list is preferred, but it still has drawbacks: much of the used memory is dedicated to the definition of the data structure (in each link, at the least, the address of the next link in the chain is stored), it implies frequent memory allocations that considerably slow down the storing process and cannot provide fast access to the data, since all links are scanned until the desired position is reached.

    In order to minimise the two firstly mentioned inconveniences, a particular type of linked list, which we call L, is used as base. It differs from a traditional linked list in the fact that instead of storing a single element in each link of the list, an array of elements is stored. Furthermore, the links do not need to store arrays of same size. Using only this structure does not permit to access the data as rapidly as intended, since the process remains similar to the one used for traditional lists.

    To avoid having to read each link preceding the pertinent one, a second list, called A1,is created, storing the addresses of the links of L, accompanied by the position in the data stream of the first element in each of these links (figure 1). Each link of A1 stores a number j of such couples (link_address,offset_of_first_element ). Once A1 contains more than one link, a second list A2 is created, storing the addresses of the links in A1 and the offset of the first element in the data of the links whose addresses are stored in A1. Once this contains more than one link, another list A3 is created in the same fashion. This recursive procedure is repeated so that t...