Introduction to Data Structures
What data structures and algorithms are, the main kinds, and why the choice matters.
A data structure is a way of organising data in memory so that the operations you need (search, insert, delete, find the smallest, ...) are fast. An algorithm is a finite sequence of well-defined steps that solves a problem. The two go together: a good algorithm is usually a good idea about how to arrange the data.
- Linear structures store items one after another; each item has at most one predecessor and one successor.
- Non-linear structures let an item connect to several others, like a family tree or a road map.
- Hash-based structures jump straight to an item computed from its key.
Why the choice matters
Suppose you need to check whether a number is in a collection of 1000 sorted numbers. Checking one by one (linear search) can take 1000 comparisons. Because the data is sorted, you can instead look at the middle and throw away half each time (binary search), which needs at most 10 comparisons. The data is the same; the algorithm makes it 100 times faster.
public class Main {
static int linearSteps(int[] a, int target) {
int steps = 0;
for (int x : a) {
steps++;
if (x == target) break;
}
return steps;
}
static int binarySteps(int[] a, int target) {
int lo = 0, hi = a.length - 1, steps = 0;
while (lo <= hi) {
steps++;
int mid = (lo + hi) / 2;
if (a[mid] == target) break;
if (a[mid] < target) lo = mid + 1; else hi = mid - 1;
}
return steps;
}
public static void main(String[] args) {
int[] nums = new int[1000];
for (int i = 0; i < nums.length; i++) nums[i] = i + 1; // 1, 2, ..., 1000
System.out.println("Linear search for 999: " + linearSteps(nums, 999) + " comparisons");
System.out.println("Binary search for 999: " + binarySteps(nums, 999) + " comparisons");
}
}Linear search for 999: 999 comparisons Binary search for 999: 9 comparisons
def linear_steps(a, target):
steps = 0
for x in a:
steps += 1
if x == target:
break
return steps
def binary_steps(a, target):
lo, hi, steps = 0, len(a) - 1, 0
while lo <= hi:
steps += 1
mid = (lo + hi) // 2
if a[mid] == target:
break
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return steps
nums = list(range(1, 1001)) # 1, 2, ..., 1000
print("Linear search for 999:", linear_steps(nums, 999), "comparisons")
print("Binary search for 999:", binary_steps(nums, 999), "comparisons")Linear search for 999: 999 comparisons Binary search for 999: 9 comparisons
int linear_steps(const int a[], int n, int target) {
int steps = 0;
for (int i = 0; i < n; i++) {
steps++;
if (a[i] == target) break;
}
return steps;
}
int binary_steps(const int a[], int n, int target) {
int lo = 0, hi = n - 1, steps = 0;
while (lo <= hi) {
steps++;
int mid = (lo + hi) / 2;
if (a[mid] == target) break;
if (a[mid] < target) lo = mid + 1; else hi = mid - 1;
}
return steps;
}
int main(void) {
int nums[1000];
for (int i = 0; i < 1000; i++) nums[i] = i + 1; /* 1, 2, ..., 1000 */
printf("Linear search for 999: %d comparisons\n", linear_steps(nums, 1000, 999));
printf("Binary search for 999: %d comparisons\n", binary_steps(nums, 1000, 999));
return 0;
}Linear search for 999: 999 comparisons Binary search for 999: 9 comparisons
Abstract data types
An abstract data type (ADT) describes what operations are allowed, not how they are implemented. A stack ADT promises push, pop and peek; it could be built on an array or on a linked list. Separating the "what" from the "how" lets you swap implementations without changing the code that uses them.
| ADT | Main operations | Common implementations |
|---|---|---|
| List | get, insert, delete by position | array, linked list |
| Stack | push, pop, peek (last in, first out) | array, linked list |
| Queue | enqueue, dequeue (first in, first out) | circular array, linked list |
| Map / dictionary | put, get, remove by key | hash table, balanced search tree |
| Priority queue | insert, remove the minimum | binary heap |
GATE CS syllabus map
This track covers the GATE Computer Science syllabus for Programming and Data Structures and Algorithms. (Programming in C itself is taught in the C tutorial.)
| GATE syllabus topic | Lessons |
|---|---|
| Recursion | Recursion and Recurrence Relations |
| Asymptotic worst-case time and space complexity | Time and Space Complexity, Recurrence Relations |
| Arrays | Arrays and Dynamic Arrays |
| Stacks and queues | Stacks, Queues and Deques |
| Linked lists | Linked Lists |
| Trees and binary search trees | Binary Trees, Binary Search Trees, AVL Trees |
| Binary heaps | Heaps and Priority Queues |
| Graphs and graph traversals | Graphs, BFS and DFS, DFS Applications |
| Shortest paths | Shortest Paths |
| Minimum spanning trees | Minimum Spanning Trees |
| Searching | Searching |
| Sorting | Simple Sorting, Fast Sorting, Heapsort |
| Hashing | Hash Tables |
| Divide and conquer | Divide and Conquer |
| Greedy algorithms | Greedy Algorithms |
| Dynamic programming | Dynamic Programming |
| Mixed revision | GATE Practice Set |
GATE-style practice questions
Which of the following is a non-linear data structure?
Show answer and explanation
Answer: CIn a binary tree a node can have two children, so items are arranged in a hierarchy rather than a single sequence. Stacks, queues and arrays are all linear.
Which of the following are abstract data types rather than concrete implementations? (Select all that apply.)
Show answer and explanation
Answer: A, BA stack and a priority queue only specify operations. A singly linked list and an array-based binary heap are concrete ways of storing data, and can be used to implement those ADTs.
Binary search is run on a sorted array of 1000 distinct elements. What is the maximum number of element comparisons (each comparison of the target with a[mid] counts as one) needed to decide whether a value is present?
Show answer and explanation
Answer: 10Each comparison halves the remaining range. After k comparisons at most 1000 / 2^k elements remain, and the worst case needs floor(log2 1000) + 1 = 9 + 1 = 10 comparisons.