A data structure is a way of organizing and storing data so that we can perform operations on it efficiently. It defines a particular way of storing data that allows access to the data, manipulation of the data, and operations like searching, inserting, deleting, and updating.
In simpler terms, think of a data structure as a container or an organization method for the data that you work with in your program. Just like in a physical warehouse, where you need to decide how to store boxes, shelves, and items to make retrieval easy, in computer science, data structures help in organizing data to make tasks like searching, insertion, and deletion easier and more efficient.
Data structures can be broadly classified into two categories:
Primitive data structures are the basic types of data that are directly supported by programming languages. These include:
These are the fundamental building blocks that can be used to construct more complex data structures.
Non-primitive data structures are more complex and can store collections of data. They are further classified into:
In linear data structures, elements are stored sequentially, and each element is connected to its previous and next elements (except the first and last element). You can traverse the structure from one element to the next in a linear manner.
Let's explore each of these in detail.
An array is a collection of elements of the same type stored at contiguous memory locations. Arrays are indexed, meaning each element in the array has a unique index or position.
Example: int arr[] = {1, 2, 3, 4, 5};
Operations:
arr[2] gives 3).Time Complexity:
A linked list is a collection of nodes, where each node contains two parts: the data and a reference (or pointer) to the next node in the list. Linked lists are dynamic, meaning they don’t require contiguous memory like arrays.
Example: Node 1 -> Node 2 -> Node 3 -> NULL
Operations:
Types of Linked Lists:
Time Complexity:
A stack is a collection that follows the LIFO (Last In, First Out) principle. The last element added to the stack is the first one to be removed. It can be imagined like a stack of plates where the last plate added is the first to be taken off.
Operations:
Example: Imagine a stack of plates, where the plate added last is the first plate you take off.
Applications:
Time Complexity:
A queue is a collection that follows the FIFO (First In, First Out) principle. The first element added to the queue is the first one to be removed. Think of it like a line at a grocery store: the first person in line is the first to be served.
Operations:
Example: In a queue, the first item added is the first to be removed.
Applications:
Time Complexity:
Non-linear data structures don't store data in a linear sequence. They are more complex and allow for hierarchical relationships between elements.
A tree is a hierarchical data structure with a root node and child nodes. Each node has a value and a list of references to its child nodes. Trees are used to represent hierarchical relationships, like organizational structures or file systems.
Example: A binary tree, where each node has at most two children (left and right).
Operations:
Time Complexity:
A graph is a collection of nodes (also called vertices) and edges that connect pairs of nodes. Graphs are used to represent relationships between objects, such as social networks or roadmaps.
Types of Graphs:
Operations:
Time Complexity:
Data structures are fundamental building blocks in computer science. Understanding how different data structures work helps in choosing the right one for your problem, ensuring that operations like searching, insertion, and deletion can be performed efficiently. Each data structure has its strengths and weaknesses, and choosing the appropriate one depends on the type of problem you're solving and the operations you'll perform most often.
Here's a quick summary of the major data structures:
| Data Structure | Type | Key Operations | Time Complexity (Average) |
|---|---|---|---|
| Array | Linear | Access, Insert, Delete | Access: O(1), Insert/Delete: O(n) |
| Linked List | Linear | Insert, Delete, Traverse | Insert/Delete: O(1), Search: O(n) |
| Stack | Linear | Push, Pop, Peek | Push/Pop/Peek: O(1) |
| Queue | Linear | Enqueue, Dequeue, Peek | Enqueue/Dequeue/Peek: O(1) |
| Tree | Non-linear | Insert, Search, Delete | Balanced Tree: O(log n) |
| Graph | Non-linear | Search, Add/Remove Edge | Adjacency List: O(V+E) |
Open this section to load past papers