Data Structures and Algorithms in All Languages

A Heap is a data structure used to implement a Priority Queue (Highest Priority First - HPF). Unlike a standard FIFO queue, a Heap allows for efficient access to the highest priority element.

A Heap is implemented as a complete binary tree, meaning every level is filled except possibly the last, which is filled from left to right. This structure allows the heap to be efficiently represented using an array rather than pointers.

Types of Heaps

• Max Heap: The root node is the maximum element. For every node, the parent must be greater than or equal to its children.
• Min Heap: The root node is the minimum element. For every node, the parent must be smaller than or equal to its children.

A Stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. This means the last item added to the stack is the first one to be removed. It is useful for scenarios where you only need to interact with the most recently inserted item, such as implementing an "undo" feature in a text editor.

A Stack implementation must provide at least these three core operations:

• push(e): Adds an item e to the top of the stack.
• pop(): Retrieves and removes the item currently at the top of the stack.
• peek(): Retrieves the item at the top of the stack without removing it.

A List is a flexible data structure used to store elements. Unlike a standard array, a List does not have a fixed size; when the underlying array reaches capacity, the List automatically copies elements to a larger array in an abstracted way.

In some languages (like Java), all elements in a list must be of the same type, while in others (like Ruby), elements can be of different types.

A Doubly Linked List (DLL) is a linear data structure where items are stored in a chain of cells (nodes) that do not need to be at sequential memory addresses. Unlike arrays, memory for each cell is allocated as needed.

Each node in a DLL contains:

1. Data: The value stored in the node.
2. Next Pointer: A pointer to the address of the next cell in the chain.
3. Previous Pointer: A pointer to the address of the previous cell in the chain.

Because of the dual pointers, DLLs are bi-directional, allowing traversal both forward and backward. This distinguishes them from Singly Linked Lists (SLLs), which only support forward traversal. The first node is known as the head and the last node is known as the tail.

A Singly Linked List (SLL) is a unidirectional data structure where items are stored in a chain of cells (nodes). Unlike arrays, these cells do not need to be at sequential memory addresses; memory is allocated for each cell as needed.

Each cell contains:

1. Data: The actual value stored.
2. Pointer: The address of the next cell in the chain.

A cell with an empty pointer marks the end of the chain. The first node is called the head and the last node is called the tail.

SLLs can be used to implement other data structures such as Stacks, Lists, and Queues.

A Queue is a data structure that follows the FIFO (First-In, First-Out) principle. This means the first item inserted into the queue is the first one to be removed, similar to a real-life waiting line.

Core operations include:

• enqueue(e): Adds an item e to the back of the queue.
• dequeue(): Removes and returns the item at the front of the queue.
• peek(): Retrieves the item at the front of the queue without removing it.

A Set represents an unordered group of unique items. It is the ideal data structure when:

1. The order of items is meaningless.
2. You must ensure that no item in the group occurs more than once.

Note: Operation names may vary depending on the programming language implementation.

Using a Doubly Linked List (DLL) is generally more efficient for Queue implementations because it provides constant time complexity for all primary operations.

enqueue(e)

Adds an item to the back of the DLL.

• Worst Case: $O(1)$

dequeue()

Removes the item from the front of the DLL.

• Worst Case: $O(1)$

peek()

Returns the element at the front of the DLL.

• Worst Case: $O(1)$

A graph is a non-linear data structure represented as G(V,E), where V is a set of vertices (nodes) and E is a set of edges connecting those vertices. Edges are denoted as pairs (u,v).

There are two primary types of graphs:

1. Directed Graphs: Edges have a specific direction (e.g., an edge from A to B allows traversal from A to B, but not B to A).
2. Undirected Graphs: Edges are bidirectional, allowing traversal in both directions between connected nodes.

Note: The implementations provided in this repository assume the use of undirected graphs unless otherwise stated.

Lists use an array as their underlying data structure. The primary difference is that a List manages its own capacity.

When performing an add(e) operation:

1. If the underlying array has space, the element is inserted at the next available index.
2. If the underlying array is full, the List allocates a larger array and copies all existing elements to the new array before inserting the new element.

This resizing process is why the worst-case time complexity for adding an element is $O(N)$ (linear time) rather than $O(1)$ (constant time).