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)

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)