ADS - Unit 1 and 2 Notes
ADS - Unit 1 and 2 Notes
The Fundamentals of Object-Oriented Programming: Necessity for OOP, Data Hiding, Data
Abstraction, Encapsulation, Procedural Abstraction, Class and Object, Scope of Class and
Scope Resolution Operator, Member Function of a Class, private, protected, and public Access
Specifier.
Object-oriented programming (OOP) is a popular programming paradigm that revolves around the
concept of "objects" which can contain data, in the form of fields (attributes or properties), and code,
in the form of procedures (methods or functions). This paradigm is centered on organizing software
design around data, rather than functions or logic.
1. Class:
- A class is a blueprint or template for creating objects. It defines the attributes and behaviors that the
objects will have.
- Attributes are represented by variables and are often called properties or fields.
- Behaviors are represented by methods or functions.
2. Object:
- An object is an instance of a class. It's a concrete entity created based on the class, possessing the
properties and behaviors defined in the class.
3. Encapsulation:
- Encapsulation is the concept of bundling the data (attributes) and the methods that operate on the
data into a single unit (i.e., class). It restricts access to certain components, preventing the direct
modification of data.
4. Abstraction:
- Abstraction involves highlighting essential features while hiding the irrelevant details. It allows you
to focus on what an object does instead of how it does it, making complex systems more manageable.
5. Inheritance:
- Inheritance allows a new class (derived or child class) to inherit properties and behaviors from an
existing class (base or parent class).
- It promotes code reusability and enables the creation of hierarchical relationships between classes.
6. Polymorphism:
- Polymorphism means the ability to take on many forms. It allows objects of different classes to be
treated as objects of a common superclass through inheritance.
- Polymorphism is often achieved through method overriding and method overloading.
2. Ease of Maintenance:
- By organizing code into objects and classes, maintenance becomes easier. Modifications or
updates can be localized to specific objects or classes without impacting the entire system, as long as
the interfaces are preserved.
5. Polymorphism:
- Polymorphism allows objects to be treated as instances of their parent class, enabling flexibility in
implementing methods that are common to different classes.
6. Real-world Modeling:
- OOP mimics real-world entities, making it easier for developers to model and represent real-world
objects in their code, enhancing understanding and design.
7. Encourages Collaboration:
- OOP can support collaborative development as different developers can work on different classes
or objects simultaneously, allowing for better team collaboration.
OOP isn't always the best paradigm for every project, and different programming paradigms might be
more suitable depending on the project's nature. However, its flexibility, scalability, and
maintainability have made OOP a cornerstone in modern software development.
Data hiding and data abstraction are two essential concepts in object-oriented programming that
contribute to the overall structure, security, and maintainability of code.
Data Hiding:
Data hiding, also known as information hiding, is the concept of restricting direct access to certain
parts of an object. It's an essential principle in OOP that helps in securing data and preventing
accidental or intentional misuse of data. This is typically achieved by making the data private within a
class, allowing only the class's methods to access and manipulate it. Outside classes or objects cannot
directly access this data.
Data Abstraction:
Data abstraction is a broader concept that refers to providing only essential information to the outside
world and hiding the background details or implementations. It involves displaying only the necessary
features of an object and hiding its complex implementation details.
1. Data Hiding:
- Encapsulation involves hiding the internal state of an object from the outside world. This is often
achieved by making the internal data private within the class, allowing access and modification of that
data only through specific methods (getters and setters).
2. Access Control:
- By using access control modifiers (such as private, protected, and public in many programming
languages), encapsulation allows the class designer to specify which parts of the data and methods are
accessible to other parts of the program.
3. Information Hiding:
- Encapsulation supports information hiding, which means that the internal implementation details
of an object are hidden and only necessary information is exposed to the outside world through well-
defined interfaces.
Benefits of Encapsulation:
1. Data Hiding:
- Using access specifiers (public, private, protected), C++ allows you to control the visibility of
class members. Private members are only accessible within the class.
2. Access Specifiers:
- `private`: Members declared as private are only accessible within the class, and not by code
outside the class.
- `public`: Members declared as public are accessible from outside the class.
- `protected`: Members declared as protected are accessible within the class and its derived classes.
```cpp
#include <iostream>
class BankAccount {
private:
// Private member variables
int accountNumber;
double balance;
public:
// Setter methods to set private member variables
void setAccountNumber(int num) {
accountNumber = num;
}
double getBalance() {
return balance;
}
};
int main() {
BankAccount acc;
return 0;
}
```
In this example:
- `BankAccount` is a class that encapsulates account information.
- The member variables `accountNumber` and `balance` are private, restricting direct access from
outside the class.
- Setter methods (`setAccountNumber`, `setBalance`) and getter methods (`getAccountNumber`,
`getBalance`) provide controlled access to the private member variables.
Encapsulation in C++ helps in keeping the internal representation of the class hidden, providing
controlled access to the class's data, and maintaining the integrity of the object's state. This principle
contributes to better security, maintainability, and flexibility in software development.
Procedural abstraction
Procedural abstraction is a programming concept that involves hiding the implementation details of a
procedure (a block of code that performs a specific task) while exposing only the essential
information needed to interact with it. This concept is not exclusive to object-oriented programming
and can also be found in procedural or structured programming paradigms.
3. Encapsulation of Logic:
- The essential logic of a task is encapsulated within a procedure, allowing it to be invoked without
the need to know how the operation is carried out internally.
1. Abstraction of Complexity:
- It simplifies program design by breaking down complex tasks into smaller, manageable
procedures, abstracting away the intricate implementation details.
2. Code Reusability:
- Procedures that perform specific tasks can be reused in different parts of the program or even in
different programs, promoting code reusability and reducing redundancy.
3. Easy Maintenance:
- Changes or updates to a procedure can be made independently without affecting other parts of the
program, as long as the procedure's interface remains unchanged.
```python
# Example of a procedure (function) to calculate the area of a rectangle
def calculate_rectangle_area(length, width):
area = length * width
return area
In this example, `calculate_rectangle_area` is a procedure that encapsulates the logic to calculate the
area of a rectangle. The internal working details of the calculation are hidden from the user, who
interacts with the procedure by providing the required inputs and retrieving the result.
Class in C++:
A class is defined using the `class` keyword and contains a set of data members (attributes) and
member functions (methods). It encapsulates the properties and behaviors that objects will exhibit.
```cpp
// Class declaration
class Car {
public: // Access specifier
// Member variables (attributes)
std::string brand;
int year;
Object in C++:
An object is an instance of a class. It is created using the class blueprint and represents a specific
entity with its own set of attributes and behaviors.
```cpp
int main() {
// Object creation
Car myCar; // Creating an object of the Car class
return 0;
}
```
In this example:
- The `Car` class defines the blueprint for a car, with attributes `brand` and `year`, and a method
`accelerate`.
- In the `main()` function, an object `myCar` is created from the `Car` class by simply using the class
name followed by the object name.
- The object `myCar` is then used to access the attributes and methods defined in the class.
Objects represent specific instances of the class and have their own unique data associated with them.
C++ class and object concepts form the basis of object-oriented programming, allowing for the
creation of complex structures by combining data and functionality within a single entity. This helps
in modeling real-world scenarios and improving code reusability and maintainability.
Scope of the class and scope resolution operator
The scope of a class in object-oriented programming defines where the members (attributes and
methods) of that class can be accessed and used. Additionally, the scope resolution operator is a tool
in some programming languages that allows you to access specific members or methods of a class
within a particular context or scope.
Scope of a Class:
The scope of a class determines where the attributes and methods defined within the class can be
accessed. In most object-oriented languages, classes have their own scope, meaning the members of a
class are accessible within the class itself, typically via object instances or within the class's methods.
Outside the class, these members might have different levels of accessibility based on their access
modifiers (public, private, protected, etc.). For instance:
The scope resolution operator (::) is used in certain programming languages to access the members
(methods and attributes) of a class. It's used to specify the context from which a particular member
should be accessed. For example:
- C++: The scope resolution operator (::) is used to access the members of a class, like so:
```cpp
class MyClass {
public:
void myMethod() {
// Method implementation
}
};
int main() {
MyClass obj;
obj.myMethod(); // Accessing method using the object
- PHP: PHP uses the double colon (::) to access static methods and properties:
```php
class MyClass {
public static function myMethod() {
// Method implementation
}
}
It's important to note that the usage and availability of the scope resolution operator may vary
depending on the programming language and its specific syntax and rules.
Access specifiers in C++
In C++, access specifiers are used to control the visibility of class members. There are three access
specifiers in C++: `public`, `private`, and `protected`.
Example (C++):
```cpp
class MyClass {
public: // Public section
int publicVar; // Public member
void publicMethod() {
// Public method
std::cout << "This is a public method" << std::endl;
}
void privateMethod() {
// Private method
std::cout << "This is a private method" << std::endl;
}
void protectedMethod() {
// Protected method
std::cout << "This is a protected method" << std::endl;
}
};
int main() {
MyClass obj;
obj.publicVar = 10; // Accessing public member
obj.publicMethod(); // Accessing public method
// Private and protected members cannot be accessed directly from outside the class
// obj.privateVar = 20; // Error: private member inaccessible
// obj.privateMethod(); // Error: private member inaccessible
return 0;
}
```
In the example:
- `publicVar` and `publicMethod()` are public and can be accessed directly from outside the class.
- `privateVar` and `privateMethod()` are private and cannot be accessed from outside the class.
- `protectedVar` and `protectedMethod()` are protected and cannot be accessed from outside the class,
but they are accessible within derived classes.
Access specifiers in C++ are fundamental for enforcing encapsulation and controlling the visibility of
class members to ensure data integrity and the proper functioning of classes in a program.
Unit II
Priority Queues: Definition, realizing a Priority Queue using Heaps, Insertion, Deletion, Heap
sort, External Sorting. Dictionaries: Linear List Representation, Skip List Representation,
Operations- Insertion, Deletion and Searching.
A priority queue is an abstract data type similar to a regular queue or stack, but with an additional
priority associated with each element. In a regular queue, elements are typically removed in the order
they were added (first-in, first-out, or FIFO), while in a priority queue, elements are removed based
on their priority.
A priority queue is a data structure that supports operations similar to a queue or a stack, but where
elements have an assigned priority. Elements with higher priority are dequeued (or removed) before
those with lower priority.
1. Priority-based Ordering: Elements in a priority queue are ordered based on their assigned priority.
Higher-priority elements are dequeued before lower-priority elements.
2. Support for Insertion and Removal: Elements can be inserted into a priority queue with an
associated priority and removed based on their priority.
4. Implementation: Priority queues can be implemented using various data structures, such as heaps,
binary search trees, or arrays combined with sorting algorithms.
Implementation:
Priority queues can be implemented using various data structures, with heaps being one of the most
commonly used structures due to their efficient implementation of priority queues. Binary heaps, in
particular, are well-suited for priority queues because they allow for efficient addition and removal of
the highest priority element.
Overall, a priority queue is a versatile data structure used when elements need to be processed in an
order based on their respective priorities, enabling the handling of tasks or elements based on their
urgency or importance.
In C++, one common implementation of a priority queue is using the `std::priority_queue` container
provided by the Standard Template Library (STL). This container adapts a heap data structure to
provide efficient retrieval of the highest (or lowest, depending on the comparison function) priority
element.
```cpp
#include <iostream>
#include <queue> // Include the priority_queue header
int main() {
// Define a priority queue of integers (default is a max heap)
std::priority_queue<int> pq;
return 0;
}
```
- Elements are added to the priority queue using the `push` function.
- The `top()` function retrieves the highest priority element without removing it.
- The `pop()` function removes the highest priority element from the priority queue.
By default, `std::priority_queue` creates a max heap. To create a min heap (where the smallest
element has the highest priority), you can specify a comparison function:
```cpp
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
```
This line declares a priority queue of integers (`int`) that operates as a min heap by using
`std::greater<int>` as the comparison function. The `std::greater<int>` will ensure that the smallest
elements have the highest priority.
`std::priority_queue` is quite flexible and can work with various data types and custom data structures.
It provides a convenient way to work with priority queues without having to implement the
underlying data structure from scratch.
```cpp
#include <iostream>
#include <vector>
class MaxHeapPriorityQueue {
private:
std::vector<int> heap;
if (largest != index) {
std::swap(heap[index], heap[largest]);
index = largest;
} else {
break;
}
}
}
public:
// Insert an element into the priority queue
void insert(int value) {
heap.push_back(value);
heapifyUp(heap.size() - 1);
}
heap[0] = heap.back();
heap.pop_back();
heapifyDown(0);
}
int main() {
MaxHeapPriorityQueue pq;
pq.insert(30);
pq.insert(20);
pq.insert(50);
pq.insert(10);
return 0;
}
```
In this implementation:
- The `MaxHeapPriorityQueue` class maintains a vector `heap` representing the max heap.
- The `insert` function adds an element to the heap and maintains the heap property using
`heapifyUp`.
- The `removeTop` function removes the top element (root) of the heap and restructures the heap
using `heapifyDown`.
- The `getTop` function returns the top element without removing it.
This implementation showcases the fundamental operations of a priority queue using a max heap.
Adjustments could be made for a min-heap priority queue by modifying the comparison logic within
the helper functions.
Insertion Operation:
The insertion operation in a priority queue using a heap typically involves adding an element to the
heap and adjusting its position to maintain the heap property.
Deletion Operation:
The deletion operation in a priority queue using a heap typically involves removing the element with
the highest (or lowest) priority and adjusting the heap to maintain the heap property.
```cpp
#include <iostream>
#include <queue> // Include the priority_queue header
int main() {
// Create a priority queue as a max heap
std::priority_queue<int> pq;
return 0;
}
```
This C++ example demonstrates the basic operations of insertion (enqueue) and deletion (dequeue) in
a priority queue implemented using `std::priority_queue`. The `push()` function inserts elements, and
the `top()` and `pop()` functions perform the deletion of elements, maintaining the max-heap property
in the background. The `pop()` function removes the top (highest priority) element from the priority
queue.
Heap sort
Heap sort is a comparison-based sorting algorithm that builds a heap from the given array and then
repeatedly extracts the maximum (for max-heap) element from the heap, thus resulting in a sorted
array.
1. Build a Heap: Convert the given array into a heap. This is usually done by reordering the elements
in the array.
2. Extract the Maximum Element: Remove the root (maximum element for a max-heap) of the heap
and place it at the end of the array.
3. Heapify the Remaining Elements: After removing the maximum element, re-heapify the heap and
reduce its size by one.
4. Repeat until the Entire Array is Sorted: Repeat steps 2 and 3 until the heap is empty and the array is
fully sorted.
```cpp
#include <iostream>
#include <vector>
if (largest != i) {
std::swap(arr[i], arr[largest]);
maxHeapify(arr, n, largest);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
heapSort(arr);
return 0;
}
```
This C++ implementation showcases the steps of the heap sort algorithm:
Heap sort is an in-place, unstable sorting algorithm with a time complexity of O(n log n) for both best
and worst cases. It's efficient and can be used for sorting large sets of data.
External Sorting
External sorting is a technique used to sort large datasets that are too extensive to fit entirely in
memory (RAM). It's an efficient method to handle sorting when the dataset size exceeds the available
memory capacity. External sorting involves using disk storage (secondary storage like hard drives or
SSDs) in addition to the main memory (RAM) for sorting operations.
1. Dividing Data into Chunks: The large dataset is divided into smaller portions or chunks that can fit
into memory.
2. Sort Chunks in Memory: Each chunk is loaded into memory, sorted internally using a sorting
algorithm like quicksort or merge sort.
3. Merge Sorted Chunks: The sorted chunks are merged back, ensuring that elements across chunks
maintain their sorted order.
4. Merging Using Priority Queue or Heap: A priority queue or a heap is commonly used to efficiently
merge the sorted chunks, picking the smallest (or largest) element from each chunk for the final sorted
output.
1. Divide the Dataset: Partition the large dataset into chunks that fit into memory.
2. Sort Each Chunk: Load a chunk into memory and sort it using an in-memory sorting algorithm.
3. Merge Sorted Chunks: Merge the sorted chunks back together, ensuring the final merged output is
in sorted order.
4. Write Sorted Output: Write the final sorted output back to disk or process it further.
Example Scenario:
Consider sorting a massive file that cannot fit entirely into RAM. The file can be divided into smaller
segments (chunks) that fit into memory. Each segment is sorted independently in memory, and the
sorted segments are then merged into a single sorted file.
- K-Way Merge: Sorting a large number of chunks using a K-way merge, where K represents the
number of chunks being merged at a time.
- Replacement Selection: A selection-based algorithm used for sorting, often combined with merge
techniques.
External sorting is widely used in databases, file systems, and other applications where sorting large
volumes of data that exceed the available memory is required. It optimizes the usage of memory and
disk storage, efficiently handling and sorting large datasets.
External sorting is a technique used in computer science and data processing to sort data that is too
large to fit entirely in memory (RAM). In external sorting, data is divided into smaller chunks, each of
which can fit in memory, and these chunks are sorted individually. Once sorted, the chunks are
merged together to produce the final sorted output. This process is particularly useful for handling
very large datasets that cannot be sorted entirely in memory.
The main idea behind external sorting is to minimize the number of expensive read and write
operations to external storage (e.g., hard disk drives) while efficiently utilizing the available memory.
1. Divide: The large dataset is divided into smaller chunks or blocks, often referred to as "runs,"
which can fit into memory. The size of each run depends on the available memory.
2. Sort: Each run is sorted using an efficient in-memory sorting algorithm, such as quicksort or merge
sort. Sorting smaller blocks in memory is faster than sorting the entire dataset.
3. Merge: The sorted runs are merged into a single output file. This merging process is typically done
in a way that minimizes the number of I/O operations, such as using a priority queue (min-heap) or
external merge-sort techniques.
4. Repeat: If the dataset cannot be sorted entirely in one pass, the merge step is repeated until the
entire dataset is sorted.
External sorting is commonly used in scenarios where data doesn't fit in memory, but it needs to be
sorted efficiently, such as:
Algorithms and techniques for external sorting may vary depending on specific requirements and
constraints. Properly designed external sorting can significantly reduce the time and I/O costs
associated with sorting large datasets.
Dictionaries
The Dictionary Abstract Data Type (ADT) represents a collection of key-value pairs, allowing users
to perform operations such as insertion, deletion, retrieval, and modification of elements based on
their keys. The Dictionary ADT does not permit duplicate keys and usually provides efficient access
to elements.
```plaintext
ADT Dictionary:
- insert(key, value)
- delete(key)
- search(key) -> value
- update(key, value)
- size() -> integer
- keys() -> list
- values() -> list
- clear()
Example Usage:
Dictionary d
d.insert("Alice", 25)
d.insert("Bob", 30)
d.insert("Charlie", 27)
d.update("Alice", 26)
value = d.search("Bob")
d.delete("Charlie")
size = d.size()
keyList = d.keys()
valueList = d.values()
d.clear()
```
The Dictionary ADT provides a flexible and useful structure for managing key-value pairs and allows
efficient retrieval and manipulation of data by keys. The choice of specific implementation (e.g.,
balanced trees or hash tables) might depend on factors such as performance requirements, ordering,
and specific use-case needs.
In C++, a dictionary, often referred to as a map or associative array, is an abstract data structure that
stores a collection of key-value pairs. The `std::map` and `std::unordered_map` containers from the
Standard Template Library (STL) offer implementations of dictionary-like structures.
`std::map` in C++:
The `std::map` is an associative container that stores elements formed by a combination of a key and a
mapped value. It is implemented as a balanced binary search tree, maintaining a sorted order based on
the keys.
```cpp
#include <iostream>
#include <map>
int main() {
// Declaration of a map with key-value pairs
std::map<std::string, int> myMap;
return 0;
}
```
`std::unordered_map` in C++:
The `std::unordered_map` is another associative container that stores elements as key-value pairs. It
uses hashing to organize elements and has a faster average lookup time compared to `std::map`.
However, it doesn't maintain a specific order of elements.
```cpp
#include <iostream>
#include <unordered_map>
int main() {
// Declaration of an unordered_map with key-value pairs
std::unordered_map<std::string, int> myUnorderedMap;
return 0;
}
```
Both `std::map` and `std::unordered_map` offer ways to store key-value pairs, with different trade-
offs in terms of ordering, time complexity, and underlying data structure (sorted binary tree for
`std::map`, and hash table for `std::unordered_map`). The choice between the two often depends on
the specific requirements of the application, such as the need for ordering and the expected operations
(lookup, insertion, deletion, etc.).
A linear list is a fundamental data structure in computer science that represents a collection of
elements in a linear order. It's also known as a sequence, where the elements are arranged
sequentially. There are various ways to represent a linear list, including arrays and linked lists.
Array Representation:
In array representation, the elements are stored in contiguous memory locations, allowing for
constant-time access to elements based on their index. Arrays have fixed sizes, and the elements are
accessed using their index or position.
Linked lists are a dynamic data structure where elements, called nodes, are linked together through
pointers or references. Each node contains the data and a reference to the next node in the sequence.
```plaintext
// Node structure definition
struct Node {
int data;
Node* next;
};
Comparison:
The choice between array and linked list representations depends on the specific use-case
requirements, such as the need for constant-time access, dynamic resizing, and efficient
insertion/deletion operations. Both representations serve as core structures in data processing and
storage.
In an array-based representation, two arrays can be used: one for storing keys and another for storing
corresponding values. The indices of the arrays are used to associate keys with their values.
# Pseudocode Example:
```plaintext
// Initialize arrays for keys and values
array keys[5] = [ "Alice", "Bob", "Charlie", "David", "Eva" ]
array values[5] = [ 25, 30, 27, 35, 22 ]
Using a linked list, each node can contain both a key and its associated value. This is a common
approach, especially for implementing hash tables, where each node in the linked list represents a key-
value pair.
# Pseudocode Example:
```plaintext
// Node structure to represent key-value pair
struct Node {
string key;
int value;
Node* next;
};
Comparison:
- Array-based representations offer direct access to elements by index but may need resizing if the
size is exceeded.
- Linked list-based representations offer dynamic sizing and better handling of insertions and
deletions, but may require traversing the list for searching.
The choice between these representations typically depends on the requirements of the application,
such as the frequency of insertions, deletions, and searches, as well as the expected size of the
dictionary.
Linear List Representation Operations- Insertion, Deletion and Searching
The operations for insertion, deletion, and searching within a linear list (like arrays or linked lists)
involve different steps for each operation.
# Array Representation:
- At a Specific Index: In an array, elements can be inserted at a specific index by shifting elements to
the right and then inserting the new element.
- At the End: To append elements, add the new element at the end of the array.
# Array Representation:
- At a Specific Index: Remove the element at the specified index by shifting elements to the left.
- At the End: Delete the last element in the array.
# Array Representation:
- Linear Search: Traverse the array sequentially and compare each element with the target value until
a match is found or the end of the array is reached.
# Linked List Representation:
- Linear Search: Traverse the linked list sequentially, comparing the data in each node with the target
value until a match is found or the end of the list is reached.
Pseudocode Examples:
```plaintext
// Insert element 'value' at index 'pos' in the array 'arr'
function insertAtIndex(arr, value, pos):
shift elements from pos to end one position to the right
arr[pos] = value
```
```plaintext
// Delete the head node in the linked list
function deleteFromBeginning(head):
if head is not null:
temp = head
head = head->next
deallocate temp
```
```plaintext
// Linear search for 'target' in the array 'arr'
function linearSearch(arr, target):
for i from 0 to length of arr - 1:
if arr[i] equals target:
return i
return "Not found"
```
```plaintext
// Linear search for 'target' in the linked list starting from 'head'
function linearSearch(head, target):
current = head
while current is not null:
if current->data equals target:
return "Found"
current = current->next
return "Not found"
```
Each operation requires different logic and steps, tailored to the specific representation (array or
linked list) and the position (beginning, end, or specific index) where the operation is performed.
Time complexity of Linear List Representation Operations- Insertion, Deletion and Searching
The time complexity of insertion, deletion, and searching operations in linear list representations (like
arrays and linked lists) varies depending on the specific operation and the structure used.
Array Representation:
3. Insertion or Deletion at the End (For Singly Linked List without tail pointer):
- Average Case: O(n) - Requires traversal to the end to perform the operation.
- Worst Case: O(n) - Similar to the average case, as end operations require traversing the entire list.
Overall:
- For arrays, insertion and deletion operations generally take O(n) time due to shifting elements.
- For linked lists, insertions and deletions at the beginning are O(1) on average, while those at the end
might take O(n) time.
Linear searches in both arrays and linked lists involve traversing the entire structure, resulting in O(n)
time complexity in the worst case. The performance of these operations can vary based on the specific
position where the operation is performed and the size of the list.
- Each node in a skip list contains a key (or value) and pointers to the next node at the same level and
the level below. The bottom level represents a traditional linked list.
- Higher-level nodes act as express lanes, allowing for faster search and traversal of the skip list.
1. Search: Starts from the top level and moves down the levels until the appropriate position for the
search key is found.
2. Insertion: Searches for the appropriate position for the new key and then inserts it. While inserting
at the lowest level, a coin toss determines if the element is also included at higher levels.
3. Deletion: Finds and removes the element from the skip list. Adjustments to the pointers are made to
maintain the list's integrity.
```plaintext
+-----------------------------+
| 3 -> 7 -> 9 -> 12 |
+-----------------------------+
| 3 -> 7 9 -> 12 |
+-----------------------------+
|3 7 9 12 |
+-----------------------------+
|3 9 |
+-----------------------------+
```
In the example, each line represents a level in the skip list. Nodes are interconnected through pointers
at different levels, allowing for faster access to the elements.
Skip lists provide an efficient compromise between the simplicity of linked lists and the efficiency of
balanced trees, offering relatively fast search operations with a simple design. This probabilistic
structure makes them a favorable choice in certain scenarios, particularly when balanced trees might
be complex to implement or maintain.
```plaintext
// Insert a key-value pair into the skip list
function insert(key, value):
level = determineLevel() // Randomly determine the level for the new node
new_node = createNode(key, value, level)
current = head // Start from the top level
for i from max_level to 0:
while current->next[i] is not null and current->next[i]->key < key:
current = current->next[i]
if i <= level:
new_node->next[i] = current->next[i]
current->next[i] = new_node
```
```plaintext
// Delete a key-value pair from the skip list
function delete(key):
current = head // Start from the top level
for i from max_level to 0:
while current->next[i] is not null and current->next[i]->key < key:
current = current->next[i]
if current->next[i]->key == key:
to_be_deleted = current->next[i]
current->next[i] = to_be_deleted->next[i]
delete to_be_deleted
```
```plaintext
// Search for a key in the skip list
function search(key):
current = head // Start from the top level
for i from max_level to 0:
while current->next[i] is not null and current->next[i]->key < key:
current = current->next[i]
if current->next[0]->key == key:
return "Key found"
return "Key not found"
```
Skip lists utilize a probabilistic approach to create multiple levels, allowing for faster access to
elements, similar to the working principle of a multi-level index. These operations exploit the multiple
express lanes for improved efficiency in searching, insertion, and deletion.
Time complexity of Skip List Representation Operations- Insertion, Deletion and Searching
In skip lists, the time complexity for insertion, deletion, and searching operations depends on the
height of the skip list and the average number of elements per level. Skip lists maintain logarithmic
time complexity for these operations on average. Here are the details:
Time Complexity:
1. Search Operation:
- Average Case: O(log n)
- Worst Case: O(n)
Details:
- Search Operation:
- In the average case, skip lists exhibit a search time complexity of O(log n), similar to binary search
trees. The search starts from the top level and moves down to the lower levels, which decreases the
number of comparisons significantly.
- In the worst case, if the key to be found is not present in the skip list, the search may reach the last
level, resulting in a time complexity of O(n).
The key feature of skip lists is that they offer a balanced trade-off between simplicity and efficiency.
Their average-case time complexity for insertion, deletion, and searching is O(log n), which makes
them favorable compared to other balanced tree structures in certain scenarios.
However, in rare worst-case scenarios where the structure is not maintained optimally or when the
structure degenerates, skip lists can exhibit linear time complexity. Nevertheless, in practice, this is
rare, and the probabilistic structure of skip lists provides good average-case performance for various
operations.