An overview of data structures every developer should know
As a software engineer, it’s important to at least be familiar with the different types of data structures. There is much more than just arrays and lists in the world and knowing the other data structures can you give the much-needed flexibility you need in your projects.
Arrays should be the first data structure any developer learns, regardless of what language they use. The question is, what is an array? An array is a collection of items stored in one section of the system's memory known as Contiguous Memory Allocation. An array is also a linear data structure as it organizes its element in a sequence, meaning one after another. Each element has an index which is that element’s position in the array. In simpler terms, you can think of an array as a building with each floor representing a different element in the array and its associated index. The only difference between a building and an array is an array doesn't start from 1, it starts from 0. Let’s take for example you had an array of 10 elements, the array would not be between 1 and 10 but instead would have indices(plural of index) between 0 and 9.
Advantages of Array’s
But why would you use arrays? One reason to use arrays is if you have multiple similar pieces of data you would like to have grouped together. For example, if you had a group of integers, an array would be a great way to group these elements together, allowing you to write cleaner code. Arrays can also be useful when you want to randomly get an element out of a group of data.
Disadvantages of Array’s
Like everything in life, Array’s are not perfect and have their downsides. One of these being that in most computer languages arrays are confined to the length they were initialized with. This means if you create an array with 5 elements, it is not possible to add new elements to the array after it has been initialized.
A Linked List is much like an array in that it is a linear data structure, but in this case, each element is a separate object. When using linked lists we refer to each one of these elements as nodes. These nodes consist of two items , the data the node holds and the reference to the next node known as a pointer. This means a linked list is not an example of Contiguous Memory Allocation but instead, Noncontiguous Memory Allocation as each element in a linked list exists in different parts of a systems memory. Using our building example from earlier, the data part of a node would be the floor and everything inside of it, the pointer would be a button on the elevator that takes you to the next floor.
Advantages of Linked Lists
There are a few advantages to linked lists, one being that unlike arrays, linked lists are dynamic in size meaning new elements can be added after initialization. The insertion and deletion of elements in linked lists are also relatively easier as each element has a clearly specified pointer.
Disadvantages of Linked Lists
One disadvantage of linked lists is random access is harder to achieve as elements are accessed sequentially, meaning one after another. This means extra work will be needed by a developer to access random elements in that they will have to create a function to do so. While this next part may or may not be considered a disadvantage, it is definitely something to keep in mind. When using a linked list extra memory space is needed because a pointer is required for each node. This memory allocation may only be a problem in much larger projects which is why I am hesitant to call it a disadvantage.
A stack is a data structure that serves as a collection of elements and is also a linear data structure. A Stack is an abstract data type as it can be created with both arrays and linked lists. If a Stack had one motto it would be“Last in,first-out”.The reason for this being that a stack consists of two principal operations push, which adds an item to the front of the collection, and pop, which takes an item from the front of the collection. You can think of a stack as a spring with only one opening. When you insert a new element into the spring you push it from the top making it the first item. When you want to remove an element from the spring you pop it from the top.
Because a stack can be created with an array or linked lists it inherits both the same advantages and disadvantages of the data structure that is using. It's easier to think of a stack less as its own data structure, but more like a modification or way to use an existing data structure such as an array and linked lists.
A queue is another example of a linear abstract data structure that serves as a collection of elements. A queue is similar to a stack that can be created using both Arrays and Linked Lists. If a Queue had one motto it would be “First in, First out”.Similar to a Stack, Queue has two principal operations enqueue, which takes an element and adds it to the rear of a queue, and dequeue, which takes the first element out of a queue. The best way to think of a queue is to think of waiting in a line.No matter what the line is for, the first person in a line is the first person to leave the line.
Just like a stack, a Queue inherits the advantages and disadvantages of the data structure it is using.