DATASTRUCTURES

-
DataStructures:
a) Data structures are formats used to organize, store and manage data efficiently.
        e.g. stacks, queues, singly-linked lists, doubly linked lists, binary search trees, hashing and heaps. 
b) Operations on data structures are searching, sorting, adding, updating and deleting. 
c) A linked list is a linear data structure where the elements are not stored at the contiguous memory locations, they are stored dynamically.
d) It has a collection of nodes where each node consists of two members which represents its value and a next/previous pointer which stores the address for the next/previous node.
e) Stacks, Queues, Singly-linked lists, Doubly linked lists, Binary Search Trees can be implemented as linked lists.

Stack:
a) Stack follows LIFO(Last In First Out) principle.
b) It is used in function calls.
c) The functions of Stack are push(Adds an element) and pop(Extracts an element).
d) It has a TOP pointer.

Example:
class Stack
{
int Data;
Stack* Node;
Stack* Next;

Stack* Top = nullptr;
Stack* First = nullptr;
public:
void pushData(int Dat)
{
Node = new Stack();
Node->Data = Dat;
Node->Next = nullptr;

if (Top == nullptr)
{
Top = Node;
First = Node;
}
else
{
Top->Next = Node;
Top = Node;
}
}

int popData()
{
if (Top == nullptr)
{
cout << "Stack is Empty" << endl;
return -1;
}

Stack* temp = First;
Stack* temp1 = First;;

if (First == Top)
{
int t = temp->Data;
delete temp;
Top = nullptr;
First = nullptr;

return t;
}
else
{
while (temp->Next != nullptr)
{
temp1 = temp;
temp = temp->Next;
}

int t = Top->Data;
Top = temp1;
Top->Next = nullptr;
delete temp;

return t;
}
return -1;
}

void Display()
{
if (Top == nullptr)
{
cout << "Stack is Empty" << endl;
return;
}

Stack* temp = First;
while (temp)
{
cout << "Data: " << temp->Data << endl;
temp = temp->Next;
}
}
};

void Stack_Functions()
{
Stack* stackObj = new Stack();
stackObj->pushData(10);
stackObj->pushData(20);
stackObj->pushData(30);
stackObj->pushData(40);
stackObj->pushData(50);

stackObj->Display();
cout << endl;
cout << "Data : " << stackObj->popData() << endl;
cout << "Data : " << stackObj->popData() << endl;
cout << "Data : " << stackObj->popData() << endl;
cout << "Data : " << stackObj->popData() << endl;
cout << "Data : " << stackObj->popData() << endl;

cout << endl;
stackObj->Display();
}

Queue:
a) Queue follows FIFO(First in First out) principle.
b) It has FRONT(Pops an element at the front) and REAR(Adds an element at the end) pointers.

Example:
class Queue
{
int data;
Queue* Node;
Queue* Next;

Queue* front = nullptr;
Queue* rear = nullptr;
public:
void Add(int dat);
int Del();
void Disp();
};

void Queue::Add(int dat)
{
Node = new Queue();
Node->data = dat;
Node->Next = nullptr;

if (front == nullptr)
{
front = Node;
rear = Node;
}
else
{
rear->Next = Node;
rear = Node;
}
}

int Queue::Del()
{
if (front == nullptr)
{
cout << "Queue is empty" << endl;
return -1;
}

int d = front->data;
Queue* temp = front;
front = front->Next;
delete temp;

return d;
}

void Queue::Disp()
{
if (front == nullptr)
{
cout << "Queue is empty" << endl;
return;
}

Queue* temp = front;
while (temp)
{
cout << "Data: " << temp->data << endl;
temp = temp->Next;
}
}

void Queue_Functions()
{
Queue* queObj = new Queue;
queObj->Add(10);
queObj->Add(20);
queObj->Add(30);
queObj->Add(40);
queObj->Add(50);

queObj->Disp();
cout << endl;

cout << "Data: " << queObj->Del() << endl;
cout << "Data: " << queObj->Del() << endl;
cout << "Data: " << queObj->Del() << endl;
cout << "Data: " << queObj->Del() << endl;
cout << "Data: " << queObj->Del() << endl;
}

Singly-linked lists:
a) Singly-linked is an unordered array of pointers.
b) It has a FIRST pointer and a next/previous pointer.

