Scribd
Upload
14 views19 pages

Node Implementation in C++

The document discusses the concept of a node as a fundamental component of various data structures like linked lists, trees, and graphs, emphasizing its ability to store data and connect to other nodes via pointers. It includes a C++ implementation of a Node class with methods for data manipulation and linking nodes together. Additionally, it provides an example of using nodes to create a linked list of car objects, demonstrating the practical application of the Node class.

Uploaded by

hadytarabay12
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views19 pages

Node Implementation in C++

The document discusses the concept of a node as a fundamental component of various data structures like linked lists, trees, and graphs, emphasizing its ability to store data and connect to other nodes via pointers. It includes a C++ implementation of a Node class with methods for data manipulation and linking nodes together. Additionally, it provides an example of using nodes to create a linked list of car objects, demonstrating the practical application of the Node class.

Uploaded by

hadytarabay12
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Structures and Algorithms

Chapter 4a – OOP and pointer application:


Node

Dr. Georges Badr

1
Node
•A node is a fundamental building block of many data structures, such as linked
lists, trees, and graphs.
• Linked lists, trees, graphs or other data structures are built of connected nodes.

•The connection between nodes is done using pointers and references.


• Each node will be connected to one or more nodes (depending on the data structure)
1
• Each node will then contain a link(s) [pointer] to the other node(s).

•On the other hand, the node should also be able to store any type of data. 2

• 1 + 2 ➔ It can be implemented as an object with a at least 2 attributes:


• Data (that can be of any type → template)
• Reference of another node: pointer to a node.

CSC315 - DR MIREILLE MAKARY 2


Node
•Representation •UML

Data Pointer Node


members - data
- next node reference
+ constructor
+ getData()
+ setData(newData)
+ getNext()
+ setNext(new ref)
+ print()

CSC315 - DR MIREILLE MAKARY 3


Node
Node.h
•Implementation in C++
#include <iostream>
using namespace std;

template <typename T>

