Data Structure Using C
Hello Everyone…..
Are you started coding..?? When you are starting your coding journey, the question arises that What are the fundamental concepts I need to know? Well, Data Structures is one of them….!!!
It means that data structures are ways to store data. Simple, right? But what does that actually mean?
Okay, so one of the first things you learn when starting to code is how to store data, usually a simple value like a string or number, in a variable. As their name states, the value that a variable contains can be changed, or varied: see what I did there? Constants are like variables because they store a value, but can’t be changed.
So, if variables and constants store data, why are not they data structures?
It is because of data structures can hold more than a single value, organize that data, and allows you, to perform operations on them. This allows to keep the data together as you pass it around your program and do different things with it.
For Free Demo classes Call: 8237077325
Registration Link: Click Here!
Before Data Structure lets understand about algorithms:
Algorithms:
It is nothing but step by step procedure to obtain solution of problem. Algorithm contains well-defined finite no of steps or rules that are executed sequentially to obtain particular solution. Algorithm solves only a single problem at am time. However, the same problem can be solved using multiple algorithms.
Characteristics of Algorithm:
– Each instruction in the algorithm should be defined clearly.
– It should be correct i.e. it should be able to perform the desired task of generating correct output from given input.
– It must contain finite no of steps.
– There should be no ambiguity.
– It should be able to terminate on its own, it should not go in infinite loop.
What is Data Structure?
– A data structure is a way of organizing data in a computer so that it can be used effectively.
– Data structure is nothing but storing and organizing information in a computer so that it can be retrieved and used most productively.
– Different kinds of data structures are used for different kinds of applications, and some are highly specialized to specific tasks.
Data structures are important for the following reasons:
- Data structures are used in almost every programming language or software system.
- Some data structures are essential factor of many efficient algorithms, and make possible the management of huge amounts of data.
- Some programming languages point up on data structures, rather than algorithms, as the key organizing factor in software design.
For Free Demo classes Call: 8237077325
Registration Link: Click Here!
How Do I Pick the Right Data Structure?
So, data structures help you store multiple values, right? What’s special about that? Generally, the tasks you will want to do on your data are:
- Add some
- Remove some
- Find some
- Sort it all
Depending on which of these tasks you’re going to want to do most, you will choose a data structure that makes that task easier, faster, and more efficient.
Array:
Arrays are like a weekly tablet organizer that a lot of elderly people have to organize their medication.
If you’re not familiar with them, the organizers have seven small containers, all lined up horizontally, one for each day of the week and marked with the day’s first letter. All of the individual containers are connected in a line.
This is how arrays are laid out in memory. When we create one, a block of continuous memory is set aside for it. The amount of memory that’s set aside is based on the type of values to be stored inside the array.
An array is collection of same type of elements. We can store more than one value under one variable using array.
Declaration:
data_type array-name[size];
e.g. int arr[5];
Above e.g. states that we can stores only integer data in array, if we want to store different types of data we have to create structures, which is used to hold different types of data.
In above example we can’t store decimal value in array if we want, we have to create float type of array. Size indicates total no of values that we are going to store in array. ‘arr’ is a array variable which stores the base address of first element of your array, it works as a internal pointer.
So, arr variable stores the address of first element.
For Free Demo classes Call: 8237077325
Registration Link: Click Here!
Accessing array element:
Instead of starting at an end of an array and traversing it to find the item you want, you access items by their index, i.e., what number place they hold in the array. This index is actually accessing a specific location in the block of memory allocated for the array.
Array elements are accessed by using their index position which is started from 0 to size-1, because the index are locations in the memory block, they are zero-based. The index number is essentially the number of the item you want from the beginning of the array. So, the first item in the array is accessed by index 0. It’s the first item plus 0 more. This also means that the last item is at the index of the total number of items, minus one (i.e., n – 1 where n is the total number of items).
Accessing a element from an array is very fast if you know the index. In fact, accessing a specific element from an array, with a known index, is constant. It stays the same regardless of the number of items in the array.
If you don’t know the index of the item you want, you have to traverse it like linked lists. The only difference is that you don’t have reference to the next item in an array like linked list, so you have to loop over all the possible index values. This is where security issues can come in with languages like C and C++, where it’s possible to go past the end of an array.
Advantages of Arrays:
Arrays can be accessed very quickly by using the index(es). Because indexes don’t change as you insert or remove data, the speed at which you access any specific item remains the same regardless of how long the array is.
For Free Demo classes Call: 8237077325
Registration Link: Click Here!
Disadvantages of Arrays:
On the down side, arrays can be slow and inefficient when you need to resize them. Because they are continuous blocks of memory, you have to create them with the size you expect to need. If you misjudge this and ask for too little memory, then when you reach the end, the array needs to be resized.
What does resizing an array mean, practically speaking? It means that a new, larger block of memory needs to be allocated for the new copy of the array. Then all the items from the original array must be copied to the new one. This is time consuming, and for a time during the resize, you will use much more memory than the array really needs.
On the other chance that you asked for too much memory at the beginning, if you won’t have to resize it, but you will be wasting that extra memory. Some languages will default to certain sizes that should fit most uses, but will still probably waste a large percentage of the space in the end.
The problem with having to copy data from one array to a new array also exists for adding and removing data. Because arrays are made from continuous blocks of memory and you access items using their index into that memory, if you want to add or remove some data from the middle, then the rest of the items have to be moved. This can be slow and inefficient, as you might expect.
When to Use an Array?
- want immediate access to elements and will know their index position.
- need to sort and search quickly
- won’t need to insert or remove data frequently
Linked Lists:
Linked lists are the simplest of the four data structures we’ll talk about. You can visualize a linked list as a chain. The links of the chain are the items in the linked list, called nodes. Each node is connected to the node in front and the node behind (except for the first and last nodes, obviously).
The simplest version of the linked list has only one connection between nodes: the connection to the next node. This is a singly-linked list.
Given that each node is only connected to the next node in the list, you can only walk through (or traverse) the list from the beginning to the end, never backwards.
In code, you will have a reference, in a variable, to the first node. This is the head of the list. You can use reference to walk through the list, by calling a method like nextNode() on each node.
More advanced versions of linked lists will also have a reference to the last node in the list, often called tail. In a singly-linked list, this reference only helps to add links to the end of the list so it isn’t usually used. The tail reference becomes much more useful in doubly-linked lists. I will give you one guess what’s different about doubly-linked lists. Right-O, doubly-linked lists are doubly-linked. Gosh, those clever, clever developers and their naming.
As you might have already guessed, doubly-linked lists have two connections between nodes. In which one connection is to the node before, and another connection is to the node after. This allows you to traverse the list in both directions.
Why would anyone use a singly-linked list then if doubly-linked lists exist and make life easier? Well, it’s a trade-off.
If each node has two links, one to the preceding node and one to the following node, you double the amount of node references used by a list. This may not seem like a big deal when talking about web-scale applications, but it is important when thinking about embedded and even mobile applications where there’s less memory to use.
So why would you choose a linked list?
And why wouldn’t you?
And, if you did choose one, why would you pick a singly-linked list over a doubly-linked one?
Well…!! let me explain.
Advantages of Linked Lists:
Linked lists are pretty simple. This means that they’re easy to create if you need to make your own. They also only take up enough memory to hold each item in the list and a reference to the next one, for a singly-linked list. For doubly-linked lists, like I mentioned above, there’s another reference to the previous link. There’s very little wasted space.
Linked lists are also easy to add and remove data from because you merely have to:
- find the spot in the list
- create a new node
- assign the new node’s next reference to the next node
- assign the current node’s next reference to your new node.
If you’re appending to the end and have a tail reference, it’s even easier because there’s no traversal.
Disadvantages of Linked Lists:
There is rare a data structure that only has upsides. Linked lists are no exception.
Because you access items in a linked list by starting at one end and working towards the other end, searching for a specific item can take a long time, relatively speaking. In the worst case, you start at one end and the item you’re looking for is on the other end. This means that the amount of time to find any specific item depends on how long the list is. Big-O notation is for: discussing the efficiency of these kinds of operations as the amount of data grows.
Searching on the poor efficiency of linked lists, sorting them is also slow. This follows by sorting, you have to take each item in the list and compare it the with rest of others, then insert it in the right place. Constantly working from one end towards to the other end, It means that we can traverse the list many times.
For Free Demo classes Call: 8237077325
Registration Link: Click Here!
When to Use a Linked List:
You can use a linked list when:
– memory usage is a concern
– Not necessary that searching and sorting does have to be fast
– the data is conceptually connected linearly
And That’s Little Bit About Data Structures…!!!
Yeah, I know it’s still there, but I hope that this post has helped you to take a much-needed step towards understanding data structures and overcoming that feeling of inefficiency.
You should now feel more confident in when to pick what data structure for many of your tasks, or at least knowing what to look for when making a decision.
I would provide remaining data structure details in next blog…!!!
For Free Demo classes Call: 8237077325
Registration Link:Click Here!
Call the Trainer and Book your free demo Class now!!!
