Detailed Notes: Linked Lists, Searching, and Sorting in C++
1. Linked Lists
Linked Lists are a linear data structure where elements are connected via pointers. Each element,
called a node, contains two parts:
1. Data: The actual value stored in the node.
2. Pointer: A reference to the next (or previous, in doubly linked lists) node in the sequence.
Advantages:
- Dynamic size adjustment (no need to define size beforehand).
- Efficient insertion and deletion (no need for shifting elements).
Types:
1. Singly Linked List: Each node contains a pointer to the next node.
2. Doubly Linked List: Each node contains pointers to both the next and previous nodes.
Key Operations:
1. Insertion: Adding a new element at a specific position.
2. Deletion: Removing an element from a specific position.
3. Traversal: Visiting all elements in the list sequentially.
1.1 Singly Linked List Implementation in C++
class Node {
public:
int data;
Node* next;
Node(int value) { // Constructor
data = value;
next = nullptr;
};
class SinglyLinkedList {
private:
Node* head;
public:
SinglyLinkedList() { head = nullptr; }
void insertAtStart(int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
void insertAtEnd(int value) {
Node* newNode = new Node(value);
if (!head) { head = newNode; return; }
Node* temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
}
void traverse() {
Node* temp = head;
while (temp) {
cout << temp->data << " -> ";
temp = temp->next;
cout << "NULL
";
void deleteAtStart() {
if (!head) return;
Node* temp = head;
head = head->next;
delete temp;
void deleteAtEnd() {
if (!head) return;
if (!head->next) { delete head; head = nullptr; return; }
Node* temp = head;
while (temp->next->next) temp = temp->next;
delete temp->next;
temp->next = nullptr;
}
};
2. Searching Algorithms
Searching is the process of finding the location of a specific element in a collection.
Key algorithms include:
1. Linear Search:
- Works on both sorted and unsorted data.
- Iterates through each element until the target is found.
- Time Complexity: O(n).
Algorithm:
1. Start from the first element.
2. Compare each element with the target.
3. If found, return the index.
4. If the end is reached, return -1 (not found).
Example Code:
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) return i;
return -1;
2. Binary Search:
- Requires sorted data.
- Divides the search space in half and checks the middle element.
- Time Complexity: O(log n).
Algorithm:
1. Set pointers (low and high) at the start and end of the array.
2. Calculate the mid-point: mid = low + (high - low) / 2.
3. Compare the mid-point with the target:
- If equal, return the index.
- If target < mid-point, adjust high = mid - 1.
- If target > mid-point, adjust low = mid + 1.
4. Repeat until low > high.
Example Code:
int binarySearch(int arr[], int n, int target) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
return -1;
3. Sorting Algorithms
Sorting arranges data in ascending or descending order.
1. Bubble Sort:
- Repeatedly compares adjacent elements and swaps them if out of order.
- Time Complexity: O(n^2).
Example Code:
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
2. Selection Sort:
- Select the smallest element and move it to the correct position.
- Time Complexity: O(n^2).
Example Code:
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
swap(arr[i], arr[minIndex]);
}
3. Quick Sort:
- Divides the array into two parts (based on a pivot) and recursively sorts them.
- Time Complexity: O(n log n).
4. Merge Sort:
- Recursively divides the array, sorts each half, and merges them.
- Time Complexity: O(n log n).
These algorithms are faster for larger data sets but require recursion and additional space.
4. Complete Example
Below is a complete implementation of a singly linked list in C++ with sorting and searching
functionalities.
Refer to the provided examples to implement insertion, deletion, bubble sort, linear search, and
binary search.
