Non-Primitive Data Structures

Non-primitive data structures are used to store and organize data in a more complex way than primitive data types. They are also known as user-defined data structures because they are defined by the programmer. In C++, non-primitive data structures include arrays, strings, structures, classes, and more.

There are two main types of Non-Primitive Data Structures in C++:

Linear

Linear data structures are those in which data elements are arranged sequentially or linearly, where each element is connected to its previous and next adjacent elements. These structures are easy to implement as they maintain a straightforward arrangement of data.

Arrays

An array is a collection of elements of the same data type stored in contiguous memory locations. Each element in an array is accessed by an index. Arrays are used to store multiple values of the same data type under a single name.

Arrays Learn more about arrays in C++.

Stack

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. It means that the element that is inserted last is the first one to be removed. Stacks are used to store data in a way that allows adding and removing elements only from one end.

Here is an example of a stack in C++:

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> s;

    s.push(10);
    s.push(20);
    s.push(30);

    cout << "Top element: " << s.top() << endl;

    s.pop();
    cout << "Top element after pop: " << s.top() << endl;

    return 0;
}

The output of the program will be:

Top element: 30
Top element after pop: 20

In the example above, we create a stack of integers and push elements 10, 20, and 30 onto the stack. We then print the top element of the stack with the .top() method and pop an element from the stack with the .pop() method.

Queue

A queue is a linear data structure that follows the First In First Out (FIFO) principle. It means that the element that is inserted first is the first one to be removed. Queues are used to store data in a way that allows adding elements from one end and removing elements from the other end.

There are two operations that can be performed on a queue:

Enqueue: Adds an element to the end of the queue.
Dequeue: Removes an element from the front of the queue.

Here is an example of a queue in C++:

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;

    q.push(10);
    q.push(20);
    q.push(30);

    cout << "Front element: " << q.front() << endl;

    q.pop();
    cout << "Front element after pop: " << q.front() << endl;

    return 0;
}

The output of the program will be:

Front element: 10
Front element after pop: 20

In the example above, we create a queue of integers and push elements 10, 20, and 30 onto the queue. We then print the front element of the queue with the .front() method and pop an element from the queue with the .pop() method.

Linked List

A linked list is a linear data structure that consists of nodes where each node contains data and a reference (link) to the next node in the sequence. Linked lists are used to store data in a way that allows dynamic memory allocation and efficient insertion and deletion of elements.

An example of one in a real-world scenario is a train. Each car in the train is a node, and each car is connected to the next car through a link.

Here is an example of a linked list in C++:

#include <iostream>

using namespace std;

struct Node { // With a struct, we are basically creating a new data type called Node, which contains an integer `data` and a pointer to the `next` Node
    int data;
    Node* next;
};

int main() {
    Node* head = new Node;
    Node* second = new Node;
    Node* third = new Node;

    head->data = 10;
    head->next = second;

    second->data = 20;
    second->next = third;

    third->data = 30;
    third->next = nullptr; // nullptr represents a null pointer value, in this case, the end of the list

    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }

    return 0;
}

The output of the program will be:

10 20 30

In the example above, we create a linked list with three nodes (head, second, and third) and print the data of each node using a while loop.

Tuple

A tuple is a fixed-size collection of elements of different data types. Tuples are used to store a fixed number of elements in a specific order. They are similar to arrays but can store elements of different data types.

Here is an example of a tuple in C++:

#include <iostream>
#include <tuple>

using namespace std;

int main() {
    tuple<int, float, string> t(10, 3.14, "Hello");

    cout << get<0>(t) << " ";
    cout << get<1>(t) << " ";
    cout << get<2>(t) << endl;

    return 0;
}

Dictionary

A dictionary is a collection of key-value pairs where each key is unique. Dictionaries are used to store data in a way that allows fast retrieval of values based on their keys.

Here is an example of a dictionary in C++ using the map container:

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, int> dict;

    dict["Alice"] = 25;
    dict["Bob"] = 30;
    dict["Charlie"] = 35;

    cout << "Age of Alice: " << dict["Alice"] << endl;
    cout << "Age of Bob: " << dict["Bob"] << endl;
    cout << "Age of Charlie: " << dict["Charlie"] << endl;

    return 0;
}

The output of the program will be:

Age of Alice: 25
Age of Bob: 30
Age of Charlie: 35

In the example above, we create a dictionary using the map container with keys as strings and values as integers. We then add key-value pairs to the dictionary and retrieve the values based on their keys.

Non-Linear

Non-linear data structures are those in which data elements are not arranged sequentially or linearly. These structures are used to represent complex relationships between data elements.

Trees

A tree is a non-linear data structure that consists of nodes connected by edges. Each node contains data and references (links) to its child nodes. Trees are used to store data in a hierarchical structure that allows efficient search, insertion, and deletion of elements.

An example of a tree in a real-world scenario is a family tree. The root of the tree represents the oldest generation, and each child node represents a new generation.

Graphs

A graph is a non-linear data structure that consists of nodes (vertices) connected by edges. Each edge connects two nodes and represents a relationship between them. Graphs are used to store data in a way that allows representing complex relationships between elements.

An example of a graph in a real-world scenario is a your network of friends on social media. Each person is a node, and each connection between two people is an edge.

Pros and Cons

Here are some of the pros and cons of using non-primitive data structures in C++:

Data Structure	Pros	Cons
Arrays	- Easy to implement - Efficient for storing multiple values of the same data type	- Fixed size - Inefficient for inserting and deleting elements
Stack	- Efficient for adding and removing elements - Simple to implement	- Fixed size - Not suitable for random access
Queue	- Efficient for adding and removing elements - Simple to implement	- Fixed size - Not suitable for random access
Linked List	- Dynamic memory allocation - Efficient for inserting and deleting elements	- Inefficient for random access - Complex to implement
Tuple	- Fixed size - Can store elements of different data types	- Limited flexibility - Inefficient for dynamic data
Dictionary	- Fast retrieval of values - Efficient for storing key-value pairs	- High memory usage - Inefficient for storing large amounts of data
Trees	- Efficient search, insertion, and deletion - Hierarchical structure	- Complex to implement - Requires balancing
Graphs	- Represent complex relationships - Flexible structure	- Complex to implement - Requires advanced algorithms