class Node
{
private:
T data;
Node<T>* next;

public:
//constructors
Node(){} //to create an empty Node

Node(T data, Node<T>* next = NULL)


{
this->data = data;
this->next = next;
}

//getters
T getData() { return data; }
Node<T>*getNext() { return next; }

//setters
void setData (T data) { this->data = data; }
void setNext (Node<T>* next) { this->next=next; }

//print
void print() { cout << data << " "; }
CSC315 - DR MIREILLE MAKARY 4
};
Node
•Implementation in C++
[Link]
20 •
#include <iostream>
using namespace std; second
#include "Node.h" 10 •
30 •
int main() {
// Create individual nodes third
Node<int>* first = new Node(10); first
Node<int>* second = new Node(20);
Node<int>* third = new Node(30);

CSC315 - DR MIREILLE MAKARY 5


Node
•Implementation in C++
[Link]
20 •
#include <iostream>
using namespace std; second
#include "Node.h" 10 •
30 •
int main() {
// Create individual nodes third
Node<int>* first = new Node(10); first
Node<int>* second = new Node(20);
Node<int>* third = new Node(30);

// Link nodes (example) // Create individual nodes and link them using the overloaded constructor
first->setNext(second); Node<int>* third = new Node(30);
second->setNext(third); Node<int>* second = new Node(20, third);
Node<int>* first = new Node(10, second);

CSC315 - DR MIREILLE MAKARY 6


Node
•Implementation in C++
[Link]
20 •
#include <iostream>
using namespace std; second
#include "Node.h" 10 •
30 •
int main() {
// Create individual nodes third
Node<int>* first = new Node(10); first
Node<int>* second = new Node(20);
Node<int>* third = new Node(30); current
// Link nodes (example)
first->setNext(second);
second->setNext(third);

// Traverse and print the list


Output
Node<int>* current = first;
while (current != nullptr) // or NULL {
cout << current->getData() << " ";
10
current = current->getNext();
}

CSC315 - DR MIREILLE MAKARY 7


Node
•Implementation in C++
[Link]
20 •
#include <iostream>
using namespace std; second
#include "Node.h" 10 •
30 •
int main() {
// Create individual nodes
current third
Node<int>* first = new Node(10); first
Node<int>* second = new Node(20);
Node<int>* third = new Node(30);

// Link nodes (example)


first->setNext(second);
second->setNext(third);

// Traverse and print the list


Output
Node<int>* current = first;
while (current != nullptr) // or NULL {
cout << current->getData() << " ";
10 20
current = current->getNext();
}

CSC315 - DR MIREILLE MAKARY 8


Node
•Implementation in C++
[Link]
20 •
#include <iostream>
using namespace std; second
#include "Node.h" 10 •
30 •
int main() {
// Create individual nodes current third
Node<int>* first = new Node(10); first
Node<int>* second = new Node(20);
Node<int>* third = new Node(30);

// Link nodes (example)


first->setNext(second);
second->setNext(third);

// Traverse and print the list


Output
Node<int>* current = first;
while (current != nullptr) // or NULL {
cout << current->getData() << " ";
10 20 30
current = current->getNext();
}

CSC315 - DR MIREILLE MAKARY 9


Node
•Implementation in C++
[Link]
20 •
#include <iostream>
using namespace std; second
#include "Node.h" 10 •
30 •
int main() {
// Create individual nodes third
Node<int>* first = new Node(10); first
Node<int>* second = new Node(20);
Node<int>* third = new Node(30);
current
// Link nodes (example)
first->setNext(second);
second->setNext(third);

// Traverse and print the list


Output
Node<int>* current = first;
while (current != nullptr) // or NULL {
cout << current->getData() << " ";
10 20 30
current = current->getNext();
}

CSC315 - DR MIREILLE MAKARY 10


Node
•Implementation in C++
[Link]
20 •
#include <iostream>
using namespace std; second
#include "Node.h" 10 •
30 •
int main() {
// Create individual nodes current third
Node<int>* first = new Node(10); first
Node<int>* second = new Node(20);
Node<int>* third = new Node(30);

// Link nodes
first->setNext(second);
second->setNext(third);

// Traverse and print the list


Output
Node<int>* current = first;
while (current != nullptr) // or NULL {
cout << current->getData() << " ";
10 20 30
current = current->getNext();
}

// Deallocate memory
delete first;
delete second;
delete third;

return 0;
} CSC315 - DR MIREILLE MAKARY 11
Node – example 2
•In this example we will consider that the data in the Node is of type car.
•A car is defined by its make (string), model (string), year (int). It has a method
print() that will display all the information of the car.

•Implement the car class


•Update the node class accordingly
•Write a main to test your program

CSC315 - DR MIREILLE MAKARY 12


Node
•Implementation in C++ car.h
#include<iostream>
using namespace std;

class Car
{
private:
string make;
string model;
int year;

public:
Car() : make("Unknown"), model("Unknown"), year(0) {}

Car (string ma, string mo, int y)


{
make = ma;
model = mo;
year = y;
}

void print()
{
cout << "Car: " << make << " " << model << " (" << year << ")\n";
}
};

CSC315 - DR MIREILLE MAKARY 13


[Link]

Node #include<iostream>
using namespace std;
#include<string>

•Implementation in C++ #include "car.h"


#include "node.h"

int main()
car1 car2 car3 {

Toyota Honda Ford Car car1("Toyota", "Corolla", 2020);


Car car2("Honda", "Civic", 2018);
Corolla Civic Mustang Car car3("Ford", "Mustang", 2022);

2020 2018 2022 // Create nodes for each car


Node<Car>* first = new Node<Car>(car1);
Node<Car>* second = new Node<Car>(car2);
Node<Car>* third = new Node<Car>(car3);

// Link the nodes together to form a linked list


first->setNext(second);
second->setNext(third);
•

second
•
•
third
first

CSC315 - DR MIREILLE MAKARY 14


[Link]

Node #include<iostream>
using namespace std;
#include<string>

•Implementation in C++ #include "car.h"


#include "node.h"

int main()
car1 car2 car3 {

Toyota Honda Ford Car car1("Toyota", "Corolla", 2020);


Car car2("Honda", "Civic", 2018);
Corolla Civic Mustang Car car3("Ford", "Mustang", 2022);

2020 2018 2022 // Create nodes for each car


Node<Car>* first = new Node<Car>(car1);
Node<Car>* second = new Node<Car>(car2);
Node<Car>* third = new Node<Car>(car3);

// Link the nodes together to form a linked list


first->setNext(second);
second->setNext(third);
•
// Print the list of cars
Node<Car>* current = first;
Car: Toyota Corolla (2020)
while (current != NULL) {
second current->getData().print();

• }
current = current->getNext();

•
third
first
current CSC315 - DR MIREILLE MAKARY 15
[Link]

Node #include<iostream>
using namespace std;
#include<string>

•Implementation in C++ #include "car.h"


#include "node.h"

int main()
car1 car2 car3 {

Toyota Honda Ford Car car1("Toyota", "Corolla", 2020);


Car car2("Honda", "Civic", 2018);
Corolla Civic Mustang Car car3("Ford", "Mustang", 2022);

2020 2018 2022 // Create nodes for each car


Node<Car>* first = new Node<Car>(car1);
Node<Car>* second = new Node<Car>(car2);
Node<Car>* third = new Node<Car>(car3);

// Link the nodes together to form a linked list


first->setNext(second);
second->setNext(third);
•
// Print the list of cars
Node<Car>* current = first;
Car: Toyota Corolla (2020)
while (current != NULL) { Car: Honda Civic (2018)
second current->getData().print();

current • }
current = current->getNext();

•
third
first

CSC315 - DR MIREILLE MAKARY 16


[Link]

Node #include<iostream>
using namespace std;
#include<string>

•Implementation in C++ #include "car.h"


#include "node.h"

int main()
car1 car2 car3 {

Toyota Honda Ford Car car1("Toyota", "Corolla", 2020);


Car car2("Honda", "Civic", 2018);
Corolla Civic Mustang Car car3("Ford", "Mustang", 2022);

2020 2018 2022 // Create nodes for each car


Node<Car>* first = new Node<Car>(car1);
Node<Car>* second = new Node<Car>(car2);
Node<Car>* third = new Node<Car>(car3);

// Link the nodes together to form a linked list


first->setNext(second);
second->setNext(third);
•
// Print the list of cars
Node<Car>* current = first;
Car: Toyota Corolla (2020)
while (current != NULL) { Car: Honda Civic (2018)
second current->getData().print(); Car: Ford Mustang (2022)
• }
current = current->getNext();

•
third
first
current
CSC315 - DR MIREILLE MAKARY 17
[Link]

Node #include<iostream>
using namespace std;
#include<string>

•Implementation in C++ #include "car.h"


#include "node.h"

int main()
car1 car2 car3 {

Toyota Honda Ford Car car1("Toyota", "Corolla", 2020);


Car car2("Honda", "Civic", 2018);
Corolla Civic Mustang Car car3("Ford", "Mustang", 2022);

2020 2018 2022 // Create nodes for each car


Node<Car>* first = new Node<Car>(car1);
Node<Car>* second = new Node<Car>(car2);
Node<Car>* third = new Node<Car>(car3);

// Link the nodes together to form a linked list


first->setNext(second);
second->setNext(third);
•
// Print the list of cars
Node<Car>* current = first;
Car: Toyota Corolla (2020)
while (current != NULL) { Car: Honda Civic (2018)
second current->getData().print(); Car: Ford Mustang (2022)
• }
current = current->getNext();

•
third
first current

CSC315 - DR MIREILLE MAKARY 18


[Link]

Node #include<iostream>
using namespace std;
#include<string>

•Implementation in C++ #include "car.h"


#include "node.h"

int main()
car1 car2 car3 {

Toyota Honda Ford Car car1("Toyota", "Corolla", 2020);


Car car2("Honda", "Civic", 2018);
Corolla Civic Mustang Car car3("Ford", "Mustang", 2022);

2020 2018 2022 // Create nodes for each car


Node<Car>* first = new Node<Car>(car1);
Node<Car>* second = new Node<Car>(car2);
Node<Car>* third = new Node<Car>(car3);

// Link the nodes together to form a linked list


first->setNext(second);
second->setNext(third);
•
// Print the list of cars
Node<Car>* current = first;
Car: Toyota Corolla (2020)
while (current != NULL) { Car: Honda Civic (2018)
second current->getData().print(); Car: Ford Mustang (2022)
• }
current = current->getNext();

• // Free up the memory


delete first;
third delete second;
current
first delete third;

return 0;
CSC315 - DR MIREILLE MAKARY } 19

You might also like