Data Structures

Understand stacks, queues, linked lists, and hash tables

Stack

A Stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. Elements are added and removed from the same end (top). Common operations include push, pop, and peek.

Time: O(1) for push/pop/peek

Space: O(n)

Queue

A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front. Common operations include enqueue and dequeue.

Time: O(1) for enqueue/dequeue

Space: O(n)

Linked List

A Linked List is a linear data structure where elements are stored in nodes, and each node points to the next node. It allows dynamic memory allocation and efficient insertion/deletion operations.

Time: O(1) for insert/delete, O(n) for search

Space: O(n)

Binary Search Tree

A Binary Search Tree (BST) is a binary tree where each node has at most two children, and the left subtree contains values less than the node, while the right subtree contains values greater than the node.

Time: O(log n) average, O(n) worst for search/insert/delete

Space: O(n)

Hash Table

A Hash Table is a data structure that implements an associative array, mapping keys to values using a hash function. It provides average O(1) time complexity for insertion, deletion, and lookup operations.

Time: O(1) average, O(n) worst for insert/delete/search

Space: O(n)

Heap

A Heap is a specialized tree-based data structure that satisfies the heap property. In a binary heap, the parent node is either greater than or equal to (max-heap) or less than or equal to (min-heap) its children. Heaps are commonly used to implement priority queues.

Time: O(log n) insert, O(log n) delete, O(1) peek

Space: O(n)