Array in Data Structure
Table of Content:
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 consecutive numbers.
- 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 notations.
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 Base(LA). 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[1932]) = 200
LOC (Auto[1933]) = 204
LOC (Auto[1934]) = 208
The address of the array element for the year K = 1965 can be obtained by,
LOC(AUTO[1965]) = Base (AUTO) + w (1965 - lower bound)
= 200 + 4(1965 —1932)
= 332
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.