Chapter 9 - Data Structrures in Java Flashcards
What is Data Structure?
A data structure is a specialized format for organizing, processing, retrieving and storing data. essential components that help organize and store data efficiently in computer memory. is a way of organizing and storing data in a computer so that it can be accessed and used efficiently
Describe the types of Data Structures?
Linear Data Structure: A data structure is called linear if all of its elements are arranged in the sequential order. In linear data structures, the elements are stored in a non-hierarchical way where each item has the successors and predecessors except the first and last element.
Non-Linear (Hierarichal) Data Structure: The Non-linear data structure does not form a sequence i.e. each item or element is connected with two or more other items in a non-linear arrangement. The data elements are not arranged in the sequential structure.
Can you list data structures?
Linear Data Structures:
Arrays
Linked List
Stacks
Queues
Hierarchical Data Structures:
Binary Trees
Heaps
Hash Tables
What is the difference between file structure and storage structure?
The main difference between file structure and storage structure is based on memory area that is being accessed.
Storage structure: It is the representation of the data structure in the computer memory. Storage structure, on the other hand, refers to the organization of data at a higher level, such as how data is stored on physical storage devices like hard drives, solid-state drives, or cloud storage systems. Examples of storage structures include file systems (e.g., FAT, NTFS, ext4), database management systems (e.g., MySQL, PostgreSQL, MongoDB), and distributed file systems (e.g., Hadoop HDFS, Amazon S3).
File structure: It is the representation of the storage structure in the auxiliary memory. File structure refers to the way data is organized within individual files or records. Examples of file structures include text files (organized as lines or blocks of text), binary files (organized in a specific binary format), XML files (structured using XML tags), and JSON files (formatted using JSON syntax).
List the data structures which are used in RDBMS, Network Data Modal, and Hierarchical Data Model.
RDBMS uses Array data structure
Network data model uses Graph
Hierarchal data model uses Trees
Big O notations
Big O notation is a mathematical notation used in computer science to describe the time complexity or space complexity of an algorithm. It helps in analyzing how the performance of an algorithm scales with the size of the input.
Common Big O Notations:
O(1) - Constant Time Complexity: The algorithm’s runtime is constant and does not depend on the size of the input. For example, accessing an element in an array by index.
O(log n) - Logarithmic Time Complexity: The algorithm’s runtime grows logarithmically as the input size increases. Commonly seen in algorithms like binary search.
O(n) - Linear Time Complexity: The algorithm’s runtime grows linearly with the size of the input. For example, iterating through an array or list of size n.
O(n log n) - Linearithmic Time Complexity: Commonly seen in efficient sorting algorithms like merge sort and quicksort. The runtime grows faster than linear but not as fast as quadratic.
O(n^2) - Quadratic Time Complexity: The algorithm’s runtime is proportional to the square of the input size. Often seen in nested loops iterating over the same collection.
O(2^n) - Exponential Time Complexity: The algorithm’s runtime grows exponentially with the input size. Common in recursive algorithms without proper pruning.
O(n!) - Factorial Time Complexity: The algorithm’s runtime grows at a factorial rate with the input size. Occurs in algorithms generating permutations or combinations.
Examples:
O(1): Retrieving an element from an array by index.
O(log n): Binary search in a sorted array.
O(n): Linear search through an unsorted array.
O(n^2): Bubble sort or selection sort on an array.
O(2^n): Recursive solutions that explore all combinations.
O(n!): Generating all permutations or combinations of a set.
LINK for study
https://coggle.it/diagram/W5E5tqYlrXvFJPsq/t/master-the-interview-click-here-for-course-link/c25f98c73a03f5b1107cd0e2f4bce29c9d78e31655e55cb0b785d56f0036c9d1
Array Data strucutre features in java
Fixed Size: Arrays in Java have a fixed size upon initialization. Once an array is created, its size cannot be changed.
Homogeneous Elements: Arrays store elements of the same data type. For instance, an array of integers will only hold integers, an array of strings will hold strings, and so on.
Indexed Elements: Elements in an array are accessed via an index. The index starts from 0 for the first element and goes up to array.length - 1 for the last element.
Length Property: Arrays have a length property that provides the number of elements contained within the array.
Initialization: Arrays can be initialized during declaration or separately using the new keyword followed by the array type and size.
Dynamic Initialization: Arrays can be initialized with values dynamically during declaration.
Pass by Reference: When an array is passed as a parameter to a method, it is passed by reference. Any changes made to the array within the method affect the original array.
Multidimensional Arrays: Java supports multidimensional arrays, allowing the creation of arrays of arrays. For example, a 2D array is an array of arrays where each element is itself an array.
Length Checking: Java provides a length property for arrays, allowing for easy checking of the number of elements in an array.
Utilities in java.util.Arrays: The java.util.Arrays class provides various utility methods for working with arrays, such as sorting, searching, filling, comparing, etc.
Enhanced for Loop: Java offers an enhanced for loop (for-each loop) that simplifies iterating through elements of an array without explicitly using an index.
Casting: Arrays can be cast to different types, including casting between arrays of different primitive types or casting to an Object type.
Analogy of Array
Array Explorer - The Adventurous Collector
Description: Array Explorer is an adventurous collector who explores a magical land where everything revolves around collecting and organizing various items.
Analogical Traits:
The Collection Coffer: Array Explorer owns a special backpack with fixed compartments. Once set, these compartments remain unchanged, much like a collector’s backpack with specific slots for different treasures.
Uniform Treasures: Each compartment in Array Explorer’s backpack only holds similar items. For example, a section might store only seashells, another only coins, just like a collector categorizes their finds.
Labelled Discoveries: Array Explorer labels each discovery with unique tags, starting from 0 and going up to the number of compartments minus one, just like labeling each treasure with a number.
Counting Relic: Array Explorer carries a magical device resembling an ancient compass that instantly shows how many treasures are collected in the backpack, similar to a treasure map marking how many treasures are found.
Flexible Collection: He can add treasures to his backpack upon its creation or later, rearranging his collection as needed, just like how a collector expands their collection over time.
Shared Adventures: Array Explorer shares his backpack with fellow collectors, allowing them to rearrange items, impacting the entire collection.
Compartmentalized Wonders: His backpack’s compartments sometimes have smaller boxes within them, similar to a set of drawers within a larger chest, allowing for a more organized collection.
Quick Inventory Insight: Array Explorer possesses a magical pendant that instantly tells him the total count of treasures in his backpack, akin to a checklist for a collector’s inventory.
Toolbox of Organization: His kit contains tools for sorting, searching, and comparing treasures, making it easier to manage and explore his collection.
Exploration Loop: He explores his collection one item at a time, using a magnifying glass to study each treasure individually, similar to a collector examining their items.
Shape-Shifting Ability: Array Explorer can transform one type of treasure into another, just like transforming coins into stamps, showcasing versatility in his collection.
50 common array challenges
https://www.geeksforgeeks.org/top-50-array-coding-problems-for-interviews/
Features of LinkedList
In Java, a LinkedList is a data structure that implements the List interface. It stores elements in a linked list format, where each element, or node, contains a reference to the next node in the sequence, forming a chain-like structure. Here are some key features of the LinkedList in Java:
Dynamic Size: LinkedLists dynamically adjust their size as elements are added or removed. This dynamic resizing allows for efficient manipulation of elements.
Node Structure: Each element in a LinkedList is stored as a node object. Each node contains the data and a reference (pointer) to the next node in the sequence.
Insertion and Deletion: Insertion and deletion operations are generally faster compared to other list implementations (like ArrayList) because LinkedLists do not require shifting elements to accommodate changes. Adding or removing elements involves changing references, making it more efficient.
Sequential Access: LinkedLists provide sequential access to elements. Accessing an element by index can be slower compared to ArrayList because it requires traversing the list from the head or tail to reach the desired position.
No Random Access: Unlike arrays or ArrayLists, LinkedLists do not provide efficient random access based on index. Accessing elements by index in a LinkedList has a time complexity of O(n) since it involves traversing the list from the beginning or end.
Iterating through Elements: LinkedLists can be efficiently traversed using iterators or enhanced for loops. The Iterator interface provides methods to sequentially access elements in the list.
Memory Overhead: LinkedLists tend to have a higher memory overhead compared to arrays or ArrayLists because of the additional memory required to store references to the next nodes.
Linked List Analogy
LinkedList Wanderer - The Dynamic Trailblazer
Description: LinkedList Wanderer roams through a mystical realm where discovery and arrangement intertwine in a tapestry of linked wonders.
Analogical Traits:
The Serpentine Path: LinkedList Wanderer carries an enchanted chain where each link seamlessly connects to the next, akin to a traveler’s journey along a winding path.
Fluid Assortment: Similar to a gatherer with an ever-evolving satchel, LinkedList Wanderer’s collection is adaptable, accommodating various treasures of different sizes and types.
Interconnected Realms: Each treasure in LinkedList Wanderer’s possession is connected to its neighbors, forming a web of interconnected stories, much like a collector tracing the history of their acquisitions.
Mutable Array of Gems: Unlike a fixed array, LinkedList Wanderer’s collection can expand and contract dynamically, akin to a collector’s cabinet with shelves that can be adjusted to fit new discoveries.
The Node Nomenclature: LinkedList Wanderer labels each treasure with a unique identifier, reminiscent of a collector’s meticulous cataloging system, ensuring each item’s distinct identity within the collection.
Ephemeral Hoard: Treasures can be seamlessly added or removed from LinkedList Wanderer’s cache, mirroring a collector’s ability to modify their collection on the fly.
Community Caravan: LinkedList Wanderer shares the roadmap of treasures with fellow explorers, allowing collaborative navigation and adjustments, much like a collective effort in curating a shared collection.
Organized Intertwining: Within the LinkedList, mini-compartments of treasures exist, each connected to the next, creating a tapestry of nested collections, similar to drawers within a cabinet housing diverse artifacts.
Fluent Catalog Insights: LinkedList Wanderer possesses an enchanted compass that instantly reveals the count of treasures and their interconnectedness, providing swift insights into the collection’s composition.
Toolset of Fluidity: A magical kit accompanies LinkedList Wanderer, enabling seamless sorting, searching, and comparison of treasures, akin to a collector’s set of tools for managing an ever-expanding collection.
Sequential Expedition: LinkedList Wanderer navigates through the collection in a flowing sequence, examining each treasure individually, much like a collector studying each acquisition with care and attention.
Metamorphic Mastery: With the ability to transform one treasure into another, LinkedList Wanderer showcases the collection’s versatility, reshaping and adapting its contents, akin to an alchemist turning base materials into precious finds.
Difference between array and linkedList
Arrays and linked lists are both data structures used to store collections of elements, but they organize and manage data quite differently:
Arrays:
Contiguous Memory: Arrays store elements in contiguous memory locations, meaning they are placed right next to each other.
Random Access: Elements can be accessed randomly by index. Accessing elements is fast because the index directly maps to the memory location.
Fixed Size: Arrays usually have a fixed size allocated at the beginning, making it challenging to resize dynamically without creating a new array and copying elements.
Insertion/Deletion: Inserting or deleting elements within an array can be costly, especially in the middle, as it may involve shifting elements to accommodate the change.
Linked Lists:
Non-Contiguous Memory: Linked lists don’t require contiguous memory. Elements are linked via pointers, with each element containing a reference to the next (singly linked list) or both previous and next elements (doubly linked list).
Sequential Access: Traversing a linked list involves following the pointers sequentially from one element to the next. Random access is not efficient since you can’t directly access an element by index.
Dynamic Size: Linked lists can easily grow or shrink by adding or removing elements without requiring pre-allocation or resizing.
Insertion/Deletion: Insertions and deletions are generally more efficient in linked lists compared to arrays. Adding or removing an element involves changing pointers, not shifting elements.
challenges about linkedList
https://medium.com/javarevisited/top-20-linked-list-coding-problems-from-technical-interviews-90b64d2df093
Stack Data structure
Stack is a data structure that follows the Last In, First Out (LIFO) principle. It’s like a stack of plates where the last plate you put on the stack is the first one to be removed. Here are the main features and operations associated with Stacks in Java:
Push: Adds an element to the top of the stack.
Method: push(E item)
Pop: Removes the element at the top of the stack and returns it.
Method: pop()
Peek: Retrieves the element at the top of the stack without removing it.
Method: peek()
Empty check: Checks if the stack is empty or not.
Method: empty()
Search: Searches for an element in the stack and returns its position (counting from the top of the stack). Returns -1 if the element is not found.
Method: search(Object o)
Queues
Queues are another fundamental data structure in computer science. Unlike stacks (which follow the Last In, First Out - LIFO - principle), queues adhere to the First In, First Out (FIFO) principle. It’s similar to waiting in a line where the first person to join the line is the first one to be served.
Key features and operations associated with queues include:
Enqueue: Adds an element to the back of the queue.
Method: enqueue(E item)
Dequeue: Removes and returns the element at the front of the queue.
Method: dequeue()
Peek: Retrieves the element at the front of the queue without removing it.
Method: peek()
Empty check: Checks if the queue is empty or not.
Method: isEmpty()
Size: Determines the number of elements in the queue.
Method: size()
Similar to stacks, queues can be implemented using various data structures such as arrays, linked lists, or other structures.
In Java, the java.util.Queue interface represents a queue. Some of its commonly used implementing classes are LinkedList and ArrayDeque.
DOuble ended queue
Certainly! A Double-ended Queue, commonly referred to as Deque (pronounced as “deck”), is a versatile linear data structure that supports insertion and deletion at both ends. It extends the capabilities of a regular queue by allowing operations to be performed at both the front and the back. Key features of Deque include:
Insertion and Deletion at Both Ends: A Deque allows efficient insertion and deletion of elements at both the front and the back. This enables flexibility in implementing various algorithms and data structures.
FIFO and LIFO Operations: Deque supports both FIFO (First In, First Out) and LIFO (Last In, First Out) paradigms. It can function as a queue, stack, or a combination of both, depending on how you use its methods.
Efficient Implementation of Stacks and Queues: Due to its support for both front and back insertion/deletion, a Deque can efficiently implement stack and queue functionalities. For example, elements can be added or removed from either end to simulate a queue or a stack.
Random Access: Some Deque implementations, such as ArrayDeque, offer indexed access to elements, allowing efficient random access to elements similar to an array.
Resizable and Dynamic: Most Deque implementations in Java, like ArrayDeque, are resizable and dynamically adjust their size based on the number of elements they contain. This flexibility eliminates the need for a fixed size and allows for efficient memory usage.
Iterator Support: Deque supports iterators, allowing traversal of elements in a linear order. Iterators provide methods to sequentially access and manipulate elements within the Deque.
Binary Tree
A binary tree is a hierarchical data structure composed of nodes where each node has at most two children, referred to as the left child and the right child. It’s a fundamental tree structure widely used in computer science and is characterized by its hierarchical organization.
Key features of a binary tree:
Nodes: Each node in a binary tree contains data and references or pointers to its left and right children (subtrees).
Root: The topmost node of the tree is called the root node. It’s the starting point for accessing the entire tree.
Parent, Child, and Siblings: Nodes in a binary tree have relationships with their parent nodes (a node that points to them) and their children (nodes they point to). Nodes with the same parent are called siblings.
Leaf Nodes: Nodes that do not have any children are called leaf nodes or terminal nodes.
Depth and Height: The depth of a node is the length of the path from the root to that node. The height of a tree is the maximum depth of any node in the tree.
Binary trees can be categorized based on their properties:
Full Binary Tree: A binary tree in which every node other than the leaves has two children.
Complete Binary Tree: A binary tree where every level is completely filled except possibly the last level, which is filled from left to right.
Balanced Binary Tree: A binary tree where the depth of the two subtrees of every node differs by at most one.
Binary Heap
A binary heap is a specialized binary tree-based data structure that satisfies the heap property. Specifically, it’s commonly implemented as an array, where the elements are arranged in a way that allows for efficient heap operations. There are two main types of binary heaps: the min-heap and the max-heap.
Here are the key features of a binary heap:
Heap Property: A binary heap satisfies either the min-heap property or the max-heap property:
In a min-heap, for any node ‘i’ other than the root, the value of ‘i’ is greater than or equal to the value of its parent.
In a max-heap, for any node ‘i’ other than the root, the value of ‘i’ is less than or equal to the value of its parent.
Complete Binary Tree Structure: A binary heap is a complete binary tree, meaning all levels of the tree are fully filled except possibly the last level, which is filled from left to right.
Array Representation: A binary heap is typically implemented using an array, where the elements are arranged in a way that preserves the heap property. For a node at index ‘i’, its left child is at index 2i + 1, and its right child is at index 2i + 2.
Efficient Operations:
Insertion: Adding an element to a binary heap involves placing it at the next available position in the array and then performing a “heapify” operation to maintain the heap property.
Deletion: Removing the root element of the heap (either the minimum or maximum, depending on whether it’s a min-heap or max-heap) and then rearranging the remaining elements to restore the heap property.
Heapify: Reordering elements in the heap to maintain the heap property after an insertion or deletion operation.
Priority Queue Implementation: Binary heaps are often used as the underlying data structure for implementing priority queues due to their efficient operations for retrieving the minimum or maximum element.
Time Complexity: The main operations of insertion, deletion, and finding the minimum or maximum element in a binary heap have time complexities of O(log n), where n is the number of elements in the heap.
ArrayList
ArrayList is a part of the Java Collections Framework and is a dynamic array implementation of the List interface. It provides a resizable array that can grow or shrink in size as elements are added or removed. Here are some key features of ArrayList in Java:
Dynamic Sizing:
ArrayList is dynamic in size, meaning it can grow or shrink as needed. It automatically adjusts its capacity based on the number of elements added or removed.
Random Access:
ArrayList provides constant-time access to elements using their index. This allows for efficient random access to elements in the list.
Duplicates Allowed:
ArrayList allows duplicate elements. It maintains the order in which elements are added and allows multiple elements with the same value.
Implements List Interface:
ArrayList implements the List interface, which means it supports methods like add, remove, get, contains, and more. This makes it suitable for tasks that involve maintaining an ordered collection of elements.
Resizable Array:
Internally, ArrayList uses an array to store elements. When the array reaches its capacity, a new array with an increased size is created, and the elements are copied from the old array to the new one. This process ensures that the ArrayList can efficiently grow or shrink based on the number of elements.
Null Values Allowed:
ArrayList allows null as a valid element. You can add null to an ArrayList and retrieve it like any other element.
Performance Considerations:
While ArrayList provides fast random access, adding or removing elements in the middle of the list can be slower compared to operations at the beginning or end of the list. This is because elements may need to be shifted to accommodate the changes.
Not Thread-Safe:
ArrayList is not synchronized and is not thread-safe. If multiple threads access an ArrayList concurrently and at least one of the threads modifies the list structurally, it must be synchronized externally.
Set
In Java, the Set interface is a part of the Java Collections Framework and is designed to represent a collection of unique elements. It does not allow duplicate elements, and it does not guarantee the order of elements. The Set interface extends the Collection interface and is implemented by several classes in the Java standard library.
Key characteristics of the Set interface:
No Duplicate Elements:
A Set does not allow duplicate elements. If you attempt to add an element that is already present in the set, the add method returns false, and the set remains unchanged.
No Index-Based Access:
Unlike List, elements in a Set are not indexed. You cannot access elements by their position, as there is no order guarantee.
Common Methods:
The Set interface includes common methods inherited from the Collection interface, such as add, remove, contains, size, isEmpty, and clear.
Iterator:
You can iterate over the elements of a Set using an iterator. The order in which elements are iterated may not be predictable and depends on the specific implementation.
Implementations:
Some commonly used implementations of the Set interface are:
HashSet: An unordered collection that uses a hash table to store elements.
LinkedHashSet: Similar to HashSet, but it maintains the order of insertion.
TreeSet: A sorted set implemented as a Red-Black tree.
HashSet
HashSet is a class in the Java Collections Framework that implements the Set interface. It is designed to store a collection of unique elements. The elements are stored in a hash table, providing constant-time average complexity for basic operations such as add, remove, contains, and size. Here are some key features of HashSet:
No Duplicate Elements:
HashSet does not allow duplicate elements. If an attempt is made to add an element that is already present in the set, the add method returns false, and the set remains unchanged.
Unordered Collection:
The elements in a HashSet are not stored in any specific order. There is no guarantee on the order in which elements are stored or retrieved.
Backed by a HashMap:
Internally, a HashSet is backed by a HashMap instance, where the elements of the set are used as keys, and a constant dummy value (PRESENT) is used as the corresponding value in the map. This allows for efficient element retrieval.
Null Element:
HashSet allows a single null element to be stored. If you attempt to add more than one null, a NullPointerException will be thrown.
Iterating Over Elements:
You can iterate over the elements of a HashSet using an iterator. However, remember that the order of iteration is not guaranteed.
Performance:
HashSet provides constant-time average complexity for basic operations like add, remove, contains, and size. However, the actual performance can vary depending on factors such as load factor and hash collisions.
LinkedHashset
LinkedHashSet is a class in the Java Collections Framework that extends the HashSet class and implements the Set interface. It is similar to HashSet but with an additional feature: it maintains the order of insertion, providing predictable iteration order. Here are the key features of LinkedHashSet:
Order Preservation:
Unlike HashSet, LinkedHashSet maintains the order in which elements are inserted into the set. When you iterate over the elements, they are returned in the order in which they were added.
No Duplicate Elements:
Similar to HashSet, LinkedHashSet does not allow duplicate elements. If an attempt is made to add an element that is already present, the add method returns false, and the set remains unchanged.
Linked Structure:
Internally, LinkedHashSet maintains a doubly-linked list in addition to a hash table. This linked structure is used to maintain the order of insertion.
Iterating Over Elements:
Iterating over the elements of a LinkedHashSet using an iterator or the enhanced for loop will produce elements in the order they were added.
Performance:
While LinkedHashSet provides predictable iteration order, its basic operations such as add, remove, contains, and size still have constant-time average complexity. The actual performance can vary depending on factors such as load factor and hash collisions.
Null Element:
Similar to HashSet, LinkedHashSet allows a single null element to be stored. If you attempt to add more than one null, a NullPointerException will be thrown.
TreeSet
TreeSet is a class in the Java Collections Framework that implements the NavigableSet interface and extends the AbstractSet class. It is designed to store a sorted set of unique elements. TreeSet uses a Red-Black tree as its underlying data structure to maintain the elements in sorted order. Here are the key features of TreeSet:
Sorted Order:
TreeSet maintains the elements in sorted (ascending) order. The sorting is based on the natural ordering of elements or a specified comparator during the set’s construction.
No Duplicate Elements:
Like other sets, TreeSet does not allow duplicate elements. If an attempt is made to add an element that is already present, the add method returns false, and the set remains unchanged.
NavigableSet Interface:
TreeSet implements the NavigableSet interface, which extends the SortedSet interface. This interface provides methods for navigation, such as lower, floor, ceiling, and higher, allowing you to find elements relative to a given element.
Red-Black Tree Structure:
Internally, TreeSet uses a Red-Black tree, a balanced binary search tree data structure. This ensures efficient retrieval, insertion, and deletion of elements, with a time complexity of O(log n) for basic operations.
Null Element:
TreeSet does not allow null elements. If you attempt to add a null element, a NullPointerException will be thrown.
Iterating Over Elements:
Iterating over the elements of a TreeSet using an iterator or the enhanced for loop will produce elements in sorted order.
Performance:
While TreeSet provides a sorted order, the basic operations such as add, remove, contains, and size still have a time complexity of O(log n). The actual performance can vary depending on factors such as the structure of the tree.
Map
In Java, the Map interface is a part of the Java Collections Framework and represents a collection of key-value pairs, where each key is associated with exactly one value. The Map interface is implemented by several classes in the Java standard library, providing different ways to store and retrieve key-value pairs. Here are some key features of the Map interface:
Key-Value Pairs:
A Map consists of key-value pairs, where each key is associated with a specific value. The keys must be unique within the map, but different keys can be associated with the same value.
No Duplicate Keys:
Each key in a Map must be unique. If you attempt to insert a key that already exists in the map, the new value will overwrite the existing value associated with that key.
Common Methods:
The Map interface includes common methods such as put(key, value), get(key), remove(key), containsKey(key), containsValue(value), keySet(), values(), and entrySet().
Implementations:
Some commonly used implementations of the Map interface are:
HashMap: An unordered collection of key-value pairs based on a hash table.
LinkedHashMap: Similar to HashMap, but it maintains the order of insertion.
TreeMap: A sorted map implemented as a Red-Black tree.
Null Key and Values:
Depending on the specific implementation, some Map classes may allow null keys and values. For example, HashMap allows one null key, and LinkedHashMap allows both null keys and values.
Iterating Over Entries:
You can iterate over the entries of a Map using an iterator or an enhanced for loop. The entrySet() method returns a Set view of the mappings, which can be used for iteration.
