In this article, I’ll analyze the qualities and weaknesses of the most common types of data structures.
In a computer science, we recognize a couple of very specific methods of organizing data for them to be used efficiently. “Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, efficient data structures are key to designing efficient algorithms.” (Data structure, 2016). Let’s shine a little light onto the data structure types. Following are the three most common data structure types:
- Arrays and Aggregates
- Lists, Stacks and Queues
Arrays and Aggregates
An array is a block of data which holds the set number of entries, which are typical of the same type.
The easiest way of explaining what an array is to imagine a row of strings, in which each entry is a string that is easily identifiable by its position (index reference) in an array. This is what we would call to be the one-dimensional array of strings. Let me illustrate this with an example:
As you can see in Diagram 1 (above), if we needed to identify a particular string, for instance, a word “ARRAY”, we could only say: String, which would be equivalent to saying, that the string is located in the one-dimensional array of strings at the position of index number 4. A one-dimensional array is the simplest form of using arrays, but it’s also very common to use more complex multi-dimensional arrays, as shown in Diagram 2.
Isf we wanted to locate a word “ARRAY” in Diagram 2 (multi-dimensional array of strings), we could only write it down as String, which means that the string is located inside the two-dimensional matrix at the location of row #2 and column #3.
There is another type that is different from an array, and that is a data structure type called an aggregate. This is basically a set of items that can consist of different data types and sizes. “The elements within the block are usually called fields. An example of an aggregate type would be the block of data relating to a single employee, the fields of which might be the employee’s name (an array of type character), age (of type integer), and skill rating (of type float). Fields in an aggregate type are usually accessed by field name, rather than by a numerical index number.” (Brooksher, G.J. and Brylow, D., 2014).
- Fast storage of elements
- Fast regular and rapid random access to elements
- Inserting or deleting requires all subsequent elements to be shifted
- Easily corruptible
- Requires more memory
Lists, Stacks, and Queues
It’s not hard to envision a list, just imagine any collection of data, such as list of guests at your party, or a list of food items you’re planning to buy in your local grocery store. That said, we can see that a list is an assembly of entries that are organized consecutively one after another. In computer science, the start of a list is called the Head, whereas the end of the list is usually referenced as the Tail. A list allows for a variety of function, such as adding new entries or entry removal from a list. But also more complex tasks as going through a list one item at a time or altering the arrangement.
Sometimes we may need to limit the way in which the list entries are retrieved, and this is where we use very distinct types of records, these are recognized under the names: Stacks and Queues.
A stack is a list in which entries are inserted and removed only at the head. An example is a pile of books where physical restrictions dictate that all additions and deletions occur at the top. A queue, on the other hand, is a list in which the entries are removed only at the head and new entries are inserted only at the tail. An example is a line, or queue, of people waiting to buy tickets at a theater.
- Provides control over how memory is allocated and deallocated
- No need to remember cleanup of objects
- Not easily corruptible
- Stack memory is limited.
- Large stack increases likelihood of stack overflow
- No random access
A tree is a set of entries organized hierarchically. The best way to illustrate this is to imagine a hierarchy of an enterprise, where “the president is represented at the top, with lines branching down to the vice presidents, who are
followed by regional managers, and so on.” (Brooksher, G.J. and Brylow, D., 2014). Then we can have different branches, etc.
I’ve created a diagram that should outline the most common tree structure and the terminology that is typically used in tree data structures:
As we can see the top node is called the root, and this node signifies the root of the tree. The nodes that do not have any child nodes are typically named leaf or terminal nodes, as they always represent the end of the particular branch). Each level of the path or the depth from the root is called the depth of the tree and height of the tree is the total depth of the tree data structure. We also recognize children and parent relationship between nodes and nodes with the same parent are called siblings. A tree where all of the parent nodes has at most two children is typically named a binary tree.
We also recognize a left and ride side of the tree, that we call left and right tree. As we can see from the diagram 3, the reason why we called it a tree structure is pretty obvious, by adding more nodes to a structure typically resolved into a form that very closely resembles a tree structure.
- Fast Searching
- Insert and Delete is faster than in Arrays
- High overhead
- Waste of idle nodes
- Programmed limit on number of children
Brooksher, G.J. and Brylow, D. (2014) Computer science: AN OVERVIEW. 12th edn. United States: Prentice Hall. (Accessed: 2 October 2016).
Data structure (2016) in Wikipedia. Available at: https://en.wikipedia.org/wiki/Data_structure (Accessed: 3 October 2016).
Singh, Y. (2016) Pros and cons of different data structures. Available at: http://www.mylearning.in/2015/06/pros-and-cons-of-different-data.html (Accessed: 3 October 2016).
Height, depth and level of a tree (2014) Available at: http://typeocaml.com/2014/11/26/height-depth-and-level-of-a-tree/ (Accessed: 3 October 2016).
What is the difference between tree depth and height? (2016) Available at: http://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height (Accessed: 3 October 2016).
Posted (2054) Array vs linked list. Intro, pros & cons, usage, etc. Available at: http://geekexplains.blogspot.ca/2008/05/array-vs-linked-list-advantages-and.html (Accessed: 3 October 2016).
Array data structure (2016) in Wikipedia. Available at: https://en.wikipedia.org/wiki/Array_data_structure (Accessed: 3 October 2016).