Basic Data Structures and Their Properties

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

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.

Array advantages

• fast constant access time, regardless of size,
• constant insert time,
• stores elements in contiguous blocks of memory

Array disadvantages

• fixed size, size of the array has to be predefined,
• store one type of object,
• expensive to insert new element in the middle

Applications of array Arrays are used to implement other data structures.

Dynamic Array

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 size (can grow and shrink)
• constant access time,
• amortized constant insert time

Dynamic array disadvantages

• because of its doubling size nature it may use more memory,
• stores one type of object

Applications of dynamic array Used in application where fixed array can’t be applied because of their fixed size restrictions.

Linked List

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

• can grow as long as resources are available,
• it does not waste memory space (like arrays) but the same size will take more memory because of the pointers
• constant insert time but slightly more expensive than array,
• can work with mixed objects

Linked list disadvantages

• at best O(1) and worst O(n) access time, same for deletions,
• navigable only one direction

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

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

• navigable both ways,
• easier to delete elements

Doubly linkes list disadvantages

• uses more space because of additional pointer to previous node,
• maintaining next and previous pointers when inserting or deleting nodes,
• insertion and deletion take a bit longer because of more pointer operations

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

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

• going from last node to first node requires one step; singly or doubly linked lists do not offer that,

Circular linked list disadvantages

• risk of introducing hard to debug infinite loops,

Applications of circular linked list

• Circular linked lists are used in application of circular nature e.g. board games.