Array in data structure

This tutorial covers the array in data structure. Array definition, array in c and different concepts of array in programming such as array declaration, types of array in data structure, two dimensional array, one dimensional array , sparse matrix etc are explained in this tutorial.


What is Array ? OR Array Definition

Array in data structure is collection of items having same data type stored which are stored in contagious memory allocation. During array definition we should also keep in mind that array in data structure is a user define data type. Array in programming is a best data structure.

Implementation of array in programming is important because of following reasons
  1. a) Most assembly language have concept of array.
  2. b) From an array any other data structure we can be built.

Why do we need array?

In general if we store any data it store at any random location. Data at any 
random location is very tough to retrieve that’s why we need data structure.

Example of an Array

Consider three variable

int  a=10;

int b=20;

int c=30;

In array contain three elements we can write

int  a[3]={10,20,30};

Where 1000, 1002 and 1004 are the addresses where these variable are stored.

Application of array in data structure

Different application of array in data structure are as follows:
  • Array is used to sort the elements.
  • Array can be used to perform the matrix operations.
  • Array is used to implement the cpu scheduling.
  • Array can be used in recursive function.

Properties of an Array

There are following properties of an array.
  • Each element is to the same size.
  • Element are stored contagious, with the first element stored at the smallest memory address.
  • Starting address of array is called base address.
  • By default array is start from 0 and the element number is an address.

Memory as an Array

Memory can also be view as an array . Memory is either Byte addressable or word addressable
  • Byte Addressing: if each byte has a unique address, we have byte addressing.
  • Word Addressing: if each word is given unique address, but the byte within a single word cannot be distinguished.

Types of array in data structure

In general array may be of following types of array in data structure.
  • One Dimension array (1-D)
  • Two dimensional array (2-D)
  • Lower Triangular matrix array
  • Upper Triangular matrix array
  • Sparse matrix array .
Some other types of array in data structure are Tridiagonal matrix array, Z matrix array and Toeplitz matrix array.

Order of an Array

An array can be ordered in two way
  • Row major order
  • Column major order
Consider the matrix as shown in following figure.


Row major array for this matrix is

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Column major order is

1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16

(i) One dimensional array

One dimensional array in data structure or Single-Dimensional array can be think as the” list of variables which have similar data types” and each variable can be distinctly accessed by specifying its index in square brackets preceded by the name of that array

int  a=10;

int b=20;

int c=30;

In array contain three elements we can write

int  a[3]={10,20,30};


Location of One D Array

Consider the array declaration : A[Lb……………..Ub], base address is BA, C-size of an array and Lb and Ub are the lower and upper bound of an array. Then address of the ith element can be find out using following formulas

                                     Loc(a[i]) = BA + (i - Lb) * C

Example: Suppose following array with its base address 1000 is given then address of the element at a[4] will be 1008,  

int a [5] = {10,20,30,40,50}

    Loc (a4) = BA + ( i - Lb) * c
                   = 1000 + ( 4 - 0 )*2
                   = 1000 + 8
                   = 1008

(ii) Two dimensional array

What is two dimensional array?

A two dimensional array in data structure is an array which is stored in the form of the row-column matrix, where the first index indicate the row and second index indicates the column. 

The second or the rightmost index of an array changes very fast as compared to first or left-most index while accessing the elements of an array.

Example - int a [4] [4] . This declaration represents an array which consist of 4 rows and 4 column.

Location of 2 D array in Row Major Order

int a[4] [4]=   A[Lb1………Ub1,Lb2………Ub2]

  Base Address =BA=1000

   S- size of any element

   No of rows- Ub1-Lb1+1

   No of columns- Ub2-Lb2+1

    LOC (aij)= BA+ [(i-lb1)*  no of column + (j- lb2)] * S

Example: Suppose if we want to find out the address of the element 32 then it will be calculated by above formula as follow:

    loc (a32) = BA+[(i-lb1)*column+(j-lb2)] * s
                    = 1000+[(3-1)*4+(2-1)]*2
                    = 1000+[8+1]*2
                    = 1000+18
                    = 1018

   So  the location of a32 in 2-d array,RMO form is 1018.

