Data Structures: Arrays and Lists

Study Notes

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.

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.

Description

This quiz covers the fundamentals of arrays and list structures in data organization. You will explore the characteristics, types, and algorithms associated with arrays, singly linked lists, doubly linked lists, and circular linked lists. Test your understanding of access times and overall functionality of these data structures.