# 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.

- Row major storing.
- 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.

Related Tutorials

- Structured Programming, its Advantages and Disadvantages
- Data Structure types and operations associated with them
- Linear, Binary & Interpolation search
- Array Data Structure
- Introduction to Linked List
- Single Linked list and its basic operations with traversing implementation
- Single linked list insertion
- Single linked list deletion
- Deleting a node from a linked list without head pointer
- Implement union and intersection of two sorted linked lists
- Stack
- Implement of stack using array
- Implementation of Multi Stack in C
- Nesting of parentheses using stack

- Check for balanced parentheses by using Stacks (C++ program)
- Double Stack
- Implementation of Stack using two Queues
- Linear Queue
- Circular Queue
- Double Ended Queue (DeQueue)
- Priority Queue
- Implementation of Queue using two Stacks
- Hashing Data Structure
- Hash functions and its characteristics
- Collisions in Hashing and Collision Resolution Techniques
- Hashing | Separate chaining for collision resolution
- Hashing | Open addressing for collision handling
- Hashing coding problems

Comments and Discussions!