Data Structures | Assignments

Data Structures - Assignments

In Emertxe each one of our Data Structures Algorithm Examples will ensure you apply the concept you have leant in your classroom. By solving these Data Structures Exercises, you will go through a systematic problem-solving approach which include requirement understanding, algorithm design, pseudocode creation, dry run and final execution. As you move from simple to more complex data Structures Exercises of each module it will slowly start building your self-confidence.

Chapter 1 : Single Linked List

A1: Write a function to insert the new data after the given data

Title

Insert After

Filename

sl_insert_after.c

Description

Write a function to insert the new data after the given data using Data Structure Algorithm Examples

Cases

List Empty
List Non-Empty
1. Given data present
2. Given data not present

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2
Sub-case:1

List Non-Empty
Given data present

Case-2
Sub-case:2

List Non-Empty
Given data not present

Example

If given_data = 40, new_data = 45

Example

If given_data = 60, new_data = 45

Input

10 -> 20 -> 30 -> 40 -> 50

Input

10 -> 20 -> 30 -> 40 -> 50

Output

10 -> 20 -> 30 -> 40 -> 45 -> 50

Output

Return DATA_NOT_FOUND

Prototype

int sl_insert_after(Slist *head, data_t g_data, data_t n_data);

head	: Pointer to the first node
g_data	: Given data
n_data	: New data to be inserted into the list
return value	: status (LIST_EMPTY, SUCCESS, DATA_NOT_FOUND)

A2: Write a function to insert the new data before the given data

Title

Insert Before

Filename

sl_insert_before.c

Description

Write a function to insert the new data before the given data.

Cases

List Empty
List Non-Empty
1. Given data present
2. Given data not present

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2
Sub-case:1

List Non-Empty
Given data present

Case-2
Sub-case:2

List Non-Empty
Given data not present

Example

If given_data = 40, new_data = 45

Example

If given_data = 60, new_data = 45

Input

10 -> 20 -> 30 -> 40 -> 50

Input

10 -> 20 -> 30 -> 40 -> 50

Output

10 -> 20 -> 30 -> 45 -> 40 -> 50

Output

Return DATA_NOT_FOUND

Case-3

Data found in the first

Example

If given_data = 10, new_data = 45

Input

10 -> 20 -> 30 -> 40 -> 50

Output

45 -> 10 -> 20 -> 30 -> 40 -> 50

Prototype

int sl_insert_after(Slist **head, data_t g_data, data_t n_data);

head	: Pointer to the first node
g_data	: Given data
n_data	: New data to be inserted into the list
return value	: status (LIST_EMPTY, SUCCESS, DATA_NOT_FOUND)

A3: Write a function to delete the given data in the single linked list

Title

Delete element

Filename

sl_delete_element.c

Description

Write a function to delete the given data in the single linked list.

Cases

List Empty
List Non-Empty
1. Given data present
2. Given data not present

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2
Sub-case:1

List Non-Empty
Given data present

Case-2
Sub-case:2

List Non-Empty
Given data not present

Example

If given_data = 40

Example

If given_data = 60

Input

10 -> 20 -> 30 -> 40 -> 50

Input

10 -> 20 -> 30 -> 40 -> 50

Output

10 -> 20 -> 30 -> 50

Output

Return DATA_NOT_FOUND

Prototype

int sl_insert_after(Slist **head, data_t g_data);

head	: Pointer to the first node
g_data	: Given data
return value	: status (LIST_EMPTY, SUCCESS, DATA_NOT_FOUND)

A4: Write a function to insert the given data exactly at the 'n' position in the single linked list

Title

Insert at ‘n’ position

Filename

sl_insert_nth.c

Description

Write a function to insert the given data exactly at the ‘n’ position in the single linked list. incorporating essential data structure algorithm examples for better understanding.

Cases

List Empty
List Non-Empty
1. Given ‘n’th position present
2. Given ‘n’th position not present

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2
Sub-case:1

List Non-Empty
Given data present

Case-2
Sub-case:2

List Non-Empty
Given data not present

Example

If n = 3, n_data = 23

Example

If n = 10, n_data = 23

Input

10 -> 20 -> 30 -> 40 -> 50

Input

10 -> 20 -> 30 -> 40 -> 50

Output

10 -> 20 -> 23 -> 30 -> 50

Output

Return POSITION_NOT_FOUND

Prototype

int sl_insert_after(Slist **head, int n, data_t n_data);

head	: Pointer to the first node
n	: Position number
n_data	: New data, to be inserted into the list
return value	: status (LIST_EMPTY, SUCCESS, POSITION_NOT_FOUND)

A5: Write a function to find the mid node in the given linke list

Title

Find Mid

Filename

sl_find_mid.c

Description

Write a function to find the mid node in the given linked list. Accompained by data structure algorithm example.

