Array in Data Structure
Array is a linear data structure. A data structure is said to be linear, if its elements form a sequence or in other
words a linear list. There are two basic Ways of representing such linear structures in memory. One way is
to have the linear relationship between the elements represented by means of sequential memory locations.
These linear structure are called array. The other way is to have the linear relationship between the elements
represented by means of pointers or links. These linear structure are called linked list.
A linear array is a list of a finite number n of
homogeneous data elements such that
- The elements of the array are referenced, respectively by an index set consisting of n
- The elements of the array are stored, respectively in successive memory locations. The number n of
elements is called the length or size of array. If not explicitly stated we will assume the index set
consists of the integers 1, 2, ... n. In general, the length or the number of data elements of the array
can be obtained from the index set by the formula
Length = UB - LB + 1
When UB is the largest index, called the upper bound and LB is the smallest index, called lower bound of the array.
Representation of linear array in memory Let LA be a linear array in the memory of the computer.
Recall that memory of the computer is simply a sequence of addressed locations as pictured in Fig. 2. Let us use the
LOC [LA[K]] = address of the element LA[K] of the array LA
As Previously noted, the elements of LA are stored in successive memory cells. Accordingly, the computer does
not need to keep track of the address of every element of LA, but needs to keep track only of the address of the
first element of LA denoted by
and called the base address of LA. Using this addres base
(LA), the computer calculates the address of any element
of LA by the following formula,
LOC (LA[K]) = Base (LA) + w(K-lower bound)
Where, w is the number of words per memory cell for the
array LA. Given, any subscript K, one can locate and
access the content of LA[K] without scanning any other
element of LA.
e.g., consider the array, which holds the number of
automobiles sold each year from 1932 through 1984.
Suppose AUTO appears in memory as pictured in Figure. 2.
Given (by figure)
Base, [AUTO] =200, w = 4
LOC (Auto) = 200
LOC (Auto) = 204
LOC (Auto) = 208
The address of the array element for the year K = 1965
can be obtained by,
LOC(AUTO) = Base (AUTO) + w (1965 - lower bound)
= 200 + 4(1965 —1932)
A collection A of data elements is said to be indexed, if
any element of A, which we shall call can be located
and processed in a time that is independent of K The
above discussion indicate that linear arrays can be
indexed. `Ellis is the very important property of the linear array.