Home » Data Structure

Introduction to Data Structure

This section is a part of Data Structure Tutorial - Introduction to Data Structure. Here, we will learn about its basic concept, terminologies etc.

What is Data Structure?

• Data structure is a logical organization of data.
• It specifies how to store and access the data from memory.

Data structure operations

• Traversing Accessing each element exactly once, is knows as traversing. It is also known as visiting.
• Insertion Adding a new element to data structure.
• Deletion Removing an element from the data structure.
• Searching Finding the location of an item in data structure.
• Sorting Arranging the items in ascending or descending order is known as sorting.

Types of Data Structure

There are two types of Data Structure: Linear Data Structure and Non Linear Data Structure.

Linear data structure: A data structure is said to be linear if items are arranged in linear or sequential format.

Non-linear data structure: Non-linear data structure does not support sequential format.

Linear data structure:

• Array
• Stack
• Queue
• Linked List

Non-linear data structure:

• Tree
• Graph

Arrays

• Array is a list of a finite number of homogeneous data items (i.e. data items of the same type).
• Array is also known as subscripted variable.
• Array can be accessed by index.
• Number of elements in array is known as length of array.
  LENTH = UB – LB + 1
  Where UB is upper bound and LB is lower bound. Here length = UB when LB = 1.
• The element of an array A may be denoted by subscript notation.
  A1, A2, A3, ……. An
  By the parentheses notation
  A(1),A(2), …….. A(N)
  By the bracket notation
  A[1],A[2],A[3], ….A[N]
  

Representation of linear arrays in memory

• Suppose A be an array in the memory. As we know that memory of the computer is simply a sequence of addressed location.
  LOC(A[i]) = address of element A[i] of the array A
  

              1000
              1001
              1002
              1003
              Computer Memory
              

• Address of first element of array is known as base address.
• Using base address, the computer calculates the address of any element of array.
  LOC(A[i]) = base(A) + w ( I – lower bound)
  Where w is the number of words(bytes) per element of array.
• Arrays are similar to matrices. There can be single dimensional array or multidimensional array.
  Ex:
  int a[5];
  
• Here int is data type, and a is array name and 5 is the size of array. All element of the array must be of same data type. In this sense, it is a homogenous data structure.
• The allocation of information about an array is fixed at compile time. Its entry is done inn symbol table at compile table.
• During execution the memory space is allocated for array. For all element of array continuous space is allocated. The array name is the start address of this memory.

Two Dimensional Array

A two dimensional array is like a two dimensional matrix, that has rows and columns. An integer 2D array with 10 rows and 20 columns can be declared as:

int a[10][20];

Here 10 is number of rows and 20 is number of columns.

Storing In Main Memory

A two dimensional matrix is represented in two dimensions. It is to be stored in the main memory, which is one dimensional. Hence some conversion processes has to be adapted from two dimensions to one dimension. There are two conversion schemes.

1. Row major storing.
2. Column major storing.

Row major implementation

In row major storing elements are stored, row by row, first store first row and then second row and so on.

Q.1: see the declaration:

#define RMAX        10
#define CMAX        20        
    

What is the address of element a[r][c] by using row major storing?

Ans: Location of a[r][c]
a + (r*CMAX+c)
Where array name "a" is the base address of the array. Only CMAX is needed, not RMAX.

Column major implementation

In column major storing elements are stored, column by column, first store first column and then second column and so on.

Q.1: see the declaration:

#define RMAX        10
#define CMAX        20
    

What is the address of element a[r][c] by using column major storing?

Ans: Location of a[r][c]
a + (c*RMAX+r)

Where array name “a” is the base address of the array. Only RMAX is needed, not CMAX.