Scribd
Upload
3 views3 pages

Data Structures and Algorithms Guide

The document covers fundamental concepts in computer science, including time and space complexity, data structures like stacks, linked lists, queues, and trees, as well as searching algorithms such as linear and binary search. It provides examples of time and space complexities for various operations. Each data structure and algorithm is explained with its corresponding time complexity for better understanding.

Uploaded by

adsurerahul96
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views3 pages

Data Structures and Algorithms Guide

The document covers fundamental concepts in computer science, including time and space complexity, data structures like stacks, linked lists, queues, and trees, as well as searching algorithms such as linear and binary search. It provides examples of time and space complexities for various operations. Each data structure and algorithm is explained with its corresponding time complexity for better understanding.

Uploaded by

adsurerahul96
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

1.

Time and Space Complexity


Time complexity is a measure of the amount of time an algorithm takes to complete, based on
input size (n).

Space complexity refers to the amount of memory used by the algorithm, including input and
auxiliary space.

Example: Linear Time


​
func printArray(_ arr: [Int]) {​
for item in arr {​
print(item)​
}​
}​
// Time: O(n), Space: O(1)​

2. Stack
A stack is a Last In First Out (LIFO) structure. Elements are added/removed from the top.

​
var stack = [Int]()​
stack.append(10)​
stack.append(20)​
stack.removeLast() // removes 20​

Time Complexity: push O(1), pop O(1), peek O(1)

3. Linked List
A linked list is a linear data structure where each element points to the next.

​
class Node {​
var value: Int​
var next: Node?​
init(_ value: Int) { self.value = value }​
}​
4. Queue
A queue is a First In First Out (FIFO) structure. Enqueue at the end, dequeue from the front.

​
var queue = [Int]()​
queue.append(1) // enqueue​
let first = queue.removeFirst() // dequeue​

Time Complexity: enqueue O(1), dequeue O(n) using array

5. Tree
A tree is a hierarchical data structure with nodes connected by edges.

​
class TreeNode {​
var value: Int​
var left: TreeNode?​
var right: TreeNode?​
init(_ value: Int) { self.value = value }​
}​

6. Searching Algorithms

i. Linear Search
​
func linearSearch(_ array: [Int], _ target: Int) -> Int? {​
for (i, val) in array.enumerated() {​
if val == target {​
return i​
}​
}​
return nil​
}​
// Time: O(n), Space: O(1)​

ii. Binary Search


​
func binarySearch(_ array: [Int], _ target: Int) -> Int? {​
var low = 0, high = array.count - 1​
while low <= high {​
let mid = (low + high) / 2​
if array[mid] == target { return mid }​
else if array[mid] < target { low = mid + 1 }​
else { high = mid - 1 }​
}​
return nil​
}​
// Time: O(log n), Space: O(1)​

You might also like