Prerequisites

Before you get started with data structures, you must know the basics of universal programming languages such as C, C++, and/or Python.

To determine where you stand when it comes to programming, we recommend that you take the prerequisite test that is provided. It includes multiple-choice questions and programming questions on basic concepts of object-oriented programming, functions, etc.

Note

• This test is not language-specific. You can use any of the languages that are provided on the HackerEarth platform.
• It is important that you read through all the resource materials to be able to solve the multiple-choice questions and programming questions in your practice tests and the final test. 

Take the pre-requisites test!

Introduction

Once you have stored some data in a variable, you require a mechanism to manipulate this data to solve problems. Data structures let you do this.

Data structures represent the way of organizing the data. This organization allows for efficient searching and retrieval of data. 

Remember, efficient data structures are key to designing efficient algorithms!

Types of data structures

Depending on the type of organization of data, they are primarily divided into two categories—linear and non-linear.

A linear data structure represents the organization of the data elements in a sequential manner. Each member element is connected to its previous element as well as the next element. For example, Arrays and Linked lists.

A non-linear data structure represents the organization of data elements that are not arranged sequentially or linearly. For example, Trees.

The following diagram shows you the different types of data structures:

Linear data structures

Array

• Arrays are the simplest and most frequently-used data structures. 
• The data elements are organized at contiguous memory locations. 
• It contains only homogenous data. In other words, it contains data of the same type only. You can not use 5 int type data and 5 float type data in an array of size 10.

The following example describes an array of size 10. All the elements in this array are integers and they are placed sequentially in the memory location.

To understand this better, you can imagine the arrangement of all N books of different types in a library. You segregate these books and you find out that there are 8 fictional books. You place them together. Then, you number them from 0 to 7. This represents an array of fictional books.

Note

• This numbering (0 to N-1) is called the index and it can be used to refer to the element in the array. For example, if you call index 4, then you are referring to the green book from the provided shelf that contains the fictional books.
• Indexing starts at 0 and ends at N-1, where N represents the number of elements in the array.

One dimensional array

The declaration of a 1D array is language-specific. In languages such as Python, the concept of lists is used instead of arrays. 

A 1D array can be declared as follows:

int marks[30];

Here, 30 informs the compiler that there are 30 elements of type integer in the array named ‘marks’.

This array will reserve 120 bytes of memory for the array—4 bytes for each of 30 integers. The values in it can be garbage values but they occupy adjacent memory locations.

The following example helps you find the average marks obtained by a class of 30 students in a test using arrays:

Furthermore, arrays are classified into one-dimensional array and two-dimensional array.

To practice arrays in C (programming language), click this. (Remember, you can always practice the same set of questions in any computer language!)

If you are preparing for a good interview, read 20+ Array Coding Problems and Questions from Programming Interviews.

Linked list

• In a linked list, as the name suggests, data elements are linked using pointers. 
• The data elements are not stored at contiguous memory locations, instead, they are linked to each other.
• Each element is a separate object.
• It contains nodes, where each node is made up of two items—data element and link to the next element. These two elements have the following properties:
• The first node is called the head and the last node is called the tail.
• The last node points to null.

You can consider the train carriages that are linked to each other. This represents a linked list. Linked list vs array

The advantage of linked lists is that they can be expanded in constant time. To create an array, you must allocate memory for a certain number of elements. If you want to add more elements to this array once it is exhausted, you are required to create a new array and copy the old array into the new array. This wastes memory if you have allocated extra space. Thus, to prevent this you can use linked lists. For more details on this, refer to this.

There are three types of linked lists—Singly, doubly, and circular linked lists. Some basic operations that you can perform on these lists are as follows:

• Traversing the list
• Inserting an item in the list
• Deleting an item from the list.

Traversing the list

Let’s assume that the head points to the first node of the list. To traverse, you perform the following steps:

1. Follow the pointers.
2. Display the contents of the nodes (or counts) as they traverse.
3. Stop when the next pointer == None.

A simple Python program describing the provided steps is shown as follows:

Inserting a node in a singly linked list at the beginning

To perform this operation, you are required to follow these steps:

1. Update the next pointer of the new node to point to the current node.
2. Update the head pointer to point to the new node.

A simple Python program describing the provided steps is shown as follows:

Task

Can you insert a node in a singly linked list at the middle and end? Try it out.

For hints, refer to operations on linked lists.

For more detailed information, refer to types of linked list. You can practice problems by referring to practice linked list.

Stack

• As the name suggests, a stack is a pile of objects. In computer science, stack refers to an ordered list in which operations such as insertion and deletion are performed at the end. 
• It has a varying length, that is, dynamic in nature.
• It contains homogeneous components, that is, data of the same type.
• It is also called Last in First out (LIFO) or First in Last Out (FILO) list.

Consider N number of plates placed one above the other on a table in your canteen. There is a long queue of students waiting to have their lunch. Here, the plate that was placed last will be removed first and the plate that was placed first will be removed at last. Thus, this scenario represents a stack.

While working on stacks, you can perform three basic operations—push(), pop(), isEmpty(), isFull(), and peek(). When an element is inserted in a stack, such an operation is called push and when an element is removed from the stack, such an operation is called pop. 

If you are trying to pop an empty stack then such a scenario is called underflow. Whereas, if you are trying to push an element in a full-stack, such a scenario is called overflow. 

 To read about this in detail, refer to stack and its basic operations.

Working and implementation of a stack

1. A pointer called TOP is used to keep track of the topmost element in the stack.
2. When you initialize the stack, you set its value to -1. This is performed to ensure that you can check if the stack is empty by comparing it with TOP == -1.
3. If you push() an element, you increase the value of TOP and place the new element in the position pointed to by TOP.
4. If you pop() an element, you return the element pointed to by TOP and reduce its value.

The following implementation of a stack is performed by using an array. In an array, you add elements from left to right and use variables to keep track of the index of the top element. A simple program describing this scenario is as follows:

Working of a queue

1. There are two pointers called the FRONT and REAR. 
2. The FRONT represents the first element in the queue. 
3. The REAR represents the last element of the queue. 
4. Initially, FRONT and REAR are set to -1.

While working on stacks, you can perform some operations—Enqueue(), dequeue(), isEmpty(), isFull(), peek(). To study in detail, refer to this.

An interesting visualization of how to implement a queue in arrays and linked lists is shown here

You can refer to this to practice some basic programming questions on queues.

Task

Try to solve the following question:

Write a program to reverse a queue Q. To access this queue, you are allowed to only use the methods of a queue.

TAKE PRACTICE TEST 1

![enter image description here][1]{:target='_blank'}