Data Structures: Arrays and Lists

Data Structure

Array and List Structures

Array
- A collection of elements identified by index or key.
- Fixed size, meaning the size must be defined at creation.
- Elements are stored in contiguous memory locations.
- Access time is O(1) for retrieval and update due to direct indexing.
- Suitable for storing data of the same type.
List
- Dynamic in size, can grow or shrink as needed.
- Types:
  - Singly Linked List: Each element points to the next; allows for efficient insertions/deletions.
  - Doubly Linked List: Each element points to both the next and the previous element; allows bidirectional traversal.
  - Circular Linked List: Last element links back to the first, useful for circular traversal.
- Access time is O(n) for retrieval and update since traversal is required.
- More flexible than arrays regarding data manipulation.

Tree Algorithms

Tree Structure
- A hierarchical structure consisting of nodes, with a single root node and sub-nodes (children).
- Each node contains a value and references to its children.
Binary Tree
- Each node has at most two children (left and right).
- Types:
  - Full Binary Tree: Every node has 0 or 2 children.
  - Complete Binary Tree: All levels are filled except possibly for the last level.
  - Perfect Binary Tree: All internal nodes have two children and all leaves are at the same level.
Binary Search Tree (BST)
- A binary tree where the left child contains values less than the parent and the right child contains values greater.
- Efficient for searching, insertion, and deletion (average O(log n)).
Tree Traversal Algorithms
- In-order: Left, Root, Right (yields sorted order in BST).
- Pre-order: Root, Left, Right (used for copying trees).
- Post-order: Left, Right, Root (used for deleting trees).
- Level-order: Visits nodes level by level (uses a queue).
Balanced Trees
- AVL Tree: Self-balancing BST where heights of two child subtrees of any node differ by no more than one.
- Red-Black Tree: A BST with an extra bit for denoting the color of a node (red or black), ensuring the tree remains approximately balanced.
Heap
- A complete binary tree where the parent node is either greater (max-heap) or less (min-heap) than its children.
- Commonly used for implementing priority queues.
Complexity
- Searching: O(n) for simple structures, O(log n) for balanced trees.
- Insertion/Deletion: O(n) for lists, O(log n) for balanced trees.

Array and List Structures

Array
- Fixed-size collection of elements accessed by index or key.
- Stored in contiguous memory locations for efficient access.
- Retrieval and updates have a time complexity of O(1).
- Ideal for uniform data types.
List
- Dynamic in size; can adjust as elements are added or removed.
- Types include:
  - Singly Linked List: Efficient insertions and deletions; each element points to the next.
  - Doubly Linked List: Each element points to both next and previous elements, allowing bi-directional traversal.
  - Circular Linked List: Last element connects to the first, supporting circular traversal.
- Retrieval and updates take O(n) time due to required traversal, offering more data manipulation flexibility than arrays.

Tree Algorithms

Tree Structure
- Hierarchical organization of nodes with a single root and multiple child nodes.
- Each node holds a value and references to its children.
Binary Tree
- Each node contains at most two children (left and right).
- Types of binary trees:
  - Full Binary Tree: Every node has either zero or two children.
  - Complete Binary Tree: All levels filled except possibly the last.
  - Perfect Binary Tree: All internal nodes have two children and leaves are at the same depth.
Binary Search Tree (BST)
- Left child values are less than the parent; right child values are greater.
- Average time complexities for searching, insertion, and deletion are O(log n).
Tree Traversal Algorithms
- In-order: Visits left child, then root, then right child; results in sorted order for BSTs.
- Pre-order: Visits root, then left and right children; useful for tree copying.
- Post-order: Visits left, right children, then root; suitable for tree deletion.
- Level-order: Visits nodes level by level using a queue.
Balanced Trees
- AVL Tree: Self-balancing BST with height differences of no more than one between child subtrees.
- Red-Black Tree: Binary search tree with an added color attribute for nodes, maintaining balance.
Heap
- Complete binary tree where each parent node is either greater (max-heap) or less (min-heap) than its children.
- Commonly utilized for priority queue implementations.