Array

An array is a type of linear data structure that is defined as a collection of

elements with same or different data types. They exist in both single dimension
and multiple dimensions. These data structures come into picture when there is a
necessity to store multiple elements of similar nature together at one place.

The difference between an array index and a memory address is that the array
index acts like a key value to label the elements in the array. However, a memory
address is the starting address of free memory available.

Following are the important terms to understand the concept of Array.

Element − Each item stored in an array is called an element.

Index − Each location of an element in an array has a numerical index, which is

used to identify the element.
 Array
data_type array_name[array_size];

Need for Arrays

Arrays are used as solutions to many problems from the small sorting problems to
more complex problems like travelling salesperson problem. There are many data
structures other than arrays that provide efficient time and space complexity for
these problems, so what makes using arrays better? The answer lies in the random
access lookup time.

Arrays provide O(1) random access lookup time. That means, accessing the
1st index of the array and the 1000th index of the array will both take the same time.
This is due to the fact that array comes with a pointer and an offset value. The
pointer points to the right location of the memory and the offset value shows how
far to look in the said memory.

int arr[] = { 1, 2, 3, 4, 5 };
char arr[5] = { 'a', 'b', 'c', 'd', 'e' };
float arr[10] = { 1.4, 2.0, 24, 5.0, 0.0 };
 Array Representation
Arrays are represented as a collection of buckets where each bucket stores one
element. These buckets are indexed from '0' to 'n-1', where n is the size of that
particular array. For example, an array with size 10 will have buckets indexed from
0 to 9.
This indexing will be similar for the multidimensional arrays as well. If it is a 2-
dimensional array, it will have sub-buckets in each bucket. Then it will be indexed
as array_name[m][n], where m and n are the sizes of each level in the array.

Index starts with 0.

Array length is 9 which means it can store 9 elements.
Each element can be accessed via its index. For example, we can fetch an element
 Basic Operations in Arrays
Traverse − print all the array elements one by one.
Insertion − Adds an element at the given index.
Deletion − Deletes an element at the given index.
Search − Searches an element using the given index or by the value.
Update − Updates an element at the given index.
Display − Displays the contents of the array.
Insertion of Array
1.Start
2. Create an Array of a desired datatype and size.
3. Initialize a variable 'i' as 0.
4. Enter the element at ith index of the array.
5. Increment i by 1.
6. Repeat Steps 4 & 5 until the end of the array.
7. Stop
arr = [1, 2, 3, 4, 5]
for i in range(len(arr)):
print(arr[i], end=" ")
 Array – Insertion Operation
# Example usage arr = [1, 2, 3, 4, 5]
x = 10 # Element to be inserted
pos = 2 # Position to insert the element
arr.insert(pos, x)
# Print the updated list
print("Updated List:", arr)
 Array - Deletion Operation
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that K<=N. Following is the
algorithm to delete an element available at the K th position of LA.
1.Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
arr = [10, 20, 30, 40, 50]
# Value to delete key = 40
if key in arr:
arr.remove(key)
else:
print("Element Not Found")
Output: [10, 20, 30, 50]
 Array - Search Operation
Searching an element in the array using a key; The key element sequentially compares every value in the array to
check if the key is present in the array or not.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that K<=N. Following is the algorithm to
find an element with a value of ITEM using sequential search.
Start
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop
# Function to implement search operation
def find_element(arr, n, key):
for i in range(n):
if arr[i] == key:
return i
return -1
 Array - Traversal Operation
Algorithm
1 Start
2. Initialize an Array of certain size and datatype.
3. Initialize another variable ‘i’ with 0.
4. Print the ith value in the array and increment i.
5. Repeat Step 4 until the end of the array is reached.
6. End
# This list will store integer type elements
arr = [1, 2, 3, 4, 5]
# Traversing over arr
for i in range(len(arr)):
print(arr[i], end=" ")
 Array - Update Operation
Update operation refers to updating an existing element from the array at a given index.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that K<=N.
Following is the algorithm to update an element available at the Kth position of LA.
1.Start
2. Set LA[K-1] = ITEM
3. Stop
LA = [1,3,5,7,8]
("The original array elements are :");
for x in range(len(LA)):
print("LA", [x], " = ", LA[x])
LA[2] = 10
print("The array elements after updation are: ")
for x in range(len(LA)):
print("LA", [x], " = ", LA[x])
 Array - Display Operation

This operation displays all the elements in the entire array using a print
statement.
Algorithm
Consider LA is a linear array with N elements. Following is the algorithm to
display an array elements.
1.Start
2. Print all the elements in the Array
3. Stop
LA = [2,3,4,5,6]
print("The array elements are: ")
for x in range(len(LA)):
print("LA", [x], " = " , LA[x])
 Linked List

