Let’s Talk About Data Structures
Learning about data structures is not of primary concern during a full stack web development bootcamp as you can build powerful applications without knowing about the aforementioned. However as I progress in my job search, I am starting to see the value of data structures in the “real world” setting.
Naturally, the first step of this journey is to ask what exactly are data structures? They can be considered a way of organizing and storing data so that we can efficiently perform operations for, for example, accessing, inserting, deleting, finding, and sorting data. It’s important to note that not all data structures can perform these operations efficiently — leading to the development of varying types and associated purposes. Questions to consider before implementing a data structure include:
- How much data do we need to store?
- How often do we need to access that data?
- What is the purpose of this data?
- Do we need to access, insert, delete, or sort the data?
Understanding the data structures used in our day to day programming will be a great starting point.
1. One Dimensional Arrays
By this point, we should be very familiar with one dimensional arrays; however, to be safe, an array can hold a fixed number of containers to store data and operations can be performed on that data based upon a user’s needs.
In the image above, the array is defined with the name arr. The numbers in the white boxes surrounded by brackets indicate the index (or position in the array) of each element. The index always started at 0 and ends at a number one less than the total amount of elements. The numbers in the orange boxes indicate the memory address each container of the array is assigned to.
2. Multidimensional Arrays
For one dimensional arrays, an array is defined with a row of containers as highlighted above. For multidimensional arrays, an array is defined with rows as well as columns. In order to access an index of a multidimensional array, we will need two numbers (indicating the row AND column).
In the diagram above, the array (with the presumed name of arrayName) is defined as arrayName[3][4] because it has 3 rows and 4 columns with a total of 12 indexes. To ascertain the number of indexes, simply multiply the number of rows by columns. Due to the layout, multidimensional arrays can be referred to as tables or matrices.
//
Note: Some programming languages, including Ruby and JavaScript, define arrays dynamically; meaning that the size of an array will be adjusted automatically based upon the user’s needs. We do not need to predefine space for the array as it will be created with precision at execution. This is done in an attempt to save memory / avoid taking up more memory than we actually need. In languages like Java and Python, we have to be more specific in terms of how we tell the program to dynamically define arrays — using the ArrayList class in Java and the list data type in Python.
//
3. Singly Linked Lists
A linked list is a linear collection of nodes that are connected by links. The nodes store data and the location of the next node. The first node is referred to as the head node and the last as the tail. The pointer of the head node points to the next node and so on until the last node; this tail node points to null. Adding and removing nodes is very easy so long that you keep track of the previous and succeeding nodes of the target node and adjust the links accordingly.
4. Doubly Linked List
A doubly linked is differentiated from a singly linked list with the fact that the pointers can point forward AND back. The back (or previous) pointer of the head node points to null and the next pointer of the tail points to null.
5. Circular Linked List
As the name suggested, a circular linked list is a linked list where all the nodes are connected and, as a result, form a circle. There is no head or tail node / any node can be used as a starting point.
//
Note: Linked lists are similar to arrays but there are no indices. As a result, we cannot randomly access data; we must traverse the list in order to find any one element instead. Linked lists can be more useful than arrays when dealing with a large dataset where we constantly need to add or remove data from the beginning or end (e.g., a stack or queue).
//
6. Stack
Stacks can be implemented using an array or linked list . They are a Last In First Out (or LIFO) data structure which means that the last item to come is the first to go out. Consider a stack of books, the last book is placed on top of the stack. If you wanted to remove a book, you would remove the first one from the top (or the last book placed). There are three operations that can be performed on stacks: Push (to input data/place it on top), Pop (to remove data from the top), and Peek (to look at the data at the top without removing it).
7. Queue
Similar to stacks, the word queue is also derived from daily life. The most common example being a queue of people waiting in the checkout line at the grocery store. Queues are First in First Out (or FIFO) structures and can be implemented using arrays or linked lists. There are three operations that can be performed on queues: Enqueue (to input data into a stack and place it at the bottom), Dequeue (to remove data from the top), and Peek (to look at data at the top without removing it).
8. Tree
Tree data structures function similarly to a family tree in terms of inheritance. There is a root node where all nodes are connected to. The root node is divided into a left and right node and so on. Nodes positioned under and linked to higher nodes are considered children. Nodes at the same level (that share a parent) are considered siblings.
9. Binary Search Trees
Binary search trees are a special kind of tree where the left node is smaller than the parent and the right node is larger. In order to add or delete a node, we must compare the value to the root node and then traverse to a specific point to do said insertion/deletion.
