Array:-

An array is a data structure for storing more than one data item that has a similar data type.
The items of an array are allocated at adjacent memory locations. These memory locations are
called elements of that array.
The total number of elements in an array is called length. The details of an array are accessed about
its position. This reference is called index or subscript.

1. An array is a container of elements.

2. Elements have a specific value and data type, like "ABC", TRUE or FALSE, etc.
3. Each element also has its own index, which is used to access the element

 Elements are stored at contiguous memory locations.

 An index is always less than the total number of array items.
 In terms of syntax, any variable that is declared as an array can store multiple values.
 Almost all languages have the same comprehension of arrays but have different ways of
declaring and initializing them.
 However, three parts will always remain common in all the initializations, i.e., array name,
elements, and the data type of elements

 Array name: necessary for easy reference to the collection of elements

 Data Type: necessary for type checking and data integrity
 Elements: these are the data values present in an array

Why do we need arrays?

Here, are some reasons for using arrays:

 Arrays are best for storing multiple values in a single variable

 Arrays are better at processing many values easily and quickly
 Sorting and searching the values is easier in arrays

Creating an Array in C++

C++ language is more flexible than Python when it comes to creating arrays. You can create arrays
in three ways mentioned ahead.
Ways to Declare an Array in C++
You can declare an array in three syntax variants. Which one suits your program; this choice is
based on your program requirements.

Declaration by Size

Syntax

dataType arrayName[arraySize];

Example

int balance[3];

Declaration Initialization Array Items Only

Syntax

dataType arrayName[] = {array, items};

Example

int balance[] = { 300, 200, 100 };

Declaration by Size and Initialization Array Items

Syntax

dataType arrayName[arraySize] = {array, items};

Example

int balance[3] = { 300, 200, 100 };

Array Operations in C++

Unlike Python, in C++ you have to program the logic yourself for performing the insert, delete,
search update and traverse operations on C++ arrays.

Insert
The logic for insertion operation goes as follows:

 loop through the array items

 shift them to a greater index
 add a new array item at a given index
Dynamic Array:-
A dynamic array is quite similar to a regular array, but its size is modifiable during program
runtime. Dynamic Array elements occupy a contiguous block of memory.

Once an array has been created, its size cannot be changed. However, a dynamic array is different.
A dynamic array can expand its size even after it has been filled.

During the creation of an array, it is allocated a predetermined amount of memory. This is not the
case with a dynamic array as it grows its memory size by a certain factor when there is a need.

Factors impacting performance of Dynamic Arrays

1. If an array has a small size and a small growth factor, it will keep on reallocating memory
more often. This will reduce the performance of the array.
2. If an array has a large size and a large growth factor, it will have a huge chunk of unused
memory. Due to this, resize operations may take longer. This will reduce the performance of
the array

Linked List
o Linked List can be defined as collection of objects called nodes that are randomly stored in the
memory.
o A node contains two fields i.e. data stored at that particular address and the pointer which contains
the address of the next node in the memory.
o The last node of the list contains pointer to the null.

Uses of Linked List

o The list is not required to be contiguously present in the memory. The node can reside any where
in the memory and linked together to make a list. This achieves optimized utilization of space.
o list size is limited to the memory size and doesn't need to be declared in advance.
o Empty node can not be present in the linked list.
 o We can store values of primitive types or objects in the singly linked list.

Singly linked list or One way chain

Singly linked list can be defined as the collection of ordered set of elements. The number of elements may
vary according to need of the program. A node in the singly linked list consist of two parts: data part and
link part. Data part of the node stores actual information that is to be represented by the node while the
link part of the node stores the address of its immediate successor.

One way chain or singly linked list can be traversed only in one direction. In other words, we can say that
each node contains only next pointer, therefore we can not traverse the list in the reverse direction.

Consider an example where the marks obtained by the student in three subjects are stored in a linked list
as shown in the figure.

In the above figure, the arrow represents the links. The data part of every node contains the marks
obtained by the student in the different subject. The last node in the list is identified by the null pointer
which is present in the address part of the last node. We can have as many elements we require, in the
data part of the list.

Complexity

Data Time Complexity S

Structure C

Average Worst

Acces Search Insertion Deletion Acces Search Insertion Deletion

s s

Singly θ(n) θ(n) θ(1) θ(1) O(n) O(n) O(1) O(1)

Linked
List