A linked list is a linear data structure which can store a collection of "nodes"
connected together via links i.e. pointers. Linked lists nodes are not stored at a
contiguous location, rather they are linked using pointers to the different
memory locations. A node consists of the data value and a pointer to the
address of the next node within the linked list.

A linked list is a dynamic linear data structure whose memory size can be
allocated or de-allocated at run time based on the operation insertion or
deletion, this helps in using system memory efficiently. Linked lists can be used
to implement various data structures like a stack, queue, graph, hash maps,
etc.
 Linked List

A linked list starts with a head node which points to the first node. Every node
consists of data which holds the actual data (value) associated with the node
and a next pointer which holds the memory address of the next node in the
linked list. The last node is called the tail node in the list which points
to null indicating the end of the list.
Linked Lists vs Arrays
In case of arrays, the size is given at the time of creation and so arrays are of
fixed length where as Linked lists are dynamic in size and any number of nodes
can be added in the linked lists dynamically. An array can accommodate similar
types of data types where as linked lists can store various nodes of different
data types.
 Types of Linked List
Singly Linked Lists

Singly linked lists contain two "buckets" in one node; one bucket holds the data
and the other bucket holds the address of the next node of the list. Traversals
can be done in one direction only as there is only a single link between two
nodes of the same list.
 Types of Linked List
Doubly Linked Lists

Doubly Linked Lists contain three "buckets" in one node; one bucket holds the
data and the other buckets hold the addresses of the previous and next nodes
in the list. The list is traversed twice as the nodes in the list are connected to
each other from both sides.
 Types of Linked List
Circular Linked Lists

Circular linked lists can exist in both singly linked list and doubly linked list.
Since the last node and the first node of the circular linked list are connected,
the traversal in this linked list will go on forever until it is broken.
 Basic Operations in Linked List

Insertion − Adds an element at the beginning of the list.

Deletion − Deletes an element at the beginning of the list.
Display − Displays the complete list.
Search − Searches an element using the given key.
Delete − Deletes an element using the given key.
 Linked List - Insertion Operation

First, create a node using the same structure and find the location where it has
to be inserted.

we are inserting a node B (New Node), between A (Left Node) and C (Right Node).
Then point B next to C
 Linked List - Insertion Operation

This will put the new node in the middle of the two. The new list should look like this
Insertion at Beginning
1. START
2. Create a node to store the data
3. Check if the list is empty
4. If the list is empty, add the data to the node and assign the head pointer to it.
5. If the list is not empty, add the data to a node and link to the current head. Assign
the head to the newly added node.
6. END
Linked List: [ 50 44 30 22 12 ]
Insertion at Ending
1. START
2. Create a new node and assign the data
3. Find the last node
4. Point the last node to new node
5. END
Linked List: [ 12 22 30 44 50 ]
Insertion at a Given Position
1 START
2. Create a new node and assign data to it
3. Iterate until the node at position is found
4. Point first to new first node
5. END
Linked List: [ 22 12 30 ]
 Linked List - Deletion Operation

First, locate the target node to be removed, by using searching algorithms.

Deletion at Beginning

1. START
2. Assign the head pointer to the next node in the list
3. END
Linked List: [ 55 40 30 22 12 ]
Linked List after deletion: [ 40 30 22 12 ]

Deletion at Ending
1. 1. START
2. Iterate until you find the second last element in the list.
3. Assign NULL to the second last element in the list.
4. END
Linked List: [ 55 40 30 22 12 ]
Linked List after deletion: [ 55 40 30 22 ]

Deletion at a Given Position

1. START
2. Iterate until find the current node at position in the list.
3. Assign the adjacent node of current node in the list to its previous node.
4. END
Linked List: [ 55 40 30 22 12 ]
Linked List after deletion: [ 55 40 22 12 ]
 Linked List - Search Operation

Searching for an element in the list using a key element. This operation is done in the
same way as array search; comparing every element in the list with the key element
given.

1 START
2 If the list is not empty, iteratively check if the list contains the key
3 If the key element is not present in the list, unsuccessful search
4 END

Linked List: [ 55 40 30 22 12 ]
Element to be searched is: 30
Element is found
 Linked List - Traversal Operation

The traversal operation walks through all the elements of the list in an order and
displays the elements in that order.

1.START
2. While the list is not empty and did not reach the end of the list, print the data in each
node
3. END

Linked List: [ 30 22 12 ]
 What is Doubly Linked List?

Doubly Linked List is a variation of Linked list in which navigation is possible in both
ways, forward as well as backward easily as compared to Single Linked List. Following
are the important terms to understand the concept of doubly linked list.

Link − Each link of a linked list can store a data called an element.
Next − Each link of a linked list contains a link to the next link called Next.
Prev − Each link of a linked list contains a link to the previous link called Prev.
Linked List − A Linked List contains the connection link to the first link called First and
to the last link called Last.

