Linked Lists, Searching, and Sorting in C++
1. Linked Lists
Linked Lists are linear data structures where elements (nodes) are connected using pointers.
They allow dynamic memory allocation and efficient insertions/deletions.
Types:
1. Singly Linked List: Each node points to the next node.
2. Doubly Linked List: Each node points to both the next and previous nodes.
Operations on Linked Lists:
1. Insertion: Add elements at the start, end, or arbitrary positions.
2. Deletion: Remove elements from the start, end, or arbitrary positions.
3. Traversal: Visit each node to process or display its data.
Key Advantages:
1. Dynamic size adjustment.
2. Efficient memory utilization.
1.1 Singly Linked List Example (C++)
class Node {
public:
int data;
Node* next;
Node(int value) { data = value; next = nullptr; }
};
class SinglyLinkedList {
private:
Node* head;
public:
SinglyLinkedList() { head = nullptr; }
void insertAtEnd(int value) { ... }
void traverse() { ... }
void deleteAtStart() { ... }
void deleteAtEnd() { ... }
};
2. Searching Algorithms
Searching involves finding a target value in a collection.
1. Linear Search:
- Sequentially checks each element for the target value.
- Time Complexity: O(n).
2. Binary Search:
- Divides the search space into halves and searches in the sorted array.
- Time Complexity: O(log n).
3. Sorting Algorithms
Sorting involves arranging elements in a specific order.
1. Bubble Sort:
- Repeatedly swap adjacent elements if they are in the wrong order.
- Time Complexity: O(n^2).
2. Selection Sort:
- Find the minimum element and place it at the beginning.
- Time Complexity: O(n^2).
3. Insertion Sort:
- Build the sorted portion one element at a time.
- Time Complexity: O(n^2).
4. Quick Sort:
- Partition the array and recursively sort the partitions.
- Time Complexity: O(n log n).
5. Merge Sort:
- Divide the array into halves, sort them, and merge.
- Time Complexity: O(n log n).
4. Complete Example: Linked List with Sorting and Searching
The following code demonstrates a complete implementation of a singly linked list
with insertion, deletion, traversal, sorting (Bubble Sort), and searching (Linear and Binary).
Refer to the full code in the study material for implementation details.
