Knowledge of data structures is fundamental for any software engineer. Why data structures are so important? The goal of data structures is to organize and store information in an efficient manner. But there is no one perfect data structure that can/should be used everywhere. You have to pick the right tool for the job. While you can use a hammer to drive both nails and screws into a piece of wood, using a screw driver for latter would most likely be a better choice. In this post I wanted to focus on most basic data structures and their properties. In later articles I will go over implementation of those basic data structures.
Array is the most basic data structure in programming languages. Other data structures very often are built on top of arrays. Fast random access time is due to requirement that array can only contain one type of objects. This allows for very easy arithmetic on memory addresses to locate object associated with a key.
Applications of array Arrays are used to implement other data structures.
Dynamic array is a data structure that take basic array and internally allows for dynamic resizing. This can be accomplished in many ways but one of the common is to double the size of original array every time it’s filled. Resizing array is quite expensive O(n) but while array is growing need of doubling array reduces logarithmically. Because of that we say that dynamic arrays have amortized constant write time.
Dynamic array advantages
Dynamic array disadvantages
Applications of dynamic array Used in application where fixed array can’t be applied because of their fixed size restrictions.
Linked list (also called singly linked list) is a data structure where each element has as reference to next element. The most important quality is that it grows dynamically and is very predictable with insert time. Major difference between linked list and array is that access time is O(n) at worst whereas with array it is constant.
Linked list advantages
Linked list disadvantages
Applications of linked list Can be used over dynamic arrays where reliable constant insert time is required. It is faster for inserts in the beginning.
Doubly linked list is just like linked list where each node has additional reference to previous element. The biggest advantage over singly linked list is that doubly linked list can be navigate both directions.
Doubly linked list advantages
Doubly linkes list disadvantages
Applications of doubly linked list Used where data structure needs to be traversed both ways. Allows for faster deletes than singly link lists.
Circular linked list has a similar implementation to singly linked list or doubly linked list. The only difference is in that its tail node’s next pointer points to the head node (full circle) or to some other node forming sort of a “key” structure. None of the nodes in circular linked list point to null as opposed to linked list.
Circular linked list advantages
Circular linked list disadvantages
Applications of circular linked list