Want to learn all the basic concepts of Data Structures from scratch?
And,
Looking for the best tutorial on web?
Don’t worry!
You’ve come to the right place.
I hope you have completed a programming language well.
And,
You have also practiced some questions in each topic.
If yes, Congrats!
But,
Trust me, If you don’t have the knowledge of data structures, then you will not feel the actual taste of coding.
Learning Data Structures along with the understanding of a programming language is like “icing on the cake“.
And,
The best part is:
If you have a better knowledge of data structures, then you’ll be able to crack any type of tech job interviews as well as you’ll also be able to solve competitive coding problems in an easy and smart way.
So, Are you excited to your Data Structures learning journey?
I know you are.
Here are the list of contents, which you’ll learn in this article:
2. Basic Terminology related to Data Structures
3. Classification (i.e., Types) of Data Structures
4. Operations on Data Structures
5. Why do we need Data Structures?
6. Advantages of Data Structures
7. Which Data Structure? ( How to know which data structure to use for a particular ADT ? )
8. Prerequisites for learning Data Structures
9. Conclusion
So, without further ado, let’s get started!
Before diving deep into the actual stuff (i.e., What actually Data Structures are…? ),
Let’s have a quick recap on some key (yet) most important terms, so that you’ll understand all the upcoming technical jargon easily and feel confidence as you move forward.
And,
The terms which I’m talking about are: Data, Information and Data Organization.
If you have a good understanding of these terms, then feel free to skip this portion and directly jump into the main concern (i.e., What is Data Structure?)
In simple words:
Data are values or sets of values (such as collection of alphabets, numbers and special symbols) in raw and an unorganized form.
It can be understood as the raw and isolated facts (i.e., words or description) and figures (i.e., numbers) about an entity (real world objects) that refers to, or represent conditions, ideas, persons and objects.
The word “raw” indicates that data have not been processed yet.
Data does not give any concrete knowledge/information about an entity.
It need to be processed, without processing – It seems random and useless to humans.
Data is measured, collected (recorded), reported and analyzed through observations and experiments, whereupon it can be visualized using images, graphs, tables or other analysis tools.
Examples: Text, audio, video, images, maps, graphs etc.
Information:
Meaningful, processed and usable data are called information.
In other words – “Information” is sometimes used for data with given attributes (properties).
Information are generally derived from a given data and are well organized.
Examples:
Data: Height of a student.
Information: The average height of a class which is derived from the given data.
Want to learn more about Data and Information? Click here!
Data Organization:
Data organization refers to the process of categorizing and classifying (i.e., systematic arrangement) of collected figures (raw-data) in such a form that comparison of the group of similar data may become easy and further analysis may be possible.
Techniques for data organization include: Tabulation, Graphical presentation, Diagrammatic presentation etc.
Organization of data makes data more useful, easy to understand and more convenient for further statistical operation.
What is Data Structure?
As the name indicates, Data Structure is made up of two words i.e., Data and Structure.
We have already learnt about Data at the beginning of this article,
Now,
Let’s have a quick look on what does structure mean?
– It simply means that to arrange something in an organized way.
Data may be organized in many different ways.
But,
The effective and efficient way of data organization is termed as Data Structure.
But,
Hold on!
What I mean by effective and efficient?
Effective in terms of: Accessing, Retrieval, Modification, Processing and reusing of data in a desired (i.e., easy and fast) way.
And,
Efficient in terms of: Memory space that a data structure requires and time consumed to perform any operation on it.
Which means that: A program is more efficient if it consumes less memory space to store a given data and also if it takes less time to perform any operation on it.
So,
Basically,
A Data Structure is a collection of data items which provides a particular (specific) way of storing, managing and organizing data in a computer’s memory so that we can perform operations (calculations) on the stored data in an effective and efficient way.
Technically speaking:- The mathematical or logical model (representation) of a particular organization of data is called a data structure.
The choice of a particular data model depends on the two considerations:
- It must be rich enough in structure to reflect the actual relationship of the data in the real world.
- The structure should be simple enough that one can effectively process the data whenever necessary.
Basic Terminology:
Data Items: Data items refers to a single unit of values.
And, Each data item is called an element of a data structure.
Group Items: Data items that are divided into sub-items are called Group items.
Example: An Employee name may be divided into three subitems- first name, middle name, and last name.
Elementary Items: Data items that are not able to divide into sub-items are called Elementary items.
Example: Roll number of a student.
Entity: An entity is something that has certain attributes (properties) which may be assigned values. The values may be either numeric or non-numeric.
Example:
| Attributes | Values |
|---|---|
| Name | Steve Smith |
| Age | 30 |
| Gender | M |
Entities with similar attributes form an entity set.
Each attribute of an entity set has a range of values, the set of all possible values that could be assigned to the particular attribute.
Field: It is a single elementary unit of information representing an attribute of an entity.
Record: It is a collection of field values of a given entity.
File: It is the collection of records of the entities in a given entity set.
Each record in a file may contain many field items,
But,
The value in a certain field may uniquely determine the record in the file. Such a field K is called a primary key and the values k1, k2, k3,….. in such a field are called keys or key values.
Records may also be classified according to length.
A file can have fixed-length records or variable-length records:
- Fixed-length records: In this type of records, all the records contain the same data items with the same amount of space assigned to each data item.
- Variable-length records: In this type, file records may contain different lengths.
Example:
Student records have variable lengths, since different students take different numbers of courses. variable-length records have a minimum and a maximum length.
Classification of Data Structures:
Data structures are generally classified into the following:
- Primitive Data structures
- Non-primitive Data structures
Image credit: javaTpoint
1. Primitive Data structures: Primitive data structures are the fundamental data types which are supported by a programming language.
Or,
We can say, Primitive data structures (types) are the predefined or compiler defined data structures whose meaning and purpose has already been described for a compiler.
Examples: Integer, character, float, double, etc.
These data types consists of characters that cannot be further divided and hence, they also called simple data types.
2. Non-primitive Data structures: Non-primitive data structures are those data structures which are created with the help of primitive data structures.
These are basically user defined data structures and not defined by the programming language.
Examples: Arrays, linked lists, stacks, Queues, trees, graphs, etc.
Based on the structure and arrangement of data, non-primitive data structures is further classified into the following:
- 1. Linear Data Structure
- 2. Non-linear Data Structure
1. Linear Data Structure:
A data structure is said to be linear if its elements form a sequence or a linear list.
There are basically two ways of representing such linear structure in memory.
1. One way is to have the linear relationship between the elements represented by means of sequential memory location. These linear structures are called arrays.
2. The other way is to have the linear relationship between the elements represented by means of pointers or links. These linear structures are called linked lists.
The common examples of linear data structure are Arrays, Stacks, Queues and Linked lists.
2. Non-linear Data Structure:
A Data Structure is said to be non-linear if the data are not arranged in sequence or a linear format.
The insertion and deletion of data is not possible in linear fashion.
This structure is mainly used to represent data containing a hierarchical (which means that, elements/objects are arranged according to their ranks or level of importance) relationship between elements.
Examples: Trees and Graphs.
⚉ Linear Data Structures
1. Arrays:
The simplest type of data structure is a linear (i.e., one dimensional) array.
An array is a collection of finite number of similar data items.
And,
Each data item is called an element of the array.
Elements of the array are referenced respectively by an index set (values) consisting of n consecutive numbers and are stored in contiguous (located next to one another in a group) memory locations.
If A is chosen the name for the array, then the elements of A are denoted by subscript notation a0, a1, a2,……an
Or,
By the parenthesis notation: A(0), A(1), A(2). . . . . A(n)
Or,
By the bracket notation: A[0], A[1], A[2]. . . . . A[n]
Example: A linear array named STUDENT consisting of the names [which all are strings (i.e., sequence of characters)] of five students.
Here STUDENT[0] denotes Matt Henry, STUDENT[1] denotes Sheldon, and so on…
| STUDENT[index number] | STUDENT Name |
|---|---|
| STUDENT[0]: | Matt Henry |
| STUDENT[1]: | Sheldon |
| STUDENT[2]: | Tim |
| STUDENT[3]: | Rickey |
| STUDENT[4]: | Joseph |
Read more: Array in Data Structure: From Zero to Hero
2. Linked list:
Linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.
It is a collection of nodes. Every nodes are connected (linked) in such a way, which together represent a sequence.
Each nodes contains a data and the address of the next node.
Thus, every node in a linked list has two component fields: one to store the relevant information (i.e., the data); and one to store the address, called the link of the next node in the list.
The address (link) of the first node in the list is stored in a separate location, called the head or first.
The address field of the last node contains pointer to the NULL.
Or,
You can say that the link field of the last node points to NULL.
3. Stack:
A Stack is a linear data structure which is derived from arrays.
It is a linear list in which insertions (additions) and deletions of elements can take place only at one end, called the top.
If you insert a data series into a stack and then remove it, the order of the data is reversed.
Let’s say: Data input as {1, 2, 3, 4, 5} then, it is removed as {5, 4, 3, 2, 1}.
And, Due to this reversing property – stack are also called as the last-in first-out (LIFO) system.
This structure is similar in its operation to a pile of dishes, stack of books or a stack of coins.
Any situation in which you can only add or remove an object at the top is a stack.
Note: The New dishes, books or coins are inserted only at the top of the stack and dishes can be deleted only from the top of the stack.
Basic Operations on Stack:
Push(): Insert an element at the top of the stack.
Pop(): Returns the top element after removing it from the stack.
IsEmpty(): Returns True, if the stack is empty.
IsFull(): Returns True, if the stack is full.
Top(): Returns the top element without removing it from the stack.
4. Queue:
A queue is a linear data structure which is derived from arrays.
It is a linear list in which deletions of elements can take place only at one end of the list, the “from” (front) of the list, and insertions can take place only at the other end of the list, the “rear” (back) of the list.
It is also called as the first-in first-out (FIFO) system. Why? because, the data item that enters first in the queue is the item that leaves out first.
This structure operates in much the same way as a line of people waiting at a bus stop, the first person in line is the first person to board the bus.
Image: Queue
Basic Operations on Queue:
Enqueue(): Insert an element from the back of the queue.
Dequeue(): Remove an element from the front of the queue.
IsEmpty(): Returns True, if the queue is empty.
IsFull(): Returns True, if the queue is full.
Peek(): Returns the front (first) element without removing it from the queue.
⚉ Non-Linear Data Structures
1. Trees:
Data frequently contain a hierarchical relationship between various elements. The data structure which reflects this relationship is called a rooted tree graph or a tree.
A Tree consists of finite set of elements, called nodes, and a finite set of directed lines, called branches, that connect the nodes.
The number of branches connected with a node is the degree of the node.
When a branch is directed toward the node, it is an indegree branch.
When a branch is directed away from the node, it is an outdegree branch.
Therefore, indegree branches + outdegree branches = degree of the node.
The topmost node is known as root node of the tree.
And,
The bottommost node is known as leaf node of the tree.
Some of the basic properties of tree are explained by means of examples.
Example: Record Structure
Although a file may be maintained by means of one or more arrays a record, where one indicates both the group items and the elementary items, can best be described by means of a tree structure.
For example: An employee personal record may contain the following data items: Name, Address, Age, Salary.
However, Name may be a group item with the sub-items First, Middle and Last name.
Also Address may be a group item with the subitems Street address and Area address, where Area itself may be a group item having subitems City, States and ZIP code (postal code) number.
The hierarchical structure is pictured below:
Another way of picturing such a tree structure is in terms of levels, as shown below:
- 01. Employee
- 02. Name
- 03. First
- 03. Middle
- 03. Last
- 02. Address
- 03. Street
- 03. Area
- 04. City
- 04. State
- 04. ZIP
- 02. Age
- 02. Salary
- 02. Name
2. Graph:
Data sometimes contain a relationship between pairs of elements which is not necessarily hierarchical in nature.
And,
That’s why we have to classify data in a non-linear format,
So,
A Graph is a pictorial (visual) representation of non-linear data structure consisting of nodes and edges. Nodes are basically referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.
Example:
Suppose a train travels only between the station connected by the lines in Fig. below. The data structure which reflects this type of relationship is called a graph.
Operations on Data Structures:
The data appearing in data structures are processed by means of certain operations.
The following four operations play a major role in this text:
1. Traversing:
Accessing each element (record/node) exactly once so that certain items in the record may be processed. (This accessing and processing is sometimes called “visiting” the record.)
2. Searching:
The process of finding the location of a data item (element) within the data structure is called Searching.
Or,
In other words – It is the process of finding the location of the desired element with a given key value, or finding the locations of all such elements which satisfy one or more conditions.
3. Inserting:
Adding a new element to the structure.
4. Deleting:
Removing an element from the structure.
The following two operations, which are used in special situations:
1. Sorting:
The process of arranging the data structure (records) in some logical order ( e.g., alphabetically according to some NAME key, or in numerical order according to some NUMBER key, such as social security number or account number) is known as sorting.
2. Merging:
It is the process of combining two different lists (records) of size P and Q respectively, of similar type of elements (i.e., data items), into a single sorted list.
The size of the new list (after combining the two lists) becomes (P+Q).
Why do we need Data Structures?
I know, you might be wondering that – why do we need to learn about data structures?
And, What is the use of it in our real life?
So,
Let’s understand with a real-world example:
Suppose, you have to buy Dettol soap and you went to a grocery store and asked for 2 Dettol soap from the shopkeeper,
And,
Not only you but also 10-15 customers are asking at the same time for soap and all customers demanding different soaps.
Imagine that situation, When all the soaps (for bathing and for washing clothes) have been mistakenly scattered somewhere in the same place by a new servant.
So what do you think?
What problems will the shopkeeper face in giving you soap.
The problems that the shopkeeper as well as the customers (including you) will face may be as follows:
- The first problem will be – It will take too long for the shopkeeper to find the soap, because the shopkeeper has to remove each soap and see if it is Dettol or not.
- The second problem will be – You and the rest of the customers will get soap in a very long time because the shopkeeper must have taken too long to find soap.
- Due to not keeping soap properly, the place will be consumed more and there may be a shortage of space in the shop.
- If at the same time a lot of customers will rush and start asking for the soaps from the shopkeeper, then the shopkeeper may refuse to deliver the soaps to some customers, and he may also say that the crowd is too much now, so, please come a little later.
Now,
You can think of soaps as data, each grocery store as a computer, shopkeeper as a server and customers as users.
And,
Just like that,
If data are not organized properly in a computer’s memory, then their may arises some problems,
such as: Low processing speed, Slowing down the search process (because, it need to traverse all the data items every time), Less efficient for uses and Server may failed due to multiple requests.
So,
In order to solve above problems, data structures are used.
Advantages of Data Structures
1. Data Structures provides as a means for storage and management of large amount of data such as databases and web/internet indexing services.
– Web indexing or internet indexing is the process for indexing the content (articles or videos) of websites or the internet as a whole.
[Indexing means that a particular page is eligible to appear in Google’s search results.]
2. It allows data storage on secondary memory, such as: Hard-disk drive (HDD) and solid-state drive (SSD).
HDD and SSD has permanent storage, Their data are static (non-volatile) and is not erased even if computer is turned off,
So, you can access (use) the stored data anytime and anywhere. It means that, if you use data structure to your program then it simply encourage reusability in long run as well.
3. Proper choice of data structures makes program effective and efficient, which leads to designing efficient algorithms.
4. It allows the data use and processing on a software system.
5. It allows safe and secure storage of data on a computer. The data cannot be lost (specially if it is stored on secondary memory or some special devices such as magnetic discs, magnetic tapes and optical disks(CD-ROMs), etc.
6. Data Structures provides as the basis of abstract data type (ADT), which are well tested and proven so, you don’t have to worry about the implementation details, and that’s why you can easily use them directly without need to research and development on them.
7. If you have an advanced knowledge of data structures, then it is a clear indicator of your capabilities in solving complex problems in minimum time.
Which Data Structure?
How to know which data structure to use for a particular ADT ?
The short answer of this question would be – It depends.
It depends upon the current requirement of the user.
If, A user wants to save memory space then, he/she can use a particular data structure which can save space.
Or,
Maybe, A user wants to run a program faster then, he/she will use a data structure which will run faster and save more time.
So,
Basically, different implementations of ADT are compared for time and memory space efficiency.
The one best suited according to the current requirement of the user will be selected.
Example:
Prerequisites for learning Data Structures
The only prerequisite for learning data structures is, you should have a basic knowledge of at least one programming language. If it is “C” or “C++” then it will be better.
Along with learning a programming language, specially focus more on the following concepts:
VariablesOperatorsData TypesInput/outputFunctionsConditional statements (i.e., if-else statement)Loop concepts (for, while and do while)ArraysStringsPointersStructuresDynamic memory allocation concepts [malloc(), calloc(), free(), realloc(), etc.]
If you complete the above topics honestly, then it is sufficient for learning data structures.
And, now you are ready to begin your data structures learning journey.
Conclusion:
So, In this post we covered mostly all the fundamentals of Data Structures, along with that we also got to know the answers of some frequently asked questions.
I hope you found this complete guide on Data Structures interesting and helpful.
And now I’d like to hear from you:
Which Data Structure do you want to learn first? Or maybe you have a question about something.
Either way, let me know by leaving a comment below right now.
Good Effort-making!
Thanks a lot brother ?