Scribd
Upload
8 views2 pages

Class Notes Computer Science

The document covers fundamental data structures in computer science, including arrays, linked lists, stacks, queues, trees, and binary search trees. It highlights the performance characteristics of each structure, such as time complexities for operations like insertion, deletion, and access. Additionally, it discusses the applications of these data structures in various algorithms and scenarios.

Uploaded by

Subrat
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
8 views2 pages

Class Notes Computer Science

The document covers fundamental data structures in computer science, including arrays, linked lists, stacks, queues, trees, and binary search trees. It highlights the performance characteristics of each structure, such as time complexities for operations like insertion, deletion, and access. Additionally, it discusses the applications of these data structures in various algorithms and scenarios.

Uploaded by

Subrat
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

Computer Science - Data Structures

Lecture 6 | March 25, 2026

1. Arrays and Linked Lists


Arrays:
- Contiguous block of memory, O(1) random access
- Fixed size (static) or resizable (dynamic/ArrayList)
- Insertion/deletion at arbitrary position: O(n)

Linked Lists:
- Each node stores data + pointer to next node
- Singly linked: traversal in one direction only
- Doubly linked: traversal in both directions
- Insertion/deletion at known position: O(1)
- Random access: O(n) — must traverse from head

Trade-off: arrays are better for random access; linked lists are better for frequent insertions/deletions.

2. Stacks and Queues


Stack (LIFO — Last In, First Out):
- Operations: push(item), pop(), peek(), isEmpty()
- All operations O(1)
- Applications: function call stack, undo operations, expression evaluation, backtracking algorithms

Queue (FIFO — First In, First Out):


- Operations: enqueue(item), dequeue(), front(), isEmpty()
- All operations O(1) with proper implementation
- Applications: BFS traversal, task scheduling, print queue, message buffers

Priority Queue: elements dequeued by priority, not insertion order. Typically implemented with a heap.

3. Trees and Binary Search Trees


A tree is a hierarchical data structure with a root node and children. Key terminology:
- Root, parent, child, leaf, depth, height
- A binary tree has at most 2 children per node

Binary Search Tree (BST):


- Left child < parent < right child
- Search, insert, delete: O(h) where h = height
- Balanced BST (AVL, Red-Black): h = O(log n) => all operations O(log n)
- Unbalanced BST: worst case h = O(n) (degenerates to a linked list)

Tree traversals:
- In-order (left, root, right): gives sorted output for BST
- Pre-order (root, left, right): used to copy/serialize a tree
- Post-order (left, right, root): used to delete a tree
- Level-order (BFS): visit nodes level by level

Notes — Computer Science - Data Structures | Page 1

You might also like