Book Of Data Structure In C Aikman Series Pdf
Marisol Stgermain
Primitive data structures come by default with the programming language and you can implement them out of the box (like arrays and objects). Non-primitive data structures don't come by default and you have to code them up if you want to use them.
Different data structures exist because some of them are better suited for certain kind of operations. You will probably be able to tackle most programming tasks with built-in data structures, but for some very specific tasks a non-primitive data structure may come in handy.
In some programming languages, the user can only store values of the same type in one array and the length of the array has to be defined at the moment of its creation and can't be modified afterwards.
In JavaScript, arrays come with many built-in properties and methods we can use with different purposes, such as adding or deleting items from the array, sorting it, filtering its values, know its, length and so on. You can find a full list of array methods here. ?
As I mentioned, in arrays, each element has an index defined by its position in the array. When we add a new item at the end of the array, it just takes the index number that follows the previous last item in the array.
But when we add/delete a new item at the beginning or the middle of the array, the indexes of all the elements that come after the element added/deleted have to be changed. This of course has a computational cost, and is one of the weaknesses of this data structure.
Arrays are useful when we have to store individual values and add/delete values from the end of the data structure. But when we need to add/delete from any part of it, there are other data structures that perform more efficiently (we'll talk about them later on).
Objects are a good way to group together data that have something in common or are somehow related. Also, thanks to the fact that property names are unique, objects come in handy when we have to separate data based on a unique condition.
Stacks are a data structure that store information in the form of a list. They allow only adding and removing elements under a LIFO pattern (last in, first out). In stacks, elements can't be added or removed out of order, they always have to follow the LIFO pattern.
To understand how this works, imagine a stack of papers on top of your desk. You can only add more papers to the stack by placing them on top of all the others. And you can remove a paper from the stack only by taking the one that is on top of all the others. Last in, first out. LIFO. ?
There's more than one way to implement a stack, but probably the simplest is using an array with its push and pop methods. If we only use pop and push for adding and deleting elements, we'll always follow the LIFO pattern and so operate over it like a stack.
Queues work in a very similar way to stacks, but elements follow a different pattern for add and removal. Queues allow only a FIFO pattern (first in, first out). In queues, elements can't be added or removed out of order, they always have to follow the FIFO pattern.
To understand this, picture people making a queue to buy food. The logic here is that if you get the the queue first, you'll be the first to be served. If you get there first, you'll be the first out. FIFO.?
Linked lists are a type of data structure that store values in the form of a list. Within the list, each value is considered a node, and each node is connected with the following value in the list (or null in case the element is the last in the list) through a pointer.
The first element of the list is considered the head, and the last element is considered the tail. Like with arrays, the length property is defined as the number of elements the list contains.
Like any data structure, different methods are implemented in order to operate over the data. The most common ones include: push, pop, unshift, shift, get, set, insert, remove, and reverse.
As mentioned, the difference between doubly and singly linked lists is that doubly linked lists have their nodes connected through pointers with both the previous and the next value. On the other hand, singly linked lists only connect their nodes with the next value.
This double pointer approach allows doubly linked lists to perform better with certain methods compared to singly linked lists, but at a cost of consuming more memory (with doubly linked lists we need to store two pointers instead of one).
Trees are formed by a root node (the first node on the tree), and all the nodes that come off that root are called children. The nodes at the bottom of the tree, which have no "descendants", are called leaf nodes. And the height of the tree is determined by the number of parent/child connections it has.
Unlike linked lists or arrays, trees are non linear, in the sense that when iterating the tree, the program flow can follow different directions within the data structure and hence arrive at different values.
An important requirement for tree formation is that the only valid connection between nodes is from parent to child . Connection between siblings or from child to parent are not allowed in trees (these types of connections form graphs, a different type of data structure). Another important requirement is that trees must have only one root.
There're many different types of trees. In each type of tree, values may be organized following different patterns that make this data structure more suitable to use when facing different kinds of problems. The most commonly used types of trees are binary trees and heaps.
In BST, values are ordered so that each node that descends to the left side of its parent must have a value less than its parent, and each node that descends to the right side of its parent must have a value bigger than its parent.
This order in its values make this data structure great for searching, since on every level of the tree we can identify if the value being looked for is greater or less than the parent node, and from that comparison progressively discard roughly half of the data until we reach our value.
The big O complexity of these operations is logarithmic (log(n)). But it's important to recognize that for this complexity to be achieved, the tree must have a balanced structure so that in each search step, approximately half of the data can be "discarded". If more values are stored to one side or another of three, the efficiency of the data structure is affected.
Heaps are another type of tree that have some particular rules. There are two main types of heaps, MaxHeaps and MinHeaps. In MaxHeaps, parent nodes are always greater than its children, and in MinHeaps, parent nodes are always smaller than its children.
Heaps, and in particular binary heaps, are frequently used to implement priority queues, which at the same time are frequently used in well-known algorithms such as Dijkstra's path-finding algorithm.
Graphs are a data structure formed by a group of nodes and certain connections between those nodes. Unlike trees, graphs don't have root and leaf nodes, nor a "head" or a "tail". Different nodes are connected to each other and there's no implicit parent-child connection between them.
If we take the following example image, you can see that there's no direction in the connection between node 2 and node 3. The connection goes both ways, meaning you can traverse the data structure from node 2 to node 3, and from node 3 to node 2. Undirected means the connections between nodes can be used both ways.
We say a graph is weighted if the connections between nodes have an assigned weight. In this case, weight just means a value that is assigned to a specific connection. It's information about the connection itself, not about the nodes.
To understand the use of weighted graphs, imagine if you wanted to represent a map with many different locations, and give the user information about how long it might take them to go from one place to another.
A weighted graph would be perfect for this, as you could use each node to save information about the location, the connections could represent the available roads between each place, and the weights would represent the physical distance from one place to another.
And as you may have guessed once again, unweighted graphs are the ones where connections between nodes have no assigned weights. So there's no particular information about the connections between nodes, only about the nodes themselves.
You can see that the matrix is like table, where columns and rows represent the nodes in our graph, and the value of the cells represent the connections between nodes. If the cell is 1, there's a connection between the row and the column, and if it's 0, there's not.
So what's the difference between adjacency matrices and lists? Well, lists tend to be more efficient when it comes to adding or removing nodes, while matrices are more efficient when querying for specific connections between nodes.
Now imagine we want to verify if there's an existing connection between node B and E. Checking that in a matrix is dead easy, as we know exactly the position in the matrix that represents that connection.
But in a list, we don't have that information we would need to iterate all over the array that represents B connections and see what's in there. So you can see there are pros and cons for each approach.
That's it, everyone. In this article we've introduced the main data structures used in computer science and software development. These structures are the base of most of the programs we use in every day life, so it's really good knowledge to have.
b1e95dc632