Introduction Into Data Structures

Introduction

The most important thing for any programmer is learning data structure and algorithms
And, understand them clearly to know how to use them right.

In this post, we’ll discuss data structure, and you will know

• What’s the data structure

• The types of the data structure

• Linear data structures like (Arrays, Stack, … etc)

• Non-linear data structures like (Trees, Graphs)

What’s the data structure

A Data structure is a tool to store your data on the computer
with an organized way, to make sure your code gets the data
in an efficient manner.

Imagine we have a hamburger store, and we need the first person who arrives there,
to be the first person who leaves.

This is what is called FIFO, which means “ first-in-first-out “ in this case,
we need to store our data in a way that helps our scenario,
this is precisely what the data structure is.

The types of data structure

The data structure is divided into two types. The first one is a linear data structure,
and the second one is a non-linear data structure.

So let’s get more deeply into each type of them to understand the difference.
Let’s start with the linear data structure.

The Linear Data Structure

The linear data structure is the data structure Its data are connected sequentially,
and the user can traverse it in a single run, also it’s easy to implement and understand.

We will take 4 data structures following this type Arrays, Stacks, Queue, LinkedList

1. Array

The array is a linear data structure, that allows us to store our data in the memory
In a contiguous way, Also the array is an indexed data structure, that helps us to get our
data immediately with Its index.

Also, it is a static data structure and needs to initial it
with an initial length to use.

2. Stack

The stack is a data structure, that allows us to store our data with
the LIFO approach which means the last element that is added is
the first element that will be deleted.

You can think of the stack as an undo feature, every task you do
the computer put it into a stack, and then when you click CTRL + Z
the computer deletes the latest task you did, That's how the stack works.

3. Queue

It’s a linear data structure that allows us to store our data in First In First Out (FIFO) order.
We can add data from one side and remove it from the other.

Some Examples

The queue is mostly used to handle some operations that need to run sequentially,
With "FIFO" order, like handling CPU operations and Memory Management
Also, it’s used for servers to handle the traffic.

Queue Implementation

We can implement a queue using an array or a LinkedList but in fact
The best way to implement it using a LinkedList because, If we implement it with an array, every delete operation will need to replace other data to the index 0 of the array which takes O(n) operations.

Queue Operations

Add -> O(1)
Peek -> O(1)
Remove -> O(n)
Or with a LinkedList -> O(1)

4. LinkedList

LinkedList is a linear data structure that consists of a list of nodes each node has a value
And it is connected to the next node.

LinkedList Applications

We can use LinkedList to implement stacks and queues and also to implement another data structure called Graph which is a non-linear data structure. Also, we can use it to calculate big arithmetic operations and more & more.

LinkedList implementation

Implementing a LinkedList is actually easy, we will need a reference for the head of the LinkedList and a tail too, and every one of those will be implemented as a node to save the value and also to connect with the next node.

Linkedlist Operations

Search- O(n)
addFirst- O(1)
addLast- O(1)
removeFirst- O(1)
removeLast- O(n)

The Non-Linear Data Structure

The data structure that its data are connected hierarchically

1. Trees

A Tree is a non-linear data structure consisting of a collection of nodes
connected with each other hierarchy, each node of the tree has a value and other children.
Also, each tree has a height, which is the count of the tree's levels, and the tree's latest nodes that are not connected with other nodes we called a Leaf.

Trees Applications

We see a lot of applications that use trees in their implementation every day,
because it’s a hierarchy data structure, it’s used to implement things like file systems to track your folders and subfolders, Also it’s used to store XML/HTML data and we can use it to implement a heap which helps to create super fast prefix lookups like google search suggestions and a lot more applications.

Trees implementation

We can implement a tree with a reference to the root which will be a node object
That object should have a value and a list of children to connect with other nodes.

Tree Operations

Lookup -> O(n) or O(log n)
if the tree is balanced.
Insert -> O(n) or O(log n)
if the tree is balanced.
Delete -> O(n) or O(log n)
if the tree is balanced.
Traverse -> O(n)

2. Graphs

Graph it’s a non-linear data structure consisting of nodes and edges, every edge can connect two nodes together and this connection can be on one side or two sides, you can think of this as social media where you can follow someone and he can also follow you.

Graph Applications

Graphs are used in our daily life in many applications like google maps, Google uses graphs to make a transportation system to calculate the shortest path between two roads.

Facebook also uses Graphs to express the connections between people.

And it's used in the World Wide Web (www.)

Graph implementation

To implement a graph we have two representations, the first one is Adjacency Matrix
and the second one is Adjacency List, we can use one of those representations to implement a graph, the choice will be dependent on the operations that you will perform
on the graph, we will take each representation and discuss how to implement it.

Adjacency Matrix

To implement an adjacency matrix we will need a 2d array AdjMatrix[v][e]
v represents the target node and e represents the connection between this node and other nodes, this representation is very efficient when it comes to removing a node or searching these operations runs in O(1) time complexity. Still, the problem with this representation is that it takes O(V^2) space, and O(V^2) to add a new node.

Adjacency List

To implement a graph with an adjacency list, we will need a list that contains
the nodes and each node should have an index then we will create another list that has the length of our nodes and each slot of this array will be a LinkedList to refer this node with the connected siblings.

Graph Operations

Add new node -> O(1) or O(V^2) if it's an adjacency matrix
Add an edge -> O(1)
Remove a node -> O(V + E) or O(V^2) if it's an adjacency matrix
Remove an edge -> O(E) or O(1) if it's an adjacency matrix
Query -> O(V) or O(1) if it's an adjacency matrix