Introduction to Data Structures

Study Notes

Data Structures provide an organized way to store and manage data in a computer program.
Algorithms define steps to solve problems systematically and efficiently.
Data Structures are classified as Linear and Non-linear data structures.
Linear data structures are arranged sequentially (arrays, linked lists, stacks, queues).
Non-linear data structures have hierarchical relationships (trees, graphs).

Linked Lists are a linear data structure where elements are linked together using pointers.
Each node in a linked list contains data and a pointer to the next node.
Pointers are variables that store memory addresses, allowing you to navigate through the list.
Basic operations on linked lists include traversing, inserting, and deleting nodes.
There are several types of linked lists: singly linked lists, doubly linked lists, circular linked lists.

Stacks are a linear data structure that follows the LIFO (Last-In, First-Out) principle.
They operate like a stack of plates, where the last element added is the first to be removed.
Stacks can implemented using arrays or linked lists.
Stacks are used in various scenarios such as function call stacks and undo/redo functionality.

Queues are a linear data structure that follows the FIFO (First-In, First-Out) principle.
They are like a line at a store, where the first person in line is the first to be served.
Basic operations in queues include enqueue (adding an element) and dequeue (removing an element).
Circular queues are a variation that allows for efficient utilization of memory.
Priority Queues prioritize elements for processing based on a specific criteria.
Queues have applications in scheduling tasks, handling interrupts, and managing network requests.

Search algorithms help find specific elements within a dataset.
Linear Search sequentially checks each element until the desired element is found.
Binary Search efficiently searches a sorted list by repeatedly dividing the search interval in half.
Interpolation Search is similar to Binary Search but estimates the position of the element using interpolation.

Sorting algorithms arrange elements within a dataset in a specific order (ascending or descending).
Bubble Sort compares adjacent elements and swaps them if they are in the wrong order.
Selection Sort repeatedly finds the minimum element and places it in the correct position.
Insertion Sort builds the sorted list by inserting elements at their correct positions.
Quick Sort uses divide and conquer approach to recursively sort sub-arrays around a pivot element.
Merge Sort divides the array into halves, sorts them recursively, and merges the sorted halves.

Hash Tables are data structures that use hash functions to map keys to unique indices in an array.
Hash function converts keys into integer values to determine their position in the array.
Hash collisions occur when different keys hash to the same index.
Hash tables provide efficient key lookup and insertion operations.
Binary Trees are non-linear data structures where each node can have at most two children (left and right).
Binary trees can be used to implement search trees, heap structures, and other hierarchical data structures.