11. Dynamic Data Structures in C++

Introduction

In C++, a dynamic data structure is a structure where the size can be changed during the runtime. This allows the data to be manipulated in complex ways. Here are some types of dynamic data structures:

• Array

• Stack

• Queue

• Dequeue

• Priority Queue

• Circular Queue

• Binary Tree

• Singly-Linked List

• Doubly-Linked List

Circular Queue

A circular queue is a type of queue that performs operations in a circular way which means that the last element points to the first element making a circular link.

Priority Queue

A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue.

Singly-Linked List

A singly-linked list is a data structure that includes a sequence of nodes where each node holds data and a link to the next node. The last node points to null, indicating the end of the list.

Key Points:

• Reading a linked list is n times slower than an array as it involves following the links from one node to the next.

• Inserting a new element at the beginning (pushfirst()) is faster with a linked list.

• Adding an element at the end (pushlast()) is slower, as it involves traversing the entire list to find the last node.

Example:

#include<iostream>
using namespace std;

struct Node {
   int data;
   struct Node *next;
};

struct Node* head = NULL;

void insert(int new_data) {
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   new_node->data = new_data;
   new_node->next = head;
   head = new_node;
}

void display() {
   struct Node* ptr;
   ptr = head;
   while (ptr != NULL) {
      cout<< ptr->data <<" ";
      ptr = ptr->next;
   }
}

int main() {
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   cout<<"The linked list is: ";
   display();
   return 0;
}

Doubly-Linked List

A doubly-linked list is a type of linked list in which each node contains a data part and two links, one to connect to the previous node and one to connect to the next node.

Inserting elements at the beginning (pushfirst()) and at the end (pushlast()) are faster in a doubly-linked list, as compared to an array.

Example:

#include<iostream>
using namespace std;

struct Node {
   int data;
   struct Node *prev;
   struct Node *next;
};

struct Node* head = NULL;

void insert(int new_data) {
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   new_node->data = new_data;
   new_node->prev = NULL;
   new_node->next = head;
   if(head != NULL)
      head->prev = new_node ;
   head = new_node;
}

void display() {
   struct Node* ptr;
   ptr = head;
   while(ptr != NULL) {
      cout<< ptr->data <<" ";
      ptr = ptr->next;
   }
}

int main() {
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   cout<<"The linked list is: ";
   display();
   return 0;
}

In summary, various types of dynamic data structures are used in C++ programming to store and manipulate data efficiently. The choice depends on the specific requirements of the algorithm or application.

Reference

The content in this document is based on the original notes provided in Azerbaijani. For further details, you can refer to the original document using the following link:

Original Note - Azerbaijani Version