Tag: Must Know

Linked List Implementation | Part 2

In the previous two posts (here and here), we have introduced linked list data structure and discussed about various types of linked lists.. We also covered in great detail the various methods to construct a linked list which inserts every new node onto the front of the list. In this post, we will discuss various …

Linked List Implementation | Part 1

In previous post, we have introduced linked list data structure and discussed about various types of linked lists. We have also covered the applications of linked list data structure and its pros and cons with respect to arrays. In this post, we will discuss various techniques in detail to construct a singly linked list.

Introduction to Linked Lists

A linked list is a linear data structure consisting of a group of nodes where each node point to the next node by means of a pointer. Each node is composed of data and a reference (in other words, a link) to the next node in the sequence.  

Binary Search

Given a sorted array of integers and a target value, find out if a target exists in the array or not in O(log(n)) time. If target exists in the array, print index of it.

Quicksort Algorithm

Given an array of integers, sort it using quick sort algorithm.   Quicksort is an efficient in-place sorting algorithm and can be about two or three times faster than its main competitors, merge sort and heapsort when implemented well. 

Merge Sort Algorithm

Given an array of integers, sort it using merge sort algorithm.     Merge sort is an efficient, general-purpose sorting algorithm which produces a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

Bubble sort | Iterative & Recursive

Given an array of integers, sort it using bubble sort algorithm.     Bubble sort is a stable, in-place sorting algorithm that is named for the way smaller or larger elements “bubble” to the top of the list. Although the algorithm is simple, it is too slow and impractical for most problems even when compared …

Selection sort | Iterative & Recursive

Given an array of integers, sort it using selection sort algorithm. Selection sort is a unstable, in-place sorting algorithm known for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited. It can be implemented as a stable sort.

Insertion sort | Iterative & Recursive

Given an array of integers, sort it using insertion sort algorithm.     Insertion sort is stable, in-place sorting algorithm that builds the final sorted array one item at a time. It is not very best in terms of performance but it is more efficient in practice than most other simple O(n2) algorithms such as …