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
