using C++
MODULE : 1 – Linked List
Hi all,
In this blog lets discuss about Data Structures and few Algorithms using C++. Don’t worry if you have an interest of different language, Since the Core concepts will be same in that case. Only thing that differs is syntax. So you can take this up without any hesitation. This might be a helpful guide for Code Newbies to understand the basics, Since data structures gives you a clear insight of what happens to the Data that we – the programmer employs or access. This write-up can be kept handy for a Quick reference by Candidates preparing for their Technical Interview in the field of Computer Science / IT for a Dev position and by Programmers who needs a quick Brush-up of their technical stuff.
I would present this self-learning guide in five modules with runnable Sourcecodes and brief Comments, at places for our easy approach.
1. Linked List:
1.1 Inserting a node at the beginning of a Linked List
1.2 Inserting a node at ‘n’th position of a Linked List
1.3 Inserting a node at the end of a Linked List
1.4 Deleting a node from ‘n’th position of a Linked List
1.5 Reversing a Linked List iteratively
1.6 Reversing a Linked List recursively
1.7 Printing the elements of a Linked List (forward and reverse)
1.8 Doubly Linked List
1.9 Circular Linked List
2. Stack:
2.1 Array implementation of stack
2.2 Linked List implementation of stack
2.3 Reversing a string or Linked List using stack
2.4 Infix, Postfix, Prefix – Evaluate Postfix expression
2.5 Infix to Postfix
2.6 Infix to Postfix with Paranthesis
3. Queue:
3.1 Array implementation of Queue
3.2 Linked List implementation of Queue
4. Tree:(BST)
4.1 Binary Search Tree(BST) implementation
4.2 Finding min and max element in a BST
4.3 Find height of BST
4.4 BST traversal breadth first,depth first
4.5 Level order traversal
4.6 Preorder, Inorder and PostOrder traversal
4.7 Checking whether a Binary tree is BST
4.8 Deleting a node from BST
4.9 Inorder successor in BST
5. Algorithms
5.1 Search algorithm:
5.1.1 Linear search
5.1.2 Binary search
5.2 Sort algorithm:
5.2.1 Selection sort
5.2.2 Bubble sort
5.2.3 Insertion sort
5.2.4 Merge sort
5.2.5 Quick sort
Lets get started…
MODULE : 1 – Linked List
Introduction–Node:
In Linked List, data is stored in Node, which is a multiple non-contiguous memory block
Head:
Address of head node gives us ACCESS of the complete list.
Syntax:
struct Node{
int data;
Node* next; //pointer to next node
};
Node* head=NULL; //pointer to head node,..empty list
/*note: its not a head node,its just a pointer to the node*/
Memory allocation:
/* memory allocation in C style*/
struct Node * temp= (Node*) malloc(sizeof(Node));
temp->data=2;
temp->next=NULL;
head=temp;
/*memory allocation in C++ style*/
Node * temp= new Node( ); //using new operator, instead of malloc function
1.1 Inserting a node at the beginning of a Linked List
Lets learn how to insert a Node at the beginning of a Linked List through Coding.
Runnable Code Snippet_1.1 a- Inserting a node at the beginning of a Linked List
/* insert a node @ beginning*/
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* head;
void Insert(int x){
Node* temp= new Node;
temp->data=x;
temp->next=NULL;
if(head!=NULL)
temp->next=head;
head=temp;
}
void Print(){
Node* temp=head;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
}
int main()
{
head=NULL;
int n,x,i;
cin>>n;
for(i=0;i<n;i++){
cin>>x;
Insert(x);
}
Print();
return 0;
}
Alternate method- by keeping the head as local variable:
Runnable Code Snippet_1.1 b- Inserting a node at the beginning of a Linked List by keeping the head as a local variable:
//Alternate method: keeping head as local variable
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* Insert(int x,Node* head){/*arg:num,head(Node*),return Node* */
Node* temp=new Node;
temp->data=x;
temp->next=NULL;
if(head!=NULL)
temp->next=head;
head=temp;
return head;
}
void Print(Node* head){
while(head!=NULL){
cout<<head->data<<" ";
head=head->next;
}
cout<<endl;
}
int main(void){
Node* head=NULL; //local
int n,x;
cout<<"Enter size: ";
cin>>n;
cout<<"Enter elements:\n";
for(int i=0;i<n;i++){
cin>>x;
head=Insert(x,head); //pass head as parameter
}
Print(head);//pass head as parameter
return 0;
}
I just tried constructing a Linked List with Object Oriented approach, please walk through that and let me know, if that’s acceptable ; )
Runnable Code Snippet_1.1 c- Linked list Object Oriented Implementation– Insertion at head:
/*Linked list Object Oriented Implementation- insertion at head ,... juz an attempt*/
#include<iostream>
using namespace std;
class Node{
private:
int data;
Node* next, *head;
public:
Node(){
head=NULL;
}
void Insert(int x){
Node* temp=new Node;
temp->data=x;
temp->next=NULL;
if(head==NULL){
head=temp;
return;
}
Node* temp1=head;
temp->next=temp1;
head=temp;
}
void Print(){
cout<<"List: ";
Node* temp=head;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
};
int main()
{
Node LL;
LL.Insert(1);
LL.Insert(2);
LL.Insert(3);
LL.Print(); //3 2 1
return 0;
}
1.2 Inserting a node at ‘n’th position of a Linked List:
Runnable Code Snippet_1.2- Inserting a node at ‘n’th position of a Linked List:
/*insert a node @ nth position */
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* head;
void Insert(int x,int n){
if(head==NULL && n!=1) return;
Node* temp1=new Node();
temp1->data=x;
if(n==1){
temp1->next=head;
head=temp1;
}
else{
Node* temp2=head;
for(int i=0;i<n-2;i++){
temp2=temp2->next; //reached n-1 node
}
temp1->next=temp2->next;
temp2->next=temp1;
}
}
void Print(){
Node* temp=head;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
}
int main()
{
head=NULL;
Insert(2,1);
Insert(4,2);
Insert(6,3);
Insert(8,4);
Insert(5,4);
Insert(3,1);
Print(); //3 2 4 6 5 8
return 0;
}
1.3 Inserting a node at the end of a Linked List:
Runnable Code Snippet_1.3- Inserting a node at the end of a Linked List:
/* insert a node @ end */
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* head;
void InsertEnd(int x){
Node* temp=new Node();
temp->data=x;
temp->next=NULL;
if(head==NULL) head=temp;
else{
Node* temp1=head;
while(temp1->next!=NULL) temp1=temp1->next;
temp1->next=temp;
}
}
void Print(){
Node* temp=head;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
}
int main()
{
head=NULL;
int n,x;
cin>>n;
for(int i=0;i<n;i++){
cin>>x;
InsertEnd(x);
}
Print();
return 0;
}
1.4 Deleting a node from ‘n’th position of a Linked List
Runnable Code Snippet_1.4- Deleting a node from ‘n’th position of a Linked List
/*delete a node @ nth position*/
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* head;
void Insert(int x){ //insert @ begining
Node* temp=new Node();
temp->data=x;
temp->next=head;
head=temp;
}
void Delete(int n){
Node* temp1=head;
if(n==1){
head=temp1->next;
delete temp1; //dealloc mem
}
else{
for(int i=0;i<n-2;i++){ /*reaches (n-1)th node*/
temp1=temp1->next;
}
Node* temp2=temp1->next;
temp1->next=temp2->next;
delete temp2; //dealloc mem
}
}
void Print(){
Node* temp=head;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}cout<<endl;
}
int main()
{
head=NULL;
Insert(2);
Insert(4);
Insert(6);
Insert(8);
Print(); //8 6 4 2
Delete(3);
Print(); //8 6 2
return 0;
}
1.5 Reversing a Linked List iteratively
Note:
Iterative solution- Time complexity: O(n); Space complexity: O(1)
Recursive solution- Time complexity: O(n); Space complexity: O(n), we use implicit stack in recursive method.
Please refer Big O notation, for more details visit:https://en.wikipedia.org/wiki/Big_O_notation
Runnable Code Snippet_1.5- Reversing a Linked List iteratively
/* reverse a L.L iteratively*/
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* head;
void Insert(int x){
Node* temp=new Node();
temp->data=x;
temp->next=head;
head=temp;
}
void Reverse(){
Node *ct,*prev, *next;
ct=head;
prev=NULL;
while(ct!=NULL){
next=ct->next;
ct->next=prev;
prev=ct;
ct=next;
}
head=prev;
}
void Print()
{
Node* temp=head;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
int main()
{
head=NULL;
int n,x;
cin>>n;
for(int i=0;i<n;i++){
cin>>x;
Insert(x);
}
cout<<"List: \n";
Print();
Reverse();
cout<<"Reversed list: \n";
Print();
return 0;
}
1.6 Reversing a Linked List recursively
Runnable Code Snippet_1.6 a – Reversing a Linked List recursively
/* reverse a L.L recursively*/
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* head;
void InsertEnd(int x){
Node* temp=new Node();
temp->data=x;
temp->next=NULL;
if(head==NULL)head=temp;
else{
Node* temp1=head;
while(temp1->next!=NULL)temp1=temp1->next;
temp1->next=temp;
}
}
void Reverse(Node* p){ //recursive method
if(p->next==NULL) { //exit condition
head=p;
return;
}
else {
Reverse(p->next); //recursive call
Node* q=p->next;
q->next=p;
p->next=NULL;
}
}
void Print(Node* p){ //recursive method
if(p==NULL) {cout<<endl;return;} //exit condition
cout<<p->data<<" ";
Print(p->next); //recursive call
}
int main()
{
head=NULL;
InsertEnd(1);
InsertEnd(2);
InsertEnd(3);
InsertEnd(4);
Print(head); //1 2 3 4
Reverse(head);
Print(head); //4 3 2 1
return 0;
}
Alternate method-using STL
Runnable Code Snippet_1.6 b – Reversing a Linked List USING A STACK STL :
//using stack STL to reverse LL
#include<iostream>
#include<stack>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* head;
void Insert(int x){
Node* temp=new Node;
temp->data=x;
temp->next=NULL;
if(head==NULL){
head=temp;
return;
}
Node* temp1=head;
temp->next=temp1;
head=temp;
}
void Reverse(){
if(head==NULL) return;
stack<Node*>S;
Node* temp=head;
while(temp!=NULL){
S.push(temp);
temp=temp->next;
}
temp=S.top();head=temp;
S.pop();
while(!S.empty()){
temp->next=S.top();
S.pop();
temp=temp->next;
}
temp->next=NULL;
}
void Print(){
Node* temp=head;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
int main(){
Insert(3);
Insert(8);
Insert(87);
Insert(45);
Print(); //45 87 8 3
Reverse();
Print(); //3 8 87 45
return 0;
}
1.7 Printing elements of a Linked List (forward & reverse)
Runnable Code Snippet_1.7– Printing elements of a Linked List (forward & reverse)
/* Print(FORWARD & REVERSE) using RECURSIVE FUNCTION */
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* head;
void Insert(int x){ //insert @ begining
Node* temp=new Node();
temp->data=x;
temp->next=head;
head=temp;
}
void Print(Node* p){
if(p==NULL){cout<<endl; return;}
cout<<p->data<<" ";
Print(p->next);
}
void RevPrint(Node* p){
if(p==NULL) return;
RevPrint(p->next);
cout<<p->data<<" ";
}
int main()
{
head=NULL;
Insert(10);
Insert(20);
Insert(5);
Insert(1);
Print(head); //1 5 20 10
RevPrint(head); //10 20 5 1
return 0;
}
1.8 Doubly Linked List
Runnable Code Snippet_1.8– Doubly Linked List
/* Doubly Linked List implementation */
#include<iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
};
Node* head; // global variable - pointer to head node.
//Creates a new Node and returns pointer to it.
Node* GetNewNode(int x) {
Node* newNode= new Node;
newNode->data = x;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
//Inserts a Node at head of doubly linked list
void InsertAtHead(int x) {
Node* newNode = GetNewNode(x);
if(head == NULL) {
head = newNode;
return;
}
head->prev = newNode;
newNode->next = head;
head = newNode;
}
//Inserts a Node at tail of Doubly linked list
void InsertAtTail(int x) {
Node* temp = head;
Node* newNode = GetNewNode(x);
if(head == NULL) {
head = newNode;
return;
}
while(temp->next != NULL) temp = temp->next; // Go To last Node
temp->next = newNode;
newNode->prev = temp;
}
//Prints all the elements in linked list in forward traversal order
void Print() {
Node* temp = head;
cout<<"Forward: ";
while(temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
}
//Prints all elements in linked list in reverse traversal order.
void ReversePrint() {
Node* temp = head;
if(temp == NULL) return; // empty list, exit
// Going to last Node
while(temp->next != NULL) {
temp = temp->next;
}
// Traversing backward using prev pointer
cout<<"Reverse: ";
while(temp != NULL) {
cout<<temp->data<<" ";
temp = temp->prev;
}
cout<<endl;
}
int main() {
/*Driver code to test the implementation*/
head = NULL; // empty list. set head as NULL.
// Calling an Insert and printing list both in forward as well as reverse direction.
InsertAtTail(2); Print(); ReversePrint();
InsertAtTail(4); Print(); ReversePrint();
InsertAtHead(6); Print(); ReversePrint();
InsertAtTail(8); Print(); ReversePrint();
}
With this we finish the first module of our Data Structures quick reference. As Circular Linked List is an important topic altogether, we will cover it separately in the next module. Please follow the blog to stay updated with the upcoming modules.
love,
<R.S>
For Complete Sourcecode visit my Github repo: Link provided in the final module
RS-codes
RS-codes 
3 thoughts on “Data Structures & Algorithms”