Data Structures: Arrays and Linked Lists

Array and Linked List Basics

• Arrays are fixed-size collections of elements of the same data type, stored contiguously in memory.
• Accessing elements in an array is very fast (O(1) time complexity) as the index directly maps to the memory location.
• Insertion and deletion of elements in the middle of an array is slow (O(n) time complexity) due to the need to shift other elements.
• Linked lists are dynamic data structures where elements are not stored contiguously.
• Each element (node) in a linked list contains data and a pointer to the next node.
• Insertion and deletion of elements in a linked list are generally faster (O(1)) than in an array, as no elements need to be shifted.
• Accessing elements in a linked list is slower (O(n)) as you need to traverse the list starting from the beginning.
• Different types of linked lists exist, such as Singly Linked Lists, Doubly Linked Lists, and Circular Linked Lists.

Sorting Algorithms

• Sorting algorithms arrange elements in a specific order (ascending or descending).
• Bubble Sort: Compares adjacent elements and swaps if they are in the wrong order. It's inefficient with O(n^2) time complexity.
• Selection Sort: Finds the smallest element and places it at the beginning, repeating this process for the remaining elements, also O(n^2).
• Insertion Sort: Builds the sorted array one element at a time. It's efficient for small datasets and has a time complexity of O(n^2).
• Merge Sort: Divides the array into smaller subarrays, sorts them recursively, and then merges them. It has a time complexity of O(n log n).
• Quick Sort: Selects a pivot element and partitions the array into elements less than and greater than the pivot, then sorts recursively. It generally has good performance as O(n log n), but the worst-case is O(n^2).

Searching Algorithms

• Searching algorithms find a specific element within a dataset.
• Linear Search: Checks each element sequentially until the target element is found or the end of the dataset is reached. O(n) time complexity.
• Binary Search: Works on sorted arrays by repeatedly dividing the search interval in half. Requires a sorted array. O(log n) time complexity, very efficient when data is large.

Stack and Queue Implementation

• Stacks: Follow the Last-In, First-Out (LIFO) principle. Common operations include push (add to the top), pop (remove from the top), peek (view the top element).
• Queues: Follow the First-In, First-Out (FIFO) principle. Common operations include enqueue (add to the rear), dequeue (remove from the front), peek (view the front element).
• Stacks and queues can be implemented using arrays or linked lists.
• Array-based implementations are often faster for access, while linked-list-based implementations are more flexible for varying sizes.