Data Structures in C++

Page Contents

Data Structure includes :

Self-Referential Classes
Dynamic Memory Allocation and Data Structures
C++ Linked Lists
C++ Stacks
C++ Queues
C++ Tress

Self-Referential Classes

A self-referential class contains a pointer member that points to a class object of the same class type. For example, the definition

class Node
{
public:
Node(int);
void setData(int);
int getData() const;
void setNextPtr(Node *);
Node *getNextPtr() const;
private:
int data;
Node *nextPtr;
};

Dynamic Memory Allocation and Data Structures

Creating and maintaining dynamic data structures requires dynamic memory allocation, which enables a program to obtain more memory at execution time to hold new nodes. When that memory is no longer needed by the program, the memory can be released so that it can be reused to allocate other objects in the future. The limit for dynamic memory allocation can be as large as the amount of available physical memory in the computer or the amount of available virtual memory in a virtual memory system. Often, the limits are much smaller because of available memory must be shared among many programs.

Operators new and delete are essential to dynamic memory allocation. Operator new takes as an argument the type of the object is dynamically allocated and returns a pointer to an object of that type. For example, the statement

Node *newPtr=new Node(10);

allocates sizeof(Node) bytes, runs the Node constructor and stores a pointer to this memory in newPtr.If no memory is available, new throws a bad_alloc exception. The value 10 is the node’s data.

C++ Linked List

A linked list is a linear collection of self-referential class objects, called nodes, connected by pointer links hence, the term “linked” list. A linked list is accessed by a pointer to the first node of the list. Subsequent nodes are accessed by the link-pointer member stored in each node. By convention, the link pointer in the last node of a list is set to null(zero) to mark the end of the list. Data are stored in a linked list dynamically each node is created as necessary. A node can contain data of any type, including objects of other classes. If nodes contain base-class pointers or base-class references to base-class and derived-class objects related by inheritance, we can have a linked list of such nodes and use virtual function calls to process these objects polymorphically. Stacks and queues are also linear data structures

Lists of data can be stored in arrays, but linked lists provide several advantages. A linked list is appropriate when the number of data elements to be represented at one time is unpredictable. Linked lists are dynamic, so the length of a list can increase or decrease as necessary. The size of a “conventional” C++ array, however, cannot be altered, because the array size is fixed at compile time.”Conventional” arrays can become full. Linked lists become full only when the system has insufficient memory to satisfy dynamic storage allocation requests.

Linked list nodes are normally not stored contiguously in memory

List in C++
List in C++

The kind of linked list we have been discussing is a singly linked list the list begins with a pointer to the first node and each node contains a pointer to the next node “in sequence.”This list terminates with a node whose pointer member has the value 0. A singly linked list may be traversed in only one direction.

A circular, singly-linked list begins with a pointer to the first node and each node contains a pointer to the next node. The “last node” does not contain a 0 pointer; rather, the pointer in the last node points back to the first node, thus closing the “circle.”

A doubly linked list allows traversals both forwards and backward. Such a list is often implemented with two “start pointers” one that points to the first elements of the list to allow front-to-back traversal of the list and one that points to the last element of the list to allow back-to-front traversal of the list. Each node has both a forward pointer to the next node in the backward direction. Where in a circular,doubly-linked list, the forward pointer of the last node points to the first node, and the backward pointer of the first node points to the last node, thus closing the “circle

Program for a Linked list

#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(12);    
insert(22);    
insert(33);
insert(1);
insert(0);    
cout<<"The linked list is: ";    
display();     
return 0;  
}  

OUTPUT:

 The linked list is: 0 1 33 22 12  

C++ Stacks

Stacks in C++
Stacks in C++

A stack data structure allows nodes to be added to a stack and removed from a stack only at the top. For this reason, a stack is referred to as a last-in,first-out(LIFO) data structure. One way to implementation, the link member in the last node of the stack is set to null(zero) to indicate the bottom of the stack.

The primary member functions used to manipulate a stack are push and pop. Function push adds a new node to the top of the stack. Function pop removes a node from the top of the stack, stores the popped value in a reference variable that is passed to the calling function and returns true if the pop operation was successful(false otherwise).

Stacks have many interesting applications. For example, when a function call is made, the called function must know how to return to its caller, so the return address is pushed onto a stack. If a series of function calls occur, the successive return values are pushed onto the stack is last-in, first-out order so that each function can return to its caller. Stacks support recursive function calls in the same manner as conventional nonrecursive calls.

Stacks provide the memory for and store the values of, automatic variables on each invocation of a function. When the function returns to its caller or throws an exception, the destructor for each local object is called, the space for that function’s automatic variables is popped off the stack and those variables are no longer known to the program.

Stacks are used by compilers in the process of evaluating expressions and generating machine language code. The exercises explore several applications of stacks, including using them to develop a complete working compiler

C++ Queues

Queue in C++
Queue in C++

A queue is similar to a supermarket checkout line the first person in line is serviced first and other customers enter the line at the end and wait to be serviced. Queue nodes are removed only from the head of the queue and are inserted only at the tail of the queue. For this reason, a queue is referred to as a first-in, first-out(FIFO) data structure. The insert and remove operations are known as enqueue and dequeue.

Queues have many applications in computer systems. Most computers have only a single processor, so only one user at a time can be served. Entries for the other users are placed in a queue. Each entry gradually advances to the front of the queue as users receive service. The entry at the front of the queue is the next to receive service.

Queues are also used to support print spooling. A multiuser environment may have only a single printer. Many users may be generating outputs to be printed. If the printer is busy, other outputs may still be generated. These are “spooled” to disk(much as the thread is wound onto a spool) where they wait in a queue until the printer becomes available.

Information packets also wait in a queue in computer networks. Each time a packet arrives at a network node, it must be routed to the next node on the network along with the path to the packet’s final destination. The routing node routes one packet at a time, so additional packets are enqueued until the router can route them.

A file server in a computer network handles file access requests from many clients throughout the network. Servers have a limited capacity to service requests from clients. When that capacity is exceeded, clients requests wait in queues.

C++ Trees

Graph in C++
Graph in C++

Linked lists, stacks, and queues are linear data structures. A tree is a nonlinear, two-dimensional data structure with special properties. Tree nodes contain two or more links. But trees whose nodes all contain two links(none, one or both of which may be null). Taking an example as the root node(node B) is the first node in a tree. Each link in the root node refers to a child(nodes A and D). The left child (node A) is the root node of the left subtree(which contains the only node A), and the right child(node D) is the root node of the right subtree(which contains nodes D and C). The children of a single node are called siblings(e.g. nodes A and D are siblings). A node with no children is called a leaf node(e.g. nodes A and C are leaf nodes). Computer scientists normally draw trees from the root node down exactly the opposite of trees in nature.

Translate »