Data Structures: Introduction

Summary

• Data structures play a critical role in organizing and managing data efficiently.
• Linear and non-linear structures have different characteristics and applications.
• Operations such as insertion, deletion, searching, and sorting are fundamental to working with any data structure.
• Understanding the strengths and limitations of each data structure helps in making the right choice for specific applications.

1. What is a Data Structure?

A Data Structure is a method of organizing, storing, and managing data efficiently so that operations such as insertion, deletion, and retrieval can be performed effectively.

For example, think of a library where books are arranged in a systematic manner. If the books are arranged properly, finding, adding, or removing a book becomes easier. Similarly, data structures organize data in a way that optimizes various operations.

2. Importance of Data Structures

Data structures play a vital role in computer science for the following reasons:

• They help manage large volumes of data efficiently.
• They allow faster searching, sorting, and modification of data.
• They optimize memory usage and processing time.
• They facilitate the design of efficient algorithms.

3. Types of Data Structures

Data structures are mainly classified into two categories:

1. Linear Data Structures

In linear data structures, data is stored sequentially, one after the other.

• Array:

  • A fixed-size collection of elements stored in contiguous memory locations.
  • Elements can be accessed using an index.
  • Example: arr[5] = {10, 20, 30, 40, 50}
  • Suitable for fast data access but has a fixed size.

• Linked List:

  • A sequence of nodes where each node stores data and a pointer to the next node.
  • Types:
    • Singly Linked List: Nodes point only to the next node.
    • Doubly Linked List: Nodes point to both the next and previous nodes.
    • Circular Linked List: The last node points to the first node.

• Stack:

  • Follows the Last In, First Out (LIFO) principle.
  • Example: A stack of plates.
  • Basic operations:
    • push() – Add an element to the top.
    • pop() – Remove the top element.
    • peek() – Retrieve the top element without removing it.

• Queue:

  • Follows the First In, First Out (FIFO) principle.
  • Example: A queue at a ticket counter.
  • Types:
    • Simple Queue
    • Circular Queue
    • Priority Queue
    • Double-Ended Queue (Deque)

2. Non-Linear Data Structures

Non-linear data structures store data in a hierarchical manner.

• Tree:

  • A hierarchical structure where data is stored in nodes connected by edges.
  • Types include:
    • Binary Tree
    • Binary Search Tree (BST)
    • AVL Tree
    • Heap
    • Trie

• Graph:

  • A collection of nodes (vertices) connected by edges.
  • Types include:
    • Directed Graph
    • Undirected Graph
    • Weighted Graph

4. Abstract Data Types (ADT)

An Abstract Data Type (ADT) defines a set of operations that can be performed on a data structure without specifying the implementation details.

Examples:

• List: Collection of ordered elements.
• Stack: Operates using LIFO.
• Queue: Operates using FIFO.
• Deque: Supports insertion and deletion at both ends.

5. Operations on Data Structures

Data structures support the following fundamental operations:

1. Insertion: Adding a new element to the structure.
2. Deletion: Removing an existing element.
3. Traversal: Accessing and processing all elements sequentially.
4. Searching: Finding the position of an element.
5. Sorting: Arranging data in a specific order.

6. Arrays

• Definition: An array is a collection of elements of the same type stored in contiguous memory locations.
• Declaration:

int arr[5] = {10, 20, 30, 40, 50};

• Indexing: Elements can be accessed using an index.
• Operations:
  • Insertion
  • Deletion
  • Searching
  • Traversal

7. Linked List

• Definition: A linked list is a sequence of nodes where each node stores data and a pointer to the next node.
• Types:
  • Singly Linked List: Nodes point only to the next node.
  • Doubly Linked List: Nodes point to both the next and previous nodes.
  • Circular Linked List: The last node points back to the first node.

8. Stack

• Definition: A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.
• Basic Operations:
  • push() – Adds an element to the top.
  • pop() – Removes the top element.
  • peek() – Retrieves the top element without removing it.

Stack Implementation:

stack<int> s;
s.push(10);
s.push(20);
s.pop(); // Removes 20