# AN INTRODUCTION TO DATA STRUCTURES IN C

0
94 INTRODUCTION

Data structure is a method to store and collect data in a computer’s memory. These data will be efficiently used when they are needed. There are different ways to arrange the data like logical or mathematical models for a group of data. This is known as a data structure in C.

The data structure is divided into two categories:

• Linear Data Structure
• Non-linear Data Structure

LINEAR DATA STRUCTURE IN C

If the elements present in the data structures in C follow a specific order, this means that the data structure is called linear.

Examples for linear data structure:

• Array
• Stack
• Queue

NON-LINEAR DATA STRUCTURE IN C

If the elements present in the data structure don’t follow any order, this means that the data structure is called non-linear. This type of data structure is mostly used to represent hierarchical relationships between elements.

Examples for non-linear data structure:

• Tree
• Graph
• Hashing

ARRAY

An array is a linear data structure with a collection of similar data items that are stored under a common name. A value in an array is identified by an index enclosed in square brackets with the array name.

Types:

• One-Dimensional Arrays
• Two-Dimensional Arrays
• Multi-Dimensional Arrays

One-Dimensional Arrays: The collection of data items that are stored under a one variable name using only one index, such a variable is called the one-dimensional array.

Two-Dimensional Arrays: Two-dimensional arrays are used in situations where a table of values needs to be stored in an array.

Multi-Dimensional Array: Similarly, like one and two-dimensional arrays. ‘C’ language allows multidimensional arrays. The dimension with three or more called multidimensional arrays.

A linked list is a linear data structure that is used to store a collection of data. The pointers are used to connect the successive elements. The last element of the linked list is NULL. The size of the linked list can be modified during the execution of the program.

Operations:

• Insert – used to insert an element into the list
• Delete – used to remove the element in a specified position
• Delete List – used to remove all the elements in the list
• Count – used to return the total number of elements present in the list

Types:

Singly Linked List: This list contains a number of nodes. Each node has a pointer to connect the following element.

Doubly Linked List: In this list, a node can navigate in both directions. Each node has two pointers since the right pointer connects the left pointer of the following element. The left pointer of the head is NULL.

Circular Linked List: This list does not have any NULL value. In this list pointer of the last node is pointed to the head.

STACK

A stack is a linear data structure in C that is used to insert and delete an element at top of the stack. When the element is inserted it is added in the last end and deletion is done in the first one. This method is called Last In First Out(LIFO).

Operation:

• Push – used to insert data
• Pop – used to remove last inserted element
• Top() – used to return the last inserted element without removing it
• Size() – used to return the total number of elements in the stack
• IsEmptyStack() – used to check whether the stack is stored with elements that are not
• IsFullStack() – used to check whether the stack is filled with the element are not

QUEUE

The queue is a linear data structure like a stack. This follows FIFO(First In First Out) method. When the element is inserted it takes place in the end position of the queue and when the element is deleted it takes place in the front position of the queue.

Operations:

• EnQueue – used to insert an element at the end position of the queue
• DeQueue – used to remove the element at the front position of the queue
• Front() – used to return the front element without deleting it
• QueueSize() – used to return the total number of elements present in the queue
• IsEmptyQueue – used to check whether the queue has elements or not

TREE

A tree is a non-linear data structure. It represents the hierarchical relationship among various elements. The node with node parent is called as root. The connection between the parent to child refers to the edge. Leaf node is the one that doesn’t have any children.

BINARY TREE

A tree with zero nodes, one child, or two children is known as a binary tree.

Types:

• Strict Binary Tree
• Full Binary Tree
• Complete Binary Tree

Strict Binary Tree: A binary tree with each node has two children or no children

Full Binary Tree: A binary tree with each node has two children and all leaf nodes at the same level

Complete Binary Tree: A binary tree with all leaf nodes are at height h or h-1 and also without any missing number in the sequence

Operations:

• Adding an element into a tree
• Removing an element from a tree
• Searching for an element
• Traversing the tree
• Finding the size of the tree
• Finding the height of the tree

GRAPH

A graph is a pair (V, E), where V is known as vertices(set of nodes), and E is known as edges(collection of pairs of vertices). Vertices are the position of elements and edges are the storage elements.

Types:

• Directed edge or Undirected edge
• Directed graph or Undirected graph
• weighted graph or Unweighted graph

Application of Graph:

• Transportation networks
• Computer networks
• Databases

HEAP

A tree with special properties is called a heap. Heap property is said to be the value of a node that must be greater than equal to the values of its children. There is another property that the heap should form a complete tree.

Types:

• Min heap
• Max heap

Min heap: The children value must be greater than or equal to the values of its node

Max heap: The children value must be lesser than or equal to the values of its node

Binary heap

In this type of heap each node is consist of two children

• Parent of a node: i-1/2
• Children of a node: 2*i+1 (left children), 2*i+2 (right children)

HASHING

Hashing is a method used to store and retrieve information as quickly as possible. It is used to implement the symbol tables and to optimize the searches.

Operations:

• CreatHashTable: Creates a new hash table
• HashSearch: Searches the key in hash table
• HashInsert: Inserts a new key into hash table
• HashDelete: Deletes a key from hash table
• DeleteHashTable: Deletes the hash table

Techniques:

Static Hashing: It is useful when the data is fixed. In this type of hashing, the set of keys is fixed and the number of primary pages is fixed.

Dynamic Hashing: It is used when the data is not fixed. In this type of hashing, the set of keys can change dynamically.

This brings us to the end of the blog on Data Structures in C. We hope that you were able to gain a better understanding of Data Structures in C and are now better acquainted with the concept.