Home » Data Structure Tutorial

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions