Basic data structures every software engineer must know

A data structure is a specialized way of organizing data that allows efficiently process it with associated algorithms. Since data is the most crucial entity in computer science, so the true worth of data structures is clear. It is one of the important topics when it comes to Software Engineering interview questions.

In this article, we briefly take a look at common data structures:

• Array
• Linked list
• Stack
• Queue
• Tree
• Heap
• Graph

Arrays

An array is a data structure that stores a sequence of values that are all of the same type. We are using the numbering to refer to the individual value in an array. For instance, if an array has N values, we think of them as being numbered from 0 to N-1. Individual objects are selected by an index. In Java/C#/Typescript/etc we are using the notation array[i] to refer to the ith value for any value of i from 0 to N-1.

 

Array operations

• Insert: may require to increase the array size
• Delete: may require to reduce the array size
• Update: update the value of an existing element at a given index
• Search: search for an element in the array. The search can be done by its value or index
• Traverse: go through array elements

Linked list

A linked list is a sequential data structure that consists of a sequence of nodes in linear order which are linked to each other. Node is a data entity that contains data of any type and a reference to another node.

 

 

Terms related to linked lists:

• Head points to the first element of the linked list
• Tail points to the last element of the linked list
• Elements in a linked list are known as nodes
• Node is a data entity that contains data of any type and a pointer to another node

Linked list operations

• Insert: insert a node to the linked list
• Delete: delete a node from a given linked list
• Update: update the value of an node

Stack

Stack is a data structure based on last in first out (LIFO) policy. A good real-life example is a pile of plates. Just like a pile of plates, a stack allows for operating data that resides at the "end" of the stack. In other words, you can add an item to the top and remove an item from the top.

 

Stack operations

• Push: adds an item to the top of the collection
• Pop - removes an item from the top of the collection

Queue

Queue is a data structure based on first in first out (FIFO) policy. In other words, the order of processing tasks depends on the order in which those tasks are added. A good real-life example is a queue in a store or a queue of people waiting in an airport.

 

 

Queue operations

• Enqueue - adds an item to the end of the collection
• Dequeue - removes an item from the beginning of the collection

Trees

A tree is a nonlinear data structure. Trees store hierarchies of data

Here are some example of trees:

• Binary tree
• Binary search tree (BST)
• B tree
• Red-black tree
• AVL tree
• Splay tree
• Treap

 

 

The terminology used in trees:

• Root: the node at the top of the binary tree
• Child: a node below a given node
• Parent: the converse definition of a child (the opposite of child)
• Leaf: a node without child nodes
• Edge: a connection between two nodes
• Subtree: a tree representing the descendants of a node

Heap

A heap is a special tree-based data structure in which is a complete tree

 

 

Heaps can be of two types:

• Max Heap: the value of the parent is greater than or equal to those of its children. This is called the max-heap property. The root contains the maximum value of the heap

• Min Heap: the value of the parent is less than or equal to those of its children. This is called the min-heap property. The root contains the minimum value of the heap

Graphs

A graph is a non-linear data structure consisting of nodes and edges

 

 

The terminology used in graphs:

• Vertex is a synonym for a node of a graph
• Edge is a link which connects a vertex to another vertex in the graph
• Adjacent vertices: two nodes are said to be adjacent if they are connected to each other by the same edge

Types of graphs

Undirected Graph: In an undirected graph, nodes are connected by edges that are all bidirectional

 

 

Directed Graph: In a directed graph, nodes are connected by directed edges. Edges go only in one direction