Operations on Singly Linked List

There are various operations which can be performed on singly linked list. A list of all such operations is
given below.

Node Creation
1. struct node   
2. {  
3.     int data;   
4.     struct node *next;  
5. };  
6. struct node *head, *ptr;   
7. ptr = (struct node *)malloc(sizeof(struct node *));  
Insertion
The insertion into a singly linked list can be performed at different positions. Based on the position of the
new node being inserted, the insertion is categorized into the following categories.

SN Operation Description

1 Insertion at It involves inserting any element at the front of the list. We just need to a few
beginning to make the new node as the head of the list.

2 Insertion at end of It involves insertion at the last of the linked list. The new node can be inserted
the list node in the list or it can be inserted as the last one. Different logics are imple
scenario.

3 Insertion after It involves insertion after the specified node of the linked list. We need to skip
specified node number of nodes in order to reach the node after which the new node will be

Deletion and Traversing

The Deletion of a node from a singly linked list can be performed at different positions. Based on the
position of the node being deleted, the operation is categorized into the following categories.

SN Operation Description

1 Deletion at It involves deletion of a node from the beginning of the list. This is the simple
beginning among all. It just need a few adjustments in the node pointers.

2 Deletion at the It involves deleting the last node of the list. The list can either be empty or fu
end of the list is implemented for the different scenarios.
 3 Deletion after It involves deleting the node after the specified node in the list. we need to sk
specified node number of nodes to reach the node after which the node will be deleted. This
traversing through the list.

4 Traversing In traversing, we simply visit each node of the list at least once in order to pe
specific operation on it, for example, printing data part of each node present i

5 Searching In searching, we match each element of the list with the given element. If the
on any of the location then location of that element is returned otherwise null

Doubly linked list

Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well
as the next node in the sequence. Therefore, in a doubly linked list, a node consists of three parts: node
data, pointer to the next node in sequence (next pointer) , pointer to the previous node (previous
pointer). A sample node in a doubly linked list is shown in the figure.

A doubly linked list containing three nodes having numbers from 1 to 3 in their data part, is shown in the
following image.
Memory Representation of a doubly linked list
Memory Representation of a doubly linked list is shown in the following image. Generally, doubly linked list
consumes more space for every node and therefore, causes more expansive basic operations such as
insertion and deletion. However, we can easily manipulate the elements of the list since the list maintains
pointers in both the directions (forward and backward).

In the following image, the first element of the list that is i.e. 13 stored at address 1. The head pointer
points to the starting address 1. Since this is the first element being added to the list therefore
the prev of the list contains null. The next node of the list resides at address 4 therefore the first node
contains 4 in its next pointer.

We can traverse the list in this way until we find any node containing null or -1 in its next part.

Node Creation

1. struct node   
2. {  
3.     struct node *prev;  
4.     int data;  
5.     struct node *next;  
 6. };  
7. struct node *head;   

All the remaining operations regarding doubly linked list are described in the following table.

S Operation Description
N

1 Insertion at beginning Adding the node into the linked list at beginning.

2 Insertion at end Adding the node into the linked list to the end.

3 Insertion after specified Adding the node into the linked list after the specified node.
node

4 Deletion at beginning Removing the node from beginning of the list

5 Deletion at the end Removing the node from end of the list.

6 Deletion of the node having Removing the node which is present just after the node containing the
given data

7 Searching Comparing each node data with the item to be searched and return th
item in the list if the item found else return null.

8 Traversing Visiting each node of the list at least once in order to perform some sp
like searching, sorting, display, etc.

Assignment 2
Till now, we were using array data structure to organize the group of elements that are to be stored
individually in the memory. However, Array has several advantages and disadvantages which must be
known in order to decide the data structure which will be used throughout the program.

Array contains following limitations:

1. The size of array must be known in advance before using it in the program.
 2. Increasing size of the array is a time taking process. It is almost impossible to expand the size of
the array at run time.
3. All the elements in the array need to be contiguously stored in the memory. Inserting any element
in the array needs shifting of all its predecessors.

Linked list is the data structure which can overcome all the limitations of an array. Using linked list is
useful because,

1. It allocates the memory dynamically. All the nodes of linked list are non-contiguously stored in the
memory and linked together with the help of pointers.
2. Sizing is no longer a problem since we do not need to define its size at the time of declaration. List
grows as per the program's demand and limited to the available memory space.