Location of 2 D Array in Column Major Order

int a [4] [4]

   a(Lb1…….Ub1,Lb2……Ub2)

   CMO

   Base address

   S- size of any element

   no of rows- Ub1-Lb1+1

   no of columns- Ub2-Lb2+1

         Loc(aij)= BA + [(J-lb2)*rows + (i-Lb1)] * S

Example

a[1…….4,1…….4]

     CMO

     BA- 1000

     Loc(a34) = BA +[(J-lb2) * no of rows + (I-Lb1)] *s
                     = 1000+[(4-1)*4+(3-1)]*2
                     = 1000+[12+2]*2
                     = 1000+28
                     = 1028
   So that the location of a34 in 2-d array, CMO form is 1028.

(iii) Lower triangular matrix 

 A[Lb1……Ub1,Lb2…….Ub2]

   LTM



   Row major Order for this lower triangular matrix is

    1 2 6 3 4 8 4 7 5 9 5 3 2 6 3
   
Base address

S- size of array

Loc (aij) = BA + [((i - Lb1)( i- Lb1+1)/2) + (j - Lb2)] * S

 A[lb1……..ub1,lb2……..ub2]

   LTM

   Column Major Order for this lower triangular matrix is

   1 2 3 4 5 6 4 7 3 8 5 2 9 6 3
   
Base address

size of array

loc(ai,j) = BA + [(col)(col+1)/2 –(ub2-j+1)(ub2-j+1+1)/2 + (i-j)] * s

(iv) Upper Triangular Matrix

   A[Lb1……Ub1,Lb2……Ub2]

    UTM


    Column Major Order

    Base address

    S- size of array

 LOC (aij) = BA + [((j – lb2)(j-lb2+1)/2) + (i-lb1)] * S
  • A[lb1…..ub1,lb2……ub2]
    UTM

   RMO

    Base address

    Size of array

LOC(ai,j) = BA + [(ub1-lb1+1)(ub1-lb1+1+1)/2 – (ub1-i+1)(ub1-i+1+1)/2 + (j-i)] * s

What is Sparse Matrix ?

Sparse matrix is a matrix which has most of the its elements of as 0 value, then it is called a sparse matrix.

Why to use Sparse Matrix instead of simple matrix ?

There are following reasons to use the sparse matrix

  • Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to store only those elements.
  • Computing time:Computing time can be saved by logically designing a data structure traversing only non-zero elements.
                            
In array this matrix can be represented as


Limitations of Array

There are following limitation of an array:
  • The dimension of an array is determined the moment the array is created, and cannot be changed later on.
  • An array is a static data structure. After declaring an array it is impossible to change its size. thus sometime memory spaces are misused.
  • Each element of array are of same data type as well as same size.we can not work with elements of different data type.
  • In an array the task of insertion and deletion is not easy because the elements are stored in contiguous memory location.
  • Array is a static data structure thus the number of elements can be stored in it are somehow fixed.

COMMENTS

Name

