Data Structures - Arrays and Queues

Arrays

• A collection of elements of the same data type stored in contiguous memory locations
• Each element is identified by an index or subscript
• Operations:
  • Accessing an element: O(1)
  • Insertion/deletion: O(n)
  • Searching: O(n)
• Advantages:
  • Fast access to elements
  • Efficient use of memory
• Disadvantages:
  • Fixed size
  • Insertion/deletion operations can be slow

Queues

• A First-In-First-Out (FIFO) data structure
• Elements are added to the end (enqueue) and removed from the front (dequeue)
• Operations:
  • Enqueue: O(1)
  • Dequeue: O(1)
  • Peek: O(1)
• Advantages:
  • Efficient insertion and deletion
  • Suitable for job scheduling, print queues, etc.
• Disadvantages:
  • Slow search operation

Trees

• A hierarchical data structure with nodes having a value and child nodes
• Types:
  • Binary Trees: each node has at most two children
  • B-Trees: self-balancing binary trees
• Operations:
  • Insertion: O(log n)
  • Deletion: O(log n)
  • Searching: O(log n)
• Advantages:
  • Efficient search, insertion, and deletion
  • Suitable for file systems, databases, etc.
• Disadvantages:
  • Complex implementation
  • Can be unbalanced

Linked Lists

• A dynamic collection of nodes, each pointing to the next node
• Types:
  • Singly Linked Lists: each node has a reference to the next node
  • Doubly Linked Lists: each node has references to the previous and next nodes
• Operations:
  • Insertion: O(1)
  • Deletion: O(1)
  • Searching: O(n)
• Advantages:
  • Dynamic size
  • Efficient insertion and deletion
• Disadvantages:
  • Slow search operation
  • More memory usage than arrays

Stacks

• A Last-In-First-Out (LIFO) data structure
• Elements are added and removed from the top
• Operations:
  • Push: O(1)
  • Pop: O(1)
  • Peek: O(1)
• Advantages:
  • Efficient insertion and deletion
  • Suitable for parsing, evaluating postfix expressions, etc.
• Disadvantages:
  • Slow search operation
  • Limited access to elements

Arrays

• Arrays store collections of elements of the same data type in contiguous memory locations.
• Each element is identified by an index or subscript.
• Accessing an element in an array takes constant time, O(1).
• Insertion and deletion operations in arrays take linear time, O(n).
• Searching for an element in an array takes linear time, O(n).
• Arrays have fast access to elements and use memory efficiently.
• However, arrays have a fixed size, and insertion and deletion operations can be slow.

Queues

• Queues are First-In-First-Out (FIFO) data structures.
• Elements are added to the end of a queue (enqueue) and removed from the front (dequeue).
• Enqueue, dequeue, and peek operations in queues take constant time, O(1).
• Queues are efficient for insertion and deletion and are suitable for job scheduling and print queues.
• However, search operations in queues are slow.

Trees

• Trees are hierarchical data structures with nodes having values and child nodes.
• Binary Trees are a type of tree where each node has at most two children.
• B-Trees are self-balancing binary trees.
• Insertion, deletion, and searching operations in trees take logarithmic time, O(log n).
• Trees are suitable for file systems and databases due to their efficient search, insertion, and deletion operations.
• However, tree implementation can be complex, and trees can become unbalanced.

Linked Lists

• Linked Lists are dynamic collections of nodes, each pointing to the next node.
• Singly Linked Lists have each node referencing the next node.
• Doubly Linked Lists have each node referencing the previous and next nodes.
• Insertion and deletion operations in Linked Lists take constant time, O(1).
• Searching for an element in a Linked List takes linear time, O(n).
• Linked Lists have dynamic sizes and are efficient for insertion and deletion.
• However, Linked Lists use more memory than arrays and have slow search operations.

Stacks

• Stacks are Last-In-First-Out (LIFO) data structures.
• Elements are added and removed from the top of a stack.
• Push, pop, and peek operations in stacks take constant time, O(1).
• Stacks are efficient for insertion and deletion and are suitable for parsing and evaluating postfix expressions.
• However, stacks have slow search operations and limited access to elements.