Data structures

Home
Data structures

Data structures

Overview

A data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

Search

Data structures

Linear data structures organize data elements sequentially, where each element is connected to its previous and next element in a single level or dimension.

Array

An array is a collection of elements, each identified by at least one array index or key. Arrays are stored in contiguous memory locations. They can be of fixed size or dynamic.

Time Complexity:
Access: O(1)
Search: O(n)

Stack

A stack is an abstract data type that serves as a collection of elements, with two main operations: push (which adds an element to the collection) and pop (which removes the most recently added element). It follows the Last In First Out (LIFO) principle.

Time Complexity:Push/Pop: O(1)

Queue

A queue is a collection of elements that follows the First In First Out (FIFO) principle. Elements are added at the rear (enqueue) and removed from the front (dequeue). It is often used in scenarios like scheduling, buffering, etc.

Time Complexity:Enqueue/Dequeue: O(1)

Singly Linked List

A singly linked list is a data structure that consists of nodes. Each node contains a data field and a reference (link) to the next node in the sequence. This allows for efficient insertion and deletion at any position in the list.

Time Complexity:Insertion/Deletion: O(1) at known position, O(n) search

Doubly linked list

A doubly linked list is similar to a singly linked list, but each node has two references: one to the next node and another to the previous node, allowing traversal in both directions.

Time Complexity:Insertion/Deletion: O(1) at known position, O(n) search

Non-Linear Data Structures

Non-linear data structures arrange data in a hierarchical manner, where each element may be connected to multiple elements.

Tree

A tree is a hierarchical data structure that consists of nodes, where each node contains a value and references to its child nodes. The topmost node is called the root, and the nodes without children are called leaves.

Graph

A graph is a data structure that consists of a finite set of nodes (vertices) and a set of edges that connect pairs of nodes. Graphs can be directed or undirected, and they are used to represent networks.

Heap

A heap is a special tree-based data structure that satisfies the heap property. In a max heap, for any given node, the value of that node is greater than or equal to the values of its children. In a min heap, the value is less than or equal to the values of its children.

Hash table

A hash table is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots.