Classification of data structure

Data Structure

• Linear data structure

: Data structure in which data elements are arranged sequentially or linearly, where each element is attached to its previous and next adjacent elements, is called a linear data structure.

- Static data structure

: Static data structure has a fixed memory size. It is easier to access the elements in a static data structure. ➡️ Array

- Dynamic data structure

: In dynamic data structure, the size is not fixed. It can be randomly updated during the runtime which may be considered efficient concerning the memory (space) complexity of the code. ➡️ Queue, Stack, Linked List

• Non-linear data structure

: Data structures where data elements are not placed sequentially or linearly are called non-linear data structures. In a non-linear data structure, we can’t traverse all the elements in a single run only. ➡️ Tree, Graph

Array

Basic Conception

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together.

This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

Real Life Examples

Books in library are one of the most popular examples used to explain insertion sort. A librarian picks up a book and insert it in correct place and then pick the next one to organize.

A student picked a book in the book shelf to read, a librarian would pushed the row to organize and fill up the empty spot of a book and the order is updated.

To Use

An array is faster but not memory efficient, better use when you already know how many elements you are going to store in it.

Queue

Basic Conception

Queue is a linear data structure that follows a particular order in which the operations are performed for storing data.

The order is First In First Out (FIFO).

The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

• enqueue() : Insertion.

• dequeue() : Deletion.

• front : Accesses the data from the front end(for dequeuing).

• rear: Accesses the data from the rear end(for enqueuing).

Real Life Examples

One can imagine a queue as a line of people waiting to receive something in sequential order which starts from the beginning of the line.

It is an ordered list in which insertions are done at one end which is known as the rear and deletions are done from the other end known as the front.

A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.

To Use

Queue and Stack are dynamic data structure which is memory efficient and flexible.

They can be used over arrays when sequential access is needed by removing data from the start(First In First Out — queue) or the end(First In Last Out —stack) of a data structure.

• Queue data structure is implemented in the hardware microinstructions inside a CPU.

• Queue structure is used in most operating systems.

Stack

Basic Conception

Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

LIFO implies that the element that is inserted last, comes out first and FILO implies that the element that is inserted first, comes out last.

• push() : Insertion.

• pop() : Deletion.

• top : Accessing point.

Real Life Examples

There are many real-life examples of a stack.

Consider an example of plates stacked over one another in the canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time.

So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order.

To Use

Use a stack when you want to get things out in the reverse order than you put them in.

Use a queue when you want to get things out in the order that you put them in.

• Some CPUs have their entire assembly language based on the concept of performing operations on registers that are stored in a stack.

• Stack structure is used in the C++ run-time system.

Linked List

Basic Conception

A linear data structure, in which elements are not stored at a contiguous location, rather they are linked using pointers.

Linked List forms a series of connected nodes, where each node stores the data and the address of the next node.

It is easier for insertion/deletion than Array, it doesn’t need to be shifted after the performing, just need address updating.

• single-linked list

: In a singly linked list, each node contains a reference to the next node in the sequence. Traversing a singly linked list is done in a forward direction.

• double linked list

: In a doubly linked list, each node contains references to both the next and previous nodes. This allows for traversal in both forward and backward directions, but it requires additional memory for the backward reference.

• circular linked list

: In a circular linked list, the last node points back to the head node, creating a circular structure. It can be either singly or doubly linked.

Real Life Examples

The simplest and most straightforward is a train.

Train cars are linked in a specific order so that they may be loaded, unloaded, transferred, dropped off, and picked up in the most efficient manner possible.

To Use

• Dynamic Size: Linked lists can grow or shrink dynamically, as memory allocation is done at runtime.

• Insertion and Deletion: Adding or removing elements from a linked list is efficient, especially for large lists.

• Flexibility: Linked lists can be easily reorganized and modified without requiring a contiguous block of memory.