addressing modes types,1,advance-java,2,advancejava,1,aktu entrance exam,1,aktu exam schedule,1,ASP,1,bare machine,1,base register and limit register,1,C Programming,13,C Plus Plus,1,C Programming,6,C Programming MCQ,2,C Programming Questions,2,C programming study material for gate exam,10,Cache Memory,1,CBNST Program,1,Childcare,1,CJ,2,Cloud Computing,1,COA GATE Questions,1,components of use case diagram,1,Computer Architecture,2,Computer architecture based questions for gate exam,11,Computer Network,4,Computer Network Study Material,2,Computer network study material for gate,2,Computer Networks,6,Computer networks GATE Questions,1,Computer Science Study Material for Gate,19,computer science study material for gate exam,32,content based image retrieval content based image retrieval system,1,contiguous memory allocation,2,Core Java,8,COre Java Interview Questions,1,core java interviews questions,1,cyber crime report,1,Cyber crime status,1,cybercrime and security,1,cybercrime examples,1,Data Mining,1,Data Structure,2,Data Structure Questions,1,Data Transmission Architecture,1,Data Transmission in wsn,1,DBMS,5,dbms question paper,1,DE,1,Digital Electronics,1,DS,1,dynamic linking,1,dynamic linking in memory management,1,Dynamic memory allocation in c,1,Electroencephalogram,1,file management in operating system notes,1,FOC,1,Fundamenatl of Computer,1,Gate 2017,5,Gate 2017 Admit card,1,Gate 2017 Exam Schedule,1,Gate 2017 Syllabus,1,gate 2018,1,gate cse study material,1,gate practice set,10,gate study material for computer science,16,Gate study material for computer science 2017,1,GatePreviousYear,1,General,3,HCL Aptitude Test,1,HR Interview Questions,1,HTML,4,Image Processing,1,Important Date of Gate 2017 Exam,1,Information Security Policy,1,internal and external fragmentation,1,JS,1,lagrange's interpolation formula,1,lagrange's interpolation formula examples,1,MComputing,1,memory fragmentation,1,memory management,1,memory management questions and answer in os,1,Motivational,4,NCER,2,Numerical Techniques Lab,1,OOT,1,Operating System,12,Operating System Gate Questions,1,Operating System Objective Questions,4,Operating System Questions Bank,1,Operating system questions for gate,1,Operating System Study material,2,operating system study material for gate exam,16,Operating system tutorial,2,page swapping,1,paged memory allocation,1,paged memory allocation in operating system,1,paging technique of memory management .paging technique,1,paging technique of memory management program in c,1,Pointer in C,4,Process based question for gate,1,Quiz on non conventional energy resources,1,Regression testing,1,relocation in memory management,1,relocation registe,1,relocation register,1,resident monitor,1,resident monitor in operating system,1,routing table,1,segmentation in memory management,1,segmentation in memory management in operating system,1,Servlet,1,session tracking,1,session tracking in java,1,session tracking in servlet,1,Software Engineering,10,Software Engineering baes study material for gate,1,software engineering interview questions,1,Software Quality Assurance,3,software verification methods,1,SPM,1,Stack,1,Structure in C,1,Study Material for gate Computer Science,9,swapping in memory management,1,swapping in operating system,1,TCS Code Vita,1,TCS Interview Questions,1,Technical Interview,1,Technical Questions from DBMS,1,Thrashing in Operating System,1,Threads concept in operating system,1,Tips to Learn Coding,1,Top 30 Core Java Interview Questions with Answer,2,top down approach,1,top down approach in programming,1,Types of operating system,1,UML,1,use case diagram explanation,1,website uses cookies,1,what is cookies website,1,What is process control block ?,1,what is software testing?,1,Wireless Sensor Network,3,worst fit algorithm for memory allocation,1,XML,1,
ltr
item
Computer Science Junction: Array in data structure
Array in data structure
This tutorial covers the array in data structure. Array definition, array in c and different concepts of array in programming such as array declaration, types of array in data structure, two dimensional array, one dimensional array , sparse matrix etc are explained in this tutorial.
https://2.bp.blogspot.com/-SqmOSCo-JeI/W_5ZUo6rJYI/AAAAAAAABG8/uWDa4m7LzO4SUnzkmS1i2Rn2aIQcfJ7BgCLcBGAs/s400/arrayindatastructure.jpg
https://2.bp.blogspot.com/-SqmOSCo-JeI/W_5ZUo6rJYI/AAAAAAAABG8/uWDa4m7LzO4SUnzkmS1i2Rn2aIQcfJ7BgCLcBGAs/s72-c/arrayindatastructure.jpg
Computer Science Junction
https://www.computersciencejunction.in/2018/11/array-data-structure.html
https://www.computersciencejunction.in/
https://www.computersciencejunction.in/
https://www.computersciencejunction.in/2018/11/array-data-structure.html
true
425357657003182083
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share. STEP 2: Click the link you shared to unlock Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy