Data Structure and Algorithms

Data Structures and Algorithms

Unit I: Basics of Data Structures

  • Data Structures: Organizing data in memory; types include arrays, linked lists, stacks, queues, etc.

  • Types of Data Structures:

    • Primitive: Holds single values (e.g., int, char, float).

    • Non-primitive: Includes collections of data (e.g., arrays, linked lists).

Arrays

  • Definition: Collection of similar data items stored at contiguous memory locations.

  • Properties:

    1. Same data type.

    2. Stored at contiguous locations.

    3. Randomly accessible via index.

  • Advantages: Easy to remember names, simple traversal, direct access by index.

  • Memory Allocation: Determined by indexing methods (e.g., 0-based, 1-based).

Linked Lists

  • Linked List: Sequence of nodes where each node contains data and a link to the next.

  • Types:

    • Simple Linked List: Forward navigation only.

    • Doubly Linked List: Forward and backward navigation.

    • Circular Linked List: The last node points to the first.

  • Operations: Insertion, deletion, displaying, searching.

Stacks and Queues

  • Stack: LIFO structure; operations include push (insert) and pop (remove).

  • Queue: FIFO structure; operations include enqueue (insert) and dequeue (remove).

  • Representation: Can be implemented using arrays or linked lists.

Evaluation of Expression

  • Notations: Infix, Prefix (Polish), Postfix (Reverse Polish).

  • Precedence and Associativity: Rules for evaluating expressions.

Algorithms on Data Structures

  • Searching: Locate elements in data structures (e.g., linear, binary search).

  • Sorting: Arrange data in order (e.g., quick sort, merge sort).

  • Insertion/Deletion: Modify structure by adding/removing elements.

Advantages of Data Structures

  • Efficiency: Optimal choice increases program’s time and space efficiency.

  • Reusability: Multiple programs can use the data structure.

  • Abstraction: Users interact with the interface without needing implementation details.