Data Structures and Algorithms Tutorial
Data Structures and algorithms are useful to solving programming puzzles and challenges.
When you encounter a programming problem, it is well worth to learn and understand data structures and algorithms, so that you can see if any of them can solve the problem in efficient way.
In this tutorial, we will go through common algorithms and see their implementation in C#, Java and C++ language. We will also go through common data structures and see their implementation in C.
Data Structures
Data Structure
Overview
Linked List is a simple data structure. Each element in a linked list is called a Node. A node will contain two items, one is data and other item is reference to the next Node.
Doubly Linked List is a linked data structure. Each element in a doubly linked list is called a Node. A node will contain three items, one is data. Second item is reference to the next Node. Third item is reference to the previous Node.
Stack is a linear data structure. It is a container of elements. Elements are removed in a Last In First Out (LIFO) fashion.
Queue is a linear data structure. It is a container of elements. Elements are removed in a First In First Out (FIFO) fashion. It functions similar to a Queue we follow in Restaurants, Airport etc.
Sorting Algorithms
Algorithm Name
Overview
In Bubble Sort, adjacent items are compared and they are swapped if they are not in sorted order. The time complexity of Bubble sort is O(n2)
In Insertion Sort, a sorted sub-array is maintained and each element is scanned and inserted into the appropriate position of the sub-array. The complexity of Insertion sort is O(n2).
In Selection Sort, smallest element is selected from unsorted array and added into the sorted array. The complexity of Selection sort is O(n2).
In Merge Sort we divide the array into two parts and then merge them in sorted order. The complexity of merge sort is O(n log n).
In Quick Sort we will split the array into two subarrays based on a pivot value. One array will contain values less than the pivot and other greater than the pivot. After that we will recursively sort the arrays. Quick sort has average complexity of O(n log n).
Search Algorithms
Algorithm Name
Purpose
In Linear Search the elements in array are searched one after the other for the given search element.
For Using binary search the array must already be sorted. In binary search the value is compared with middle value, and if is is less than middle only the sub-array before the middle is searched. Otherwise it is searched in the sub-array after the middle element.