What is Data Structure?
In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.
What is Memory Allocation?
Memory allocation is the process of setting aside sections of memory in a program to be used to store variables, and instances of structures and classes.
Types of Memory Allocation
- Static Memory Allocation
- Dynamic Memory Allocation
Static Memory Allocation
When you declare a variable or an instance of a structure or class. The memory for that object is allocated by the operating system. The name you declare for the object can then be used to access that block of memory. This is known as static memory allocation.
Dynamic Memory Allocation
When you use dynamic memory allocation you have the operating system designate a block of memory of the appropriate size while the program is running. This is done either with the new operator or with a call to the malloc function. The block of memory is allocated and a pointer to the block is returned. This is then stored in a pointer to the appropriate data type.
Data Structures in Memory Allocation
There are several data structures that are used in memory allocation. Some of them are:
- Linked List
What is Array?
In computer science, an array data structure, or simply an array, is a data structure consisting of a collection of elements, each identified by at least one array index or key. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula.
What is Record?
A record is a data structure that groups together related items of data. These are slightly more complex than arrays as you can store more than one type of data together. For example, with a game, it could be useful to set up a data structure which collects a player’s login and their score in one structure.
Difference Between Array and Record
|Record is a collection of related data items.||Array is a collection of similar data items.|
|A record can have different types of data.||An array only have one data type.|
|Record is indexed by it’s field names.||Array is indexed by a series of integer numbers.|
What is Linked List?
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.
A linked list is a linear collection of data elements, called nodes, where the linear order is given by means of pointers.
Difference Between Array and Linked List
|An array is a collection of elements of a similar data type.||A linked list is a collection of objects known as a node consisting two parts, data and address.|
|Array elements store in a contiguous memory location.||Linked list elements can be stored anywhere in the memory or randomly stored.|
|Array works with fixed size memory which cannot be changed at the run time.||The Linked list works with dynamic memory. Memory size can be changed at the run time.|
|Array elements are independent of each other.||Linked list elements are linked to each other.|
|Array takes more time while performing any operation like insertion, deletion, etc.||Linked list takes less time while performing any operation like insertion, deletion, etc.|
|Accessing any element in an array is faster as the element in an array can be directly accessed through the index.||Accessing an element in a linked list is slower as it starts traversing from the first element of the linked list.|
|In the case of an array, memory is allocated at compile-time.||In the case of a linked list, memory is allocated at run time.|
|Memory utilization is inefficient in the array. For example, if the size of the array is 6, and array consists of 3 elements only then the rest of the space will be unused.||Memory utilization is efficient in the case of a linked list as the memory can be allocated or deallocated at the run time according to our requirement.|
What is Stack?
In computer science, a stack is an abstract data type that serves as a collection of elements, with two main principal operations: Push, which adds an element to the collection, and Pop, which removes the most recently added element that was not yet removed.
Stack works in LIFO (Last In First Out) sequence.
What is Queue
In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.
Queue works in FIFO (First In First Out) sequence.
Difference Between Stack and Queue
|Stacks are based on the LIFO principle, i.e., the element inserted at the last, is the first element to come out of the list.||Queues are based on the FIFO principle, i.e., the element inserted at the first, is the first element to come out of the list.|
|Insertion and deletion in stacks takes place only from one end of the list called the top.||Insertion and deletion in queues takes place from the opposite ends of the list. Insertion in rear and deletion in front.|
|Insert operation is called push operation.||Insert operation is called enqueue operation.|
|Delete operation is called pop operation.||Delete operation is called dequeue operation.|
|In stacks we maintain only one pointer to access the list.||In queues we maintain two pointers to access the list.|
|Stack is used in solving problems works on recursion.||Queue is used in solving problems having sequential processing.|
Memory Allocation Problems
If there is no space in data structure for new item to insert then the condition is called overflow. That means the maximum size of data structure is fulfilled.
If there is no element in data structure for delete then the condition is called underflow. That means the data structure is empty. To work with this data structure again you must need to insert.
Solution of Memory Allocation Problems
Underflow depends exclusively upon the given algorithm and the given data, and hence there is no direct control by the programmer. On the other hand, Overflow depends upon the arbitrary choice of the programmer. Generally, the number of elements in a stack fluctuates as elements are added to or removed from stack to handle overflow and underflow.
What is Garbage Collection?
The operating system of a computer may periodically collect all the deleted space onto the free storage list. The technique which does this collection is called garbage collection.
When Does Garbage Collection Take Place?
The garbage collection take place when there is only some minimum amount of space or no space at all left in the free storage list or when CPU is idle and has time to do the collection.
What is Compaction?
In the second step of garbage of garbage collection, the computer runs through the memory, collecting all untagged spaces onto the free storage list. This is called compaction.
Thanks for following us. Please notify us if need.