Doubly Linked List contains a link element called first and last.
Each link carries a data field(s) and a link field called next.
Each link is linked with its next link using its next link.
Each link is linked with its previous link using its previous link.
The last link carries a link as null to mark the end of the list.
 Basic Operations in Doubly Linked List

Insertion − Adds an element at the beginning of the list.

Insert Last − Adds an element at the end of the list.
Insert After − Adds an element after an item of the list.
Deletion − Deletes an element at the beginning of the list.
Delete Last − Deletes an element from the end of the list.
Delete − Deletes an element from the list using the key.
Display forward − Displays the complete list in a forward manner.
Display backward − Displays the complete list in a backward manner.
 Doubly Linked List - Insertion at the Beginning

In this operation, we create a new node with three compartments, one containing the
data, the others containing the address of its previous and next nodes in the list. This
new node is inserted at the beginning of the list.

1.START
2. Create a new node with three variables: prev, data, next.
3. Store the new data in the data variable
4. If the list is empty, make the new node as head.
5. Otherwise, link the address of the existing first node to the next variable of the
new node, and assign null to the prev variable.
6. Point the head to the new node.
7. END

Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10)

 Doubly Linked List - Insertion at the End

In this insertion operation, the new input node is added at the end of the doubly
linked list; if the list is not empty. The head will be pointed to the new node, if the list
is empty.

1.START
2. If the list is empty, add the node to the list and point the head to it.
3. If the list is not empty, find the last node of the list.
4. Create a link between the last node in the list and the new node.
5. The new node will point to NULL as it is the new last node.
6. END

Doubly Linked List: (4,1) (3,30) (2,20) (1,10) (5,40) (6,56)

 Doubly Linked List - Deletion at the Beginning

This deletion operation deletes the existing first nodes in the doubly linked list. The
head is shifted to the next node and the link is removed.

1.START
2. Check the status of the doubly linked list
3. If the list is empty, deletion is not possible
4. If the list is not empty, the head pointer is shifted to the next node.
5. END

Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10)

List after deleting first record: (5,40) (4,1) (3,30) (2,20) (1,10)
 What is Circular Linked List?

Circular Linked List is a variation of Linked list in which the first element
points to the last element and the last element points to the first element. Both
Singly Linked List and Doubly Linked List can be made into a circular linked
list.
Singly Linked List as Circular
In singly linked list, the next pointer of the last node points to the first node.
 Applications of circular linked lists
Multiplayer games use this to give each player a chance to play.

A circular linked list can be used to organize multiple running

applications on an operating system. These applications are iterated
over by the OS.

Circular linked lists can be used in resource allocation problems.

Circular linked lists are commonly used to implement circular buffers,

Circular linked lists can be used in simulation and gaming.

 Doubly Linked List as Circular

In doubly linked list, the next pointer of the last node points to the first node
and the previous pointer of the first node points to the last node making the
circular in both directions.

The last link's next points to the first link of the list in both cases of singly as well
as doubly linked list.

The first link's previous points to the last of the list in case of doubly linked list.
 Basic Operations in Circular Linked List

Insert − Inserts an element at the start of the list.

delete − Deletes an element from the start of the list.
display − Displays the list.
 Circular Linked List - Insertion Operation

The insertion operation of a circular linked list only inserts the element at the
start of the list. This differs from the usual singly and doubly linked lists as
there is no particular starting and ending points in this list. The insertion is
done either at the start or after a particular node (or a given position) in the
list.

1 START
2. Check if the list is empty
3. If the list is empty, add the node and point the head to this node
4. If the list is not empty, link the existing head as the next node to the new
node.
5. Make the new node as the new head.
6. END

Circular Linked List: [ (6,56) (5,40) (4,1) (3,30) (2,20) ]

Circular Linked List - Insertion Operation
 Circular Linked List - Deletion Operation
The Deletion operation in a Circular linked list removes a certain node from
the list. The deletion operation in this type of lists can be done at the
beginning, or a given position, or at the ending.

1.START
2. If the list is empty, then the program is returned.
3. If the list is not empty, we traverse the list using a current pointer that is set
to the head pointer and create another pointer previous that points to the last
node.
4. Suppose the list has only one node, the node is deleted by setting the head
pointer to NULL.
5. If the list has more than one node and the first node is to be deleted, the
head is set to the next node and the previous is linked to the new head.
6. If the node to be deleted is the last node, link the preceding node of the
last node to head node.
7. If the node is neither first nor last, remove the node by linking its preceding
node to its succeeding node.
8. END
Circular Linked List: (6,56) (5,40) (4,1) (3,30) (2,20)
List after deleting the first item: (5,40) (4,1) (3,30) (2,20)
 Circular Linked List - Displaying the List

The Display List operation visits every node in the list and prints them all in
the output.

1.START
2. Walk through all the nodes of the list and print them
3. END

Circular Linked List: [ (6,56) (5,40) (4,1) (3,30) (2,20) ]