Cases

List Empty
List Non-Empty

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2
Sub-case:1

List Non-Empty
List contains Odd nodes

Case-2
Sub-case:2

List Non-Empty
List contains Even nodes

Input

10 -> 20 -> 30 -> 40 -> 50

Input

10 -> 20 -> 40 -> 50

Output

Prototype

int sl_find_mid(Slist *head, Slist **mid);

head	: Pointer to the first node
mid	: Pointer to the mid node
return value	: status (LIST_EMPTY, SUCCESS)

Note

Traverse the linked list only once

A6: Write a function to get nth node from the end of the linked list

Title

Get nth node from last

Filename

sl_get_nth_from_last.c

Description

Write a function to get the nth node from the end of the linked list. a common problem in data structure algorithms examples.

Cases

List Empty
List Non-Empty

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2

List Non-Empty

Input

10 -> 20 -> 30 -> 40 -> 50, n = 2

Output

40 (From the last, second node conatins the data 40)

Prototype

int sl_get_nth_from_last(Slist *head, int n);

head	: Pointer to the first node
g_data	: Given data
n	: Position from the last node
return value	: status (LIST_EMPTY, SUCCESS)

A7: Write a function to insert the new data in the already sorted linked list

Title

Insert Sorted

Filename

sl_insert_sorted.c

Description

Write a function to insert the new data in the already sorted linked list

Cases

List Empty
List Non-Empty

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2

List Non-Empty

Example

If n_data = 45

Input

10 -> 20 -> 30 -> 40 -> 50

Output

10 -> 20 -> 30 -> 40 -> 45 -> 50

Prototype

int sl_insert_after(Slist **head, data_t n_data);

head	: Pointer to the first node
n_data	: New data to be inserted into the sorted list
return value	: status (LIST_EMPTY, SUCCESS)

A8: Write a function to detect whether the given linked list is ending with loop or not

Title

Find loop

Filename

sl_find_loop.c

Description

Write a function to detect whether the given linked list is ending with loop or not incorporating data structure algorithm examples to illustrate practical implementation

Cases

List Empty
List Non-Empty

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2
Sub-Case:1

List Non-Empty

Input

Output

Loop detected.

Case-2
Sub-Case:2

List Non-Empty

Input

Output

Loop not detected.

Prototype

int sl_insert_after(Slist *head);

head	: Pointer to the first node
return value	: status (LIST_EMPTY, LOOP_DETECTED, LOOP_NOT_DETECTED)

Note

Traverse the linked list only once

A9: Write a function to sort the given single linked list

Title

Sort

Filename

sl_sort.c

Description

Write a function to sort the given single linked list.

Cases

List Empty
List Non-Empty

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2

List Non-Empty

Input

50 -> 40 -> 30 -> 20 -> 10

Output

10 -> 20 -> 30 -> 40 -> 50

Prototype

int sl_sort(Slist **head);

head	: Pointer to the first node
return value	: status (LIST_EMPTY, SUCCESS)

Note

Don’t swap the data present in the nodes, swap the nodes itself.

Title

Reverse

Filename

sl_reverse_iterative.c
sl_reverse_recursive.c

Description

Write a function to reverse the single linked list in both iterative and recursive methods

Cases

List Empty
List Non-Empty

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2

List Non-Empty

Input

50 -> 40 -> 30 -> 20 -> 10

Output

10 -> 20 -> 30 -> 40 -> 50

Prototype

int sl_sort(Slist **head);

head	: Pointer to the first node
return value	: status (LIST_EMPTY, SUCCESS)

A10: Write a function to reverse the single linked list in both iterative and recursive methods

Title

Reverse

Filename

sl_reverse_iterative.c
sl_reverse_recursive.c

Description

Write a function to reverse the single linked list in both iterative and recursive methods, incorporating data structure algorithm examples to illustrate the implementation process.

Cases

List Empty
List Non-Empty

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2

List Non-Empty

Input

50 -> 40 -> 30 -> 20 -> 10

Output

10 -> 20 -> 30 -> 40 -> 50

Prototype

int sl_sort(Slist **head);

head	: Pointer to the first node
return value	: status (LIST_EMPTY, SUCCESS)

A11: Write a function to remove the duplicates data present in the single linked list

Title

Remove Duplicates

Filename

sl_remove_duplicates.c

Description

Write a function to remove the duplicates data present in the single linked list, implementing a data structure algorithm example for efficient removal of duplicates

Cases

List Empty
List Non-Empty

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2

List Non-Empty

Input

5 -> 3 -> 4 -> 5 -> 2 -> 1 -> 4 -> 5 -> 3

Output

5 -> 3 -> 4 -> 2 -> 1

Prototype

int sl_sort(Slist **head);

head	: Pointer to the first node
return value	: status (LIST_EMPTY, SUCCESS)

A12: Write a function to merge two linked list into one

Title

Sorted Merge

Filename

sl_sorted_merge.c

Description

Write a function to merge two linked list into one

Cases

List Empty
List Non-Empty

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2

List Non-Empty

Input

List – 1
30 -> 10 -> 50
List – 2
20 -> 5 -> 35

Output

5 -> 10 -> 20 -> 30 -> 35 -> 50

Prototype

int sl_sort(Slist **head1, Slist **head2);

head1	: Pointer to the first node of the first linked list
head2	: Pointer to the first node of the second linked list
return value	: status (LISTS_EMPTY, SUCCESS)

Note

If lists are not sorted, sort it
If second list is EMPTY, no need to append it.
If first list is EMPTY, update head1 to the head2
If both list are EMPTY, return LISTS_EMPTY

Chapter 2 : Double Linked List

A1: Write a function to insert the new data after the given data

Title

Insert After

Filename

dl_insert_after.c

Description

Write a function to insert the new data after the given data.

Cases

List Empty
List Non-Empty
1. Given data present
2. Given data not present

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2
Sub-case:1

List Non-Empty
Given data present

Case-2
Sub-case:2

List Non-Empty
Given data not present

Example

If given_data = 40, new_data = 45

Example

If given_data = 60, new_data = 45

Input

10 -> 20 -> 30 -> 40 -> 50

Input

10 -> 20 -> 30 -> 40 -> 50

Output

10 -> 20 -> 30 -> 40 -> 45 -> 50

Output

Return DATA_NOT_FOUND

Prototype

int dl_insert_after(Dlist *head, data_t g_data, data_t n_data);

head	: Pointer to the first node
g_data	: Given data
n_data	: New data to be inserted into the list
return value	: status (LIST_EMPTY, SUCCESS, DATA_NOT_FOUND)

A2: Write a function to insert the new data before the given data

Title

Insert Before

Filename

dl_insert_before.c

Description

Write a function to insert the new data before the given data.

Cases

List Empty
List Non-Empty
1. Given data present
2. Given data not present

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2
Sub-case:1

List Non-Empty
Given data present

Case-2
Sub-case:2

List Non-Empty
Given data not present

Example

If given_data = 40, new_data = 45

Example

If given_data = 60, new_data = 45

Input

10 -> 20 -> 30 -> 40 -> 50

Input

10 -> 20 -> 30 -> 40 -> 50

Output

10 -> 20 -> 30 -> 45 -> 40 -> 50

Output

Return DATA_NOT_FOUND

Case-3

Data found in the first

Example

If given_data = 10, new_data = 45

Input

10 -> 20 -> 30 -> 40 -> 50

Output

45 -> 10 -> 20 -> 30 -> 40 -> 50

Prototype

int sl_insert_after(Dlist **head, data_t g_data, data_t n_data);

head	: Pointer to the first node
g_data	: Given data
n_data	: New data to be inserted into the list
return value	: status (LIST_EMPTY, SUCCESS, DATA_NOT_FOUND)

A3: Write a function to delete the given data in the double linked list

Title

Delete element

Filename

dl_delete_element.c

Description

Write a function to delete the given data in the double linked list.

Cases

List Empty
List Non-Empty
1. Given data present
2. Given data not present

Case-1

List Empty

Input

Head = NULL

Output

return LIST_EMPTY

Case-2
Sub-case:1

List Non-Empty
Given data present

Case-2
Sub-case:2

List Non-Empty
Given data not present

Example

If given_data = 40

Example

If given_data = 60

Input

10 -> 20 -> 30 -> 40 -> 50

Input

10 -> 20 -> 30 -> 40 -> 50

Output

10 -> 20 -> 30 -> 50

Output

Return DATA_NOT_FOUND

Prototype

int sl_insert_after(Dlist **head, data_t g_data);

head	: Pointer to the first node
g_data	: Given data
return value	: status (LIST_EMPTY, SUCCESS, DATA_NOT_FOUND)

Chapter 3 : Stacks

A1: Write a function to convert the given infix expression into the postfix form

Title

Infix to Postfix

Filename

infix_postfix.c

Description

Write a function to convert the given infix expression into the postfix form

Cases

Single digit numbers
Multiple digit numbers

Case-1

Single digit numbers

Input

2 * 3 – 3 + 8 / 4 / (1 + 1)

Output

2 3 * 3 – 8 4 / 1 1 + / +

Case-2

Multiple digit numbers

Input

2 * 30 – 3 + 8 / 4 / (10 + 1)

Output

2, 30, *, 3, –, 8, 4, /, 10, 1, +, / ,+

Sample Prototype

Char * infix_postfix(char *infix);

infix	: Pointer the base address of the infix array
return	: Pointer the base address of the postfix array

A2: Write a function to evaluate the postfix expression

Title

Postfix Evaluation

Filename

postfix_eval.c

Description

Write a function to evaluate the postfix expression.

Cases

Single digit numbers
Multiple digit numbers

Case-1

Single digit numbers

Input

2 3 * 3 – 8 4 / 1 1 + / +

Output

Case-2

Multiple digit numbers

Input

2, 30, *, 3, –, 8, 4, /, 10, 1, +, / ,+

Output

57.181

Sample Prototype

double infix_postfix(char *postfix);

Postfix	: Pointer the base address of the postfix array
return	: Result of the expression in double.

A3: Write a function to convert the given infix expression into the prefix form

Title

Infix to Prefix

Filename

infix_prefix.c

Description

Write a function to convert the given infix expression into the prefix form

Cases

Single digit numbers
Multiple digit numbers

Case-1

Single digit numbers

Input

2 * 3 – 3 + 8 / 4 / (1 + 1)

Output

+ – * 2 3 3 / / 8 4 + 1 1

Case-2

Multiple digit numbers

Input

2 * 30 – 3 + 8 / 4 / (10 + 1)

Output

+, -, *, 2, 30, 3, /, /, 8, 4, +, 10, 1

Sample Prototype

Char * infix_prefix(char *infix);

infix	: Pointer the base address of the infix array
return	: Pointer the base address of the prefix array

A4: Write a function to evaluate the prefix expression

Title

Prefix Evaluation

Filename

prefix_eval.c

Description

Write a function to evaluate the prefix expression.

Cases

Single digit numbers
Multiple digit numbers

Case-1

Single digit numbers

Input

+ – * 2 3 3 / / 8 4 + 1 1

Output

Case-2

Multiple digit numbers

Input

+, -, *, 2, 30, 3, /, /, 8, 4, +, 10, 1

Output

57.181

Sample Prototype

double infix_postfix(char *prefix);

Prefix	: Pointer the base address of the prefix array
return	: Result of the expression in double.

Chapter 4 : Sorting

A1: Write a function to sort given array using bubble sort

Title

Bubble Sort

Filename

bubble.c

Description

Write a function to sort given array using bubble sort

Input

5 4 3 2 1

Output

1 2 3 4 5

Sample Prototype

void bubble_sort(int *ptr)

ptr	: Base address of the integer array
return	: void

A2: Write a function to sort given array using insertion sort

Title

Insertion Sort

Filename

insertion.c

Description

Write a function to sort given array using insertion sort

Input

5 4 3 2 1

Output

1 2 3 4 5

Sample Prototype

void insertion_sort(int *ptr)

ptr	: Base address of the integer array
return	: void

A3: Write a function to sort given array using selection sort

Title

Selection Sort

Filename

selection.c

Description

Write a function to sort given array using selection sort

Input

5 4 3 2 1

Output

1 2 3 4 5

Sample Prototype

void selection_sort(int *ptr)

ptr	: Base address of the integer array
return	: void

Chapter 5 : Trees

A1: Write a function to delete the given data from the BST

Description	Write a function to delete the given data from the bst
Title	Delete nodes
Filename	bst_delete_node.c
Cases	Node to be deleted may be, Leaf node Node with single child Node with two children
Case-1	Leaf node
Input
Output
Case-2	Node with single child
Input
Output	After deleting 30
Case-3	Node with two children
Input
Output	After deleting 50

A2: Write a function to find the height of the given tree

Description	Write a function to find the height of the given tree
Title	Find height
Filename	bst_find_height.c
Cases	Tree Empty Tree Non-Empty
Case-1	Tree Non-Empty
Input
Output	Height = 2

Chapter 6 : Hashing

A1: Writ a function to create the hash table

Description	Write a function to create the hash table
Title	Create hash table
Filename	create_hash_table.c
Input	Size
Output	Hash table with the given size

A2: Write a function to search the data in the hash table

Description	Write a function to search the data in the hash table
Title	Hash table search
Filename	hash_search.c
Input	Hash Table
Output	Address of the node where data is found in the hash table

A3: Write a function to insert the data in the hash table

Description	Write a function to insert the data in the hash table
Title	Hash table insert
Filename	hash_insert.c
Input	Hash Table
Output	Status [SUCCESS / FAILURE]

A4: Write a function to delete the given item from the hash table

Description	Write a function to delete the given item from the hash table
Title	Hash delete element
Filename	hash_delete_element.c
Input	Hash Table
Output	Status [SUCCESS / FAILURE]

A5: Write a function to delete the entire hash table

Description	Write a function to delete the entire hash table
Title	Hash Table delete
Filename	hash_table_delete.c
Input	Hash Table
Output	Status [SUCCESS / FAILURE]