array, linked list, stack, queue Flashcards
What is an array?
An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).
Array Index
In an array, elements are identified by their indexes. Array index starts from 0.
Array Element
Elements are items stored in an array and can be accessed by their index.
Array Length
The length of an array is determined by the number of elements it can contain.
The representation of an array can be defined by its declaration. A declaration means
allocating memory for an array of a given size.
Array (Array Elements) ->
2 8 14 3 6 9
0 1 2 3 4 5 (Array Index)
int arr[5];
// This array will store integer type element
char arr[10];
// This array will store char type element
float arr[20];
// This array will store float type element
C++ and C arrays
/* Static Arrays are arrays that are declared before runtime
and are assigned values while writing the code.
*/
// The syntax of declaring a static array is:
<data><variable>[]
= {<data1>, <data2>,…..<dataN> };
// Example:
int arr[] = { 2, 5, 6, 9, 7, 4, 3 };
</dataN></data2></data1></variable></data>
Java array
int[] arr = new int[5]; // This array will store integer type element
C# array
let arr=[10,20,30];
// This array will store integer
let arr2 = [‘c’, ‘d’, ‘e’]
// This array will store characters
let arr3 = [28.5, 36.5, 40.2]
// This array will store floating elements
JavaScript array
arr = [10, 20, 30]
# This array will store integer
arr2 = [‘c’, ‘d’, ‘e’]
# This array will store characters
arr3 = [28.5, 36.5, 40.2]
# This array will store floating elements
Python array
static or compile-time memory allocation
the array element’s memory is allocated when a program is compiled. Here only a fixed size (i,e. the size that is mentioned in square brackets []) of memory will be allocated for storage
It is possible to allocate memory dynamically. So, dynamic memory allocation is the process of
assigning the memory space during the execution time or the run time.
int *array = new int[5];
Dynamic array C++
// <data> <variable> [ <Total>];
// Example:
int arr[10];
// Store integer elements
String arr[5];
// Store String type of elements</Total></variable></data>
Dynamic array c++
Empty list
list of integers
my_list = [1, 2, 3, 4]
my_list = []
my_list = [“Hello”, 1, 5.5]
Dynamic array Python3
int[] numArray = new int[] {};
Dynamic array C#
// Create array using literal
var x = [“a”, “b”, “c”];
// Create array using constructor
var x = new Array();
// Create array using constructor with items
var y = new Array(“a”, “b”, “c”);
JavaScript has dynamic arrays: their size is not predetermined, nor the type of data.
$arr = array(“a”,”b”,”c”);
PHP dynamic array
One-dimensional array (1-D arrays)
You can imagine a 1d array as a row, where elements are stored one after another.
Two-dimensional array
2-D Multidimensional arrays can be considered as an array of arrays or as a matrix consisting of rows and columns.
Col 0 1 2
0 5 4 10
1 2 3 44
2 11 1 2
Three-dimensional array
A 3-D Multidimensional array contains three dimensions, so it can be considered an array of two-dimensional arrays.
arr[2][row][col] contains two 2-d arrays (arr[0][row][col] and arr[1][row][col])
Array operation Traversal
Traverse through the elements of an array.
Array operation Insertion
Inserting a new element in an array.
Array operation Deletion
Deleting element from the array.
Array operation Searching
Search for an element in the array.
Array operation Sorting
Maintaining the order of elements in the array.
Advantages of arrays
Arrays allow random access to elements. This makes accessing elements by position faster.
Arrays have better cache locality which makes a pretty big difference in performance.
Arrays represent multiple data items of the same type using a single name.
Arrays store multiple data of similar types with the same name.
Array data structures are used to implement the other data structures like linked lists, stacks, queues, trees, graphs, etc.
Disadvantages of Arrays
As arrays have a fixed size, once the memory is allocated to them, it cannot be increased or decreased, making it impossible to store extra data if required. An array of fixed size is referred to as a static array.
Allocating less memory than required to an array leads to loss of data.
An array is homogeneous in nature so, a single array cannot store values of different data types.
Arrays store data in contiguous memory locations, which makes deletion and insertion very difficult to implement. This problem is overcome by implementing linked lists, which allow elements to be accessed sequentially
Application of Arrays
They are used in the implementation of other data structures such as array lists, heaps, hash tables, vectors, and matrices.
Database records are usually implemented as arrays.
It is used in lookup tables by computer.
It is used for different sorting algorithms such as bubble sort insertion sort, merge sort, and quick sort.
Linked List
Head -> (data, next) -> Null
Node
It is basically chains of nodes, each node contains information such as data and a pointer to the next node in the chain. In the linked list there is a head pointer, which points to the first element of the linked list, and if the list is empty then it simply points to null or nothing.
advantages of a linked list that is listed below, it will help you understand why it is necessary to know.
Dynamic Data structure:
The size of memory can be allocated or de-allocated at run time based on the operation insertion or deletion.
Ease of Insertion/Deletion:
The insertion and deletion of elements are simpler than arrays since no elements need to be shifted after insertion and deletion, Just the address needed to be updated.
Efficient Memory Utilization:
As we know Linked List is a dynamic data structure the size increases or decreases as per the requirement so this avoids the wastage of memory.
Implementation:
Various advanced data structures can be implemented using a linked list like a stack, queue, graph, hash maps, etc.
Types of linked lists:
Single-linked list
Double linked list
Circular linked list
Singly linked list
Traversal of items can be done in the forward direction only due to the linking of every node to its next node.
Head -> (data, next) -> (data, next) -> Null
class Node {
public:
int data;
Node* next;
};
Single linked list C++
struct Node {
int data;
struct Node* next;
};
single linked list C
class LinkedList {
Node head; // head of list
/* Node Class */
class Node {
int data;
Node next;
// Constructor to create a new node
Node(int d)
{
data = d;
next = null;
}
} }
Single linked list Java
Linked List class
class Node:
# Function to initialize the node object
def \_\_init\_\_(self, data):
self.data = data # Assign data
self.next = None # Initialize next as null
class LinkedList:
# Function to initialize the Linked List object
def \_\_init\_\_(self):
self.head = None
Singly linked list Python3
Singly linked list C#
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
// Linked List Class
var head; // head of list
/* Node Class */
class Node {
// Constructor to create a new node
constructor(d) {
this.data = d;
this.next = null;
}
}
Singly linked list Javascript
Singly linked list operations
Insertion: beginning, end, and specific location in list
Deletion: beginning, end, and specific node
Search: front, end, or anywhere in list to be retrieved
Display: display elements of single-linked list
Doubly linked list
Traversal of items can be done in both forward and backward directions as every node contains an additional prev pointer that points to the previous node.
Head-> (prev, data, next) -> NULL
NULL<-
/* Node of a doubly linked list /
class Node {
public:
int data;
Node next; // Pointer to next node in DLL
Node* prev; // Pointer to previous node in DLL
};
Doubly linked list C++
struct Node {
int data;
struct Node* next; // Pointer to next node in DLL
struct Node* prev; // Pointer to previous node in DLL
};
Doubly linked list C
public class DLL {
Node head; // head of list
/* Doubly Linked list Node*/
class Node {
int data;
Node prev;
Node next;
// Constructor to create a new node
// next and prev is by default initialized as null
Node(int d) { data = d; }
} }
DOubly linked list Java
class Node:
def __init__(self, next=None, prev=None, data=None):
self.next = next # reference to next node in DLL
self.prev = prev # reference to previous node in DLL
self.data = data
Doubly linked list Python3
public class DLL {
Node head; // head of list
/* Doubly Linked list Node*/
public class Node {
public int data;
public Node prev;
public Node next;
// Constructor to create a new node
// next and prev is by default initialized as null
Node(int d) { data = d; }
} }
Doubly linked list C#
var head; // head of list
/* Doubly Linked list Node */
class Node {
// Constructor to create a new node
// next and prev is by default initialized as null
constructor(val) {
this.data = val;
this.prev = null;
this.next = null;
}
}
Doubly linked list JavaScript
Doubly linked list Operations
Insertion: beginning, after a node, end, and before a node
Deletion: beginning, end, or a specific node
Display: display elements of the list
Circular linked list
A circular linked list is a type of linked list in which the first and the last nodes are also connected to each other to form a circle, there is no NULL at the end.
HEAD->(data,next)->(data,next)—|
|____________________________|
Circular linked list operations:
Insertion: empty list, begiing, end, between nodes
Deletion: beginning, end, specific node
Display: elements of linked list diaplayed
Advantages of linked lists
Dynamic nature: Linked lists are used for dynamic memory allocation.
Memory efficient: Memory consumption of a linked list is efficient as its size can grow or shrink dynamically according to our requirements, which means effective memory utilization hence, no memory wastage.
Ease of Insertion and Deletion: Insertion and deletion of nodes are easily implemented in a linked list at any position.
Implementation: For the implementation of stacks and queues and for the representation of trees and graphs.
The linked list can be expanded in constant time.
Disadvantages of linked lists
Memory usage: The use of pointers is more in linked lists hence, complex and requires more memory.
Accessing a node: Random access is not possible due to dynamic memory allocation.
Search operation costly: Searching for an element is costly and requires O(n) time complexity.
Traversing in reverse order: Traversing is more time-consuming and reverse traversing is not possible in singly linked lists
Applications of Linked List
Linear data structures such as stack, queue, and non-linear data structures such as hash maps, and graphs can be implemented using linked lists.
Dynamic memory allocation: We use a linked list of free blocks.
Implementation of graphs: Adjacency list representation of graphs is the most popular in that it uses linked lists to store adjacent vertices.
In web browsers and editors, doubly linked lists can be used to build a forwards and backward navigation button.
A circular doubly linked list can also be used for implementing data structures like Fibonacci heaps.
what is stack?
A stack is a linear data structure in which the insertion of a new element and removal of an existing element takes place at the same end represented as the top of the stack.
To implement the stack, it is required to maintain the pointer to the top of the stack, which is the last element to be inserted because we can access the elements only on the top of the stack.
Last In First Out (LIFO)
This strategy states that the element that is inserted last will come out first. You can take a pile of plates kept on top of each other as a real-life example. The plate which we put last is on the top and since we remove the plate that is at the top, we can say that the plate that was put last comes out first.
Operations on stack
push() to insert an element into the stack
pop() to remove an element from the stack
top() Returns the top element of the stack.
isEmpty() returns true if stack is empty else false.
size() returns the size of stack.
-> push item
_> pop item
top-> (item)
(item)
push()
Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.
Algorithm for push:
begin
if stack is full
return
endif
else
increment top
stack[top] assign value
end else
end procedure
pop()
Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.
Algorithm for pop:
begin
if stack is empty
return
endif
else
store value of stack[top]
decrement top
return value
end else
end procedure
top()
Returns the top element of the stack.
Algorithm for Top:
begin
return stack[top]
end procedure
isEmpty()
Returns true if the stack is empty, else false.
Algorithm for isEmpty:
begin
if top < 1
return true
else
return false
end procedure
Fixed size stack
As the name suggests, a fixed size stack has a fixed size and cannot grow or shrink dynamically. If the stack is full and an attempt is made to add an element to it, an overflow error occurs. If the stack is empty and an attempt is made to remove an element from it, an underflow error occurs.
Dynamic size stack
A dynamic size stack can grow or shrink dynamically. When the stack is full, it automatically increases its size to accommodate the new element, and when the stack is empty, it decreases its size. This type of stack is implemented using a linked list, as it allows for easy resizing of the stack.
Infix to Postfix stack
This type of stack is used to convert infix expressions to postfix expressions.
expression evaluation stack
This type of stack is used to evaluate postfix expressions.
Recursion stack
This type of stack is used to keep track of function calls in a computer program and to return control to the correct function when a function returns.
Memory management stack
This type of stack is used to store the values of the program counter and the values of the registers in a computer program, allowing the program to return to the previous state when a function returns.
Balanced parenthesis stack
This type of stack is used to check the balance of parentheses in an expression.
Undo-redo stack
This type of stack is used in computer programs to allow users to undo and redo actions.
Applications of the stack
Infix to Postfix /Prefix conversion
Redo-undo features at many places like editors, photoshop.
Forward and backward features in web browsers
Used in many algorithms like Tower of Hanoi, tree traversals, stock span problems, and histogram problems.
Backtracking is one of the algorithm designing techniques. Some examples of backtracking are the Knight-Tour problem, N-Queen problem, find your way through a maze, and game-like chess or checkers in all these problems we dive into someway if that way is not efficient we come back to the previous state and go into some another path. To get back from a current state we need to store the previous state for that purpose we need a stack.
In Graph Algorithms like Topological Sorting and Strongly Connected Components
In Memory management, any modern computer uses a stack as the primary management for a running purpose. Each program that is running in a computer system has its own memory allocations
String reversal is also another application of stack. Here one by one each character gets inserted into the stack. So the first character of the string is on the bottom of the stack and the last element of a string is on the top of the stack. After Performing the pop operations on the stack we get a string in reverse order.
Stack also helps in implementing function call in computers. The last called function is always completed first.
Stacks are also used to implement the undo/redo operation in text editor.
A stack can be implemented using an array or a linked list. In an array-based implementation, the push operation is implemented by incrementing the index of the top element and storing the new element at that index. The pop operation is implemented by decrementing the index of the top element and returning the value stored at that index.
In a linked list-based implementation, the push operation is implemented by creating a new node with the new element and setting the next pointer of the current top node to the new node. The pop operation is implemented by setting the next pointer of the current top node to the next node and returning the value of the current top node.
Stacks are commonly used in computer science for a variety of applications, including the evaluation of expressions, function calls, and memory management. In the evaluation of expressions, a stack can be used to store operands and operators as they are processed. In function calls, a stack can be used to keep track of the order in which functions are called and to return control to the correct function when a function returns.
In memory management, a stack can be used to store the values of the program counter and the values of the registers in a computer program, allowing the program to return to the previous state when a function returns.
advantages of array implementation of stacks
Easy to implement.
Memory is saved as pointers are not involved.
disadvantages of array implementation of stacks
It is not dynamic i.e., it doesn’t grow and shrink depending on needs at runtime. [But in case of dynamic sized arrays like vector in C++, list in Python, ArrayList in Java, stacks can grow and shrink with array implementation as well].
The total size of the stack must be defined beforehand.
Advantages of linked list implementation of stacks
The linked list implementation of a stack can grow and shrink according to the needs at runtime.
It is used in many virtual machines like JVM.
Disadvantages of linked list implementation of stack
Requires extra memory due to the involvement of pointers.
Random accessing is not possible in stack.
A queue is a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order.
define a queue to be a list in which all additions to the list are made at one end, and all deletions from the list are made at the other end. The element which is first pushed into the order, the delete operation is first performed on that.
FIFO principle of queue
A Queue is like a line waiting to purchase tickets, where the first person in line is the first person served. (i.e. First come first serve).
Position of the entry in a queue ready to be served, that is, the first entry that will be removed from the queue, is called the front of the queue(sometimes, head of the queue), similarly, the position of the last entry in the queue, that is, the one most recently added, is called the rear (or the tail) of the queue. See the below figure.
Rear(1) Front(5)
(0)(1) (2) (3) (4)(5)
Enqueue()-> ()(10)(15)(20)(25)()->dequeue()
Characteristics of Queues
Queue can handle multiple data.
We can access both ends.
They are fast and flexible.
Like stacks, Queues can also be represented in an array: In this representation, the Queue is implemented using the array. Variables used in this case are
Queue: the name of the array storing queue elements.
Front: the index where the first element is stored in the array representing the queue.
Rear: the index where the last element is stored in an array representing the queue.
Linked List representation of queue
queue can also be represented using following entities:
Linked-lists,
Pointers, and
Structures.
Input restricted queue
This is a simple queue. In this type of queue, the input can be taken from only one end but deletion can be done from any of the ends.
Output restricted queue
This is also a simple queue. In this type of queue, the input can be taken from both ends but deletion can be done from only one end.
Circular queue
This is a special type of queue where the last position is connected back to the first position. Here also the operations are performed in FIFO order.
Double-ended queue (dequeue)
the insertion and deletion operations, both can be performed from both ends.
Priority queue
A priority queue is a special queue where the elements are accessed based on the priority assigned to them.
Basic Operations for queue in data structure
Enqueue() – Adds (or stores) an element to the end of the queue..
Dequeue() – Removal of elements from the queue.
Peek() or front()- Acquires the data element available at the front node of the queue without deleting it.
rear() – This operation returns the element at the rear end without removing it.
isFull() – Validates if the queue is full.
isNull() – Checks if the queue is empty.
Enqueue() operation in Queue adds (or stores) an element to the end of the queue.
The following steps should be taken to enqueue (insert) data into a queue:
Step 1: Check if the queue is full.
Step 2: If the queue is full, return overflow error and exit.
Step 3: If the queue is not full, increment the rear pointer to point to the next empty space.
Step 4: Add the data element to the queue location, where the rear is pointing.
Step 5: return success.
void enqueue(struct Queue* queue, int item)
{
if (isFull(queue))
return;
queue->rear = (queue->rear + 1) % queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
printf(“%d enqueued to queue\n”, item);
}
Dequeue(0 operation on Queue
Removes (or access) the first element from the queue.
The following steps are taken to perform the dequeue operation:
Step 1: Check if the queue is empty.
Step 2: If the queue is empty, return the underflow error and exit.
Step 3: If the queue is not empty, access the data where the front is pointing.
Step 4: Increment the front pointer to point to the next available data element.
Step 5: The Return success.
int dequeue(struct Queue* queue)
{
if (isEmpty(queue)) {
printf(“\nQueue is empty\n”);
return;
}
int item = queue->array[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size = queue->size - 1;
return item;
}
int front(struct Queue* queue)
{
if (isempty(queue))
return INT_MIN;
return queue->arr[queue->front];
}
Queue operation
This operation returns the element at the front end without removing it.
int rear(struct Queue* front)
{
if (front == NULL) {
printf(“Queue is empty.\n”);
return -1;
}
while (front->next != NULL) {
front = front->next;
}
return front->data; }
Queue operation
This operation returns the element at the rear end without removing it.
bool isEmpty(struct Queue* queue)
{
return (queue->size == 0);
}
Queue operation
This operation returns a boolean value that indicates whether the queue is empty or not.
bool isFull(struct Queue* queue)
{
return (queue->size == queue->capacity);
}
Queue operation
This operation returns a boolean value that indicates whether the queue is full or not.
Application of queue is common. In a computer system, there may be queues of tasks waiting for the printer, for access to disk storage, or even in a time-sharing system, for use of the CPU. Within a single program, there may be multiple requests to be kept in a queue, or one task may create other tasks, which must be done in turn by keeping them in a queue.
It has a single resource and multiple consumers.
It synchronizes between slow and fast devices.
In a network, a queue is used in devices such as a router/switch and mail queue.
Variations: dequeue, priority queue and double-ended priority queue.