Example:
class List
{
int Data;
List* Node;
List* Next;
List* First = nullptr;
public:
void Append(int Data)
{
Node = new List();
Node->Data = Data;
Node->Next = nullptr;

if (First == nullptr)
{
First = Node;
}
else
{
List* temp = First;
while (temp->Next != nullptr)
{
temp = temp->Next;
}

temp->Next = Node;
}
}

void Insert(int Data, int pos)
{
Node = new List();
Node->Data = Data;
Node->Next = nullptr;

List* temp = First;
List* temp1 = First;
if (pos == 1)
{
Node->Next = First;
First = Node;
}
else
{
for (int i = 1; i <= pos; i++)
{
if (i == pos)
{
Node->Next = temp1->Next;
temp1->Next = Node;
break;
}
temp1 = temp;
temp = temp->Next;

if (temp == nullptr)
{
cout << "Invalid position" << endl;
break;
}
}
}
}

int Delete(int pos)
{
List* temp = First;
List* temp1 = First;

if (pos == 1)
{
int t = First->Data;
First = First->Next;
delete temp;
return t;
}
else
{
for (int i = 1; i <= pos; i++)
{
if (i == pos)
{
temp1->Next = temp->Next;
int t = temp->Data;
delete temp;
return t;
}
temp1 = temp;
temp = temp->Next;

if (temp == nullptr)
{
cout << "Invalid position" << endl;
return -1;
}
}
}
}

void Display()
{
List* temp = First;
while (temp != nullptr)
{
cout << "Data: " << temp->Data << endl;
temp = temp->Next;
}
}
};

void List_Functions()
{
List* listObj = new List();
listObj->Append(10);
listObj->Append(20);
listObj->Append(30);
listObj->Append(40);
listObj->Append(50);

listObj->Display();
cout << endl;

listObj->Insert(60, 1);
listObj->Insert(70, 2);

listObj->Display();
cout << endl;

cout<<"Data: "<<listObj->Delete(1)<<endl;
cout<<"Data: "<<listObj->Delete(2)<<endl;
cout << endl;

listObj->Display();
}

Doubly-linked lists:
a) Doubly-linked is an unordered array of pointers.
b) It has a FIRST pointer and both next and previous pointers.

Example:
class Doubly_List
{
int Data;
Doubly_List* Node;
Doubly_List* Prev;
Doubly_List* Next;
Doubly_List* First = nullptr;
public:
void Append(int Data)
{
Node = new Doubly_List();
Node->Data = Data;
Node->Next = nullptr;
Node->Prev = nullptr;

if (First == nullptr)
{
First = Node;
}
else
{
Doubly_List* temp = First;
Doubly_List* temp1 = First;
while (temp->Next != nullptr)
{
temp1 = temp;
temp = temp->Next;
}

temp->Next = Node;
Node->Prev = temp;
}
}

void Insert(int Data, int pos)
{
Node = new Doubly_List();
Node->Data = Data;
Node->Next = nullptr; 
Node->Prev = nullptr;

Doubly_List* temp = First;
Doubly_List* temp1 = First;

if (pos == 1)
{
Node->Next = First;
First->Prev = Node;
First = Node;
}
else
{
for (int i = 1; i <= pos; i++)
{
if (i == pos)
{
temp1->Next->Prev = Node;
Node->Next = temp1->Next;
temp1->Next = Node;
break;
}
temp1 = temp;
temp = temp->Next;

if (temp == nullptr)
{
cout << "Invalid position" << endl;
break;
}
}
}
}

int Delete(int pos)
{
Doubly_List* temp = First;
Doubly_List* temp1 = First;

if (pos == 1)
{
int t = First->Data;
First = First->Next;
First->Next->Prev = nullptr;
delete temp;
return t;
}
else
{
for (int i = 1; i <= pos; i++)
{
if (i == pos)
{
temp1->Next = temp->Next;
temp->Next->Prev = temp1;
int t = temp->Data;
delete temp;
return t;
}
temp1 = temp;
temp = temp->Next;

if (temp == nullptr)
{
cout << "Invalid position" << endl;
return -1;
}
}
}
}

void Display()
{
Doubly_List* temp = First;
while (temp != nullptr)
{
cout << "Data: " << temp->Data << endl;
temp = temp->Next;
}
}
};

void DoublyList_Functions()
{
Doubly_List* listObj = new Doubly_List();
listObj->Append(10);
listObj->Append(20);
listObj->Append(30);
listObj->Append(40);
listObj->Append(50);

listObj->Display();
cout << endl;

listObj->Insert(60, 1);
listObj->Insert(70, 2);

listObj->Display();
cout << endl;

cout << "Data: " << listObj->Delete(1) << endl;
cout << "Data: " << listObj->Delete(2) << endl;
cout << endl;

listObj->Display();
}

Binary Search Trees(BST):
a) The root of a binary tree is the topmost node. 
b) Each node can have at most two children, which are referred to as the left child(only smaller values) and the right child(only larger values).
            i) LNR  -> Left, Node, Right
           ii) NLR  -> Node, Left, Right
          iii) LRN  -> Left, Right, Node
Example:
class BinaryTree
{
int Data;
BinaryTree* Node;
BinaryTree* lNode;
BinaryTree* rNode;
public:
BinaryTree* Root = nullptr;

void AddNode(int data)
{
Node = new BinaryTree();
Node->Data = data;
Node->lNode = nullptr;
Node->rNode = nullptr;

if (Root == nullptr)
{
Root = Node;
}
else
{
BinaryTree* binTreeObject = Root;
BinaryTree* temp = Root;
while (temp)
{
binTreeObject = temp;
if (data > temp->Data)
{
temp = temp->rNode;
}
else
{
temp = temp->lNode;
}
}

if (data > binTreeObject->Data)
{
binTreeObject->rNode = Node;
}
else
{
binTreeObject->lNode = Node;
}
}
}

void delNode(int data)
{
if (Root == nullptr)
{
cout << "ROOT is null" << endl;
return;
}

BinaryTree* temp = Root;

while (temp)
{
if (temp->Data == data)
{
BinaryTree* temp1 = temp;
BinaryTree* temp2 = temp;
while (temp1->lNode)
{
temp2 = temp1;
temp1 = temp1->lNode;
}
if ((temp1->rNode == nullptr) && (temp1->lNode == nullptr))
{
//if temp2 has no child
temp2->lNode = nullptr;
temp1->lNode = temp->lNode;
temp1->rNode = temp->rNode;

if (temp == Root)
Root = temp1;
delete temp;

return;
}
else if ((temp1->rNode != nullptr) && (temp1->lNode == nullptr))
{
//if temp2 has rchild
temp2->lNode = temp1->rNode;
temp1->lNode = temp->lNode;
temp1->rNode = temp->rNode;

if (temp == Root)
Root = temp1;
delete temp;

return;
}
}
if (data > temp->Data)
{
temp = temp->rNode;
}
else
{
temp = temp->lNode;
}
}
cout << "Data is not present" << endl;
}

void PreOrderTraversal(BinaryTree* Node) //NLR
{
if (Node == nullptr)
{
return;
}
cout << Node->Data <<" -> ";
PreOrderTraversal(Node->lNode);
PreOrderTraversal(Node->rNode);
}

void InOrderTraversal(BinaryTree* Node)  //LNR
{
if (Node == nullptr)
{
return;
}

InOrderTraversal(Node->lNode);
cout << Node->Data << " -> ";
InOrderTraversal(Node->rNode);
}

void PostOrderTraversal(BinaryTree* Node) //LRN
{
if (Node == nullptr)
{
return;
}

PostOrderTraversal(Node->lNode);
PostOrderTraversal(Node->rNode);
cout << Node->Data << " -> ";
}
};

void BinaryTree_Functions()
{
BinaryTree* BTree = new BinaryTree();
BTree->AddNode(100);
BTree->AddNode(50);
BTree->AddNode(120);
BTree->AddNode(40);
BTree->AddNode(60);
BTree->AddNode(110);
BTree->AddNode(125);

BTree->PreOrderTraversal(BTree->Root);
cout << endl;
BTree->InOrderTraversal(BTree->Root);
cout << endl;
BTree->PostOrderTraversal(BTree->Root);
cout << endl;

BTree->delNode(100);
BTree->PreOrderTraversal(BTree->Root);
cout << endl;
BTree->InOrderTraversal(BTree->Root);
cout << endl;
BTree->PostOrderTraversal(BTree->Root);
}

Popular posts from this blog

OBJECT ORIENTED ANALYSIS AND DESIGN (OOAD)

-
Object Oriented Analysis and Design (OOAD): OOAD is a powerful approach for developing complex software systems by breaking them down into manageable objects and their interactions, leading to more robust, maintainable, and reusable code.  Creational Patterns :           1) Singleton           2) Factory           3) Abstract Factory           4) Builder           5) Prototype Structural Patterns :           1)  Adapter           2)  Bridge           3)  Composite           4)  Decorator           5) Facade           6) Flyweight           7) Proxy Behavioural Patterns :     ...
Read more

OBJECT ORIENTED PROGRAMMING

-
  OBJECT ORIENTED PROGRAMMING: The principles of OOPS are: 1) Abstraction 2) Encapsulation 3) Inheritance 4) Polymorphism 1) Abstraction: Abstraction can be of two forms, data abstraction and functional abstraction . a) Data Abstraction: The representation of the data is hidden. b) Functional Abstraction:                The implementation is hidden.   C++, ' class ' provides data and functional abstraction.               Refer:  FRIEND FUNCTIONS AND FRIEND CLASS 2) Encapsulation:           a) Holding the data members and member functions as a single unit.          b) A 'class' holds its data members and member functions as a unit.             Refer: CONSTRUCTORS AND DESTRUCTORS           3) Inheritance: Inheriting...
Read more

STARTING A BUSINESS

-
  STARTING A BUSINESS STEP INTO THE LIFE YOU WANT TO CREATE FOR YOURSELF A) START A BUSINESS:   The Key to start a Business are Time, Money and Experience. Passion is not something you find in life; its something you do.  Transform your vision into Innovation and Impact.       How to turn your ideas into action: Small builds lead to confidence, Confidence leads to consistency and Consistency leads to mastery.      How to master Entrepreneurship: It demands consistent action and transparent progress tracking. You need continuous practice, proper mindset and right support system.      Know the Business Insights: Learn how processes run, how data flows and how functions execute. 1) How to start a Business?   a ) You can start a new Startup: Startups need money to build a prototype of your product, to conduct market research,  to grow your engineering teams and to develop your software ...
Read more