Pre-lab Exercise
1. Which of the following is true about linked list and structure
a. Structures that hold pointers of instance of them are called self referential structures.
b. A linked list is a data structure that can store an indefinite amount of items
c. Item can be added or removed from the middle of the list
d. To use linked list we need to define an initial size.
e. Structures can contain instance of themselves
f. There is no random access in linked list.
Answer
The correct statements about linked lists and structures are:
a. Structures that hold pointers to instances of themselves are called self-referential
structures.
True. This is a key concept in creating linked lists where each node contains a pointer to the
next node.
b. A linked list is a data structure that can store an indefinite amount of items.
True. A linked list can grow dynamically as items are added, limited only by system memory.
c. Items can be added or removed from the middle of the list.
True. Items can be inserted or deleted from any position in a linked list, which is one of its
advantages over arrays.
d. To use a linked list, we need to define an initial size.
False. Unlike arrays, linked lists do not require an initial size to be defined; they grow
dynamically.
e. Structures can contain instances of themselves.
False. Structures cannot contain direct instances of themselves. However, they can contain
pointers to instances of themselves, which is common in linked lists.
f. There is no random access in a linked list.
True. Linked lists do not support random access because you must traverse the list sequentially
to access a specific node.
2. Which of the following basic operation that single linked list support
a. Insert last− Add an element at the end of the list.
b. Delete first − Deletes an element at the beginning of the list.
c. Display backward − Displays the complete list in a backward manner.
d. Search − Searches an element using the given key.
e. Delete − Deletes an element using the given key.
Answer
In a singly linked list, the following operations are generally supported:
1. Insert last: Supported
Adding an element at the end of the list is a basic operation.
2. Delete first: Supported
Deleting an element at the beginning of the list is straightforward as you can update the
head pointer to the next node.
3. Display backward: Not directly supported
A singly linked list does not have pointers to previous nodes, so traversing backward
requires extra logic, like recursion or using an auxiliary data structure (e.g., a stack).
4. Search: Supported
Searching an element by traversing the list from the head is a standard operation.
5. Delete: Supported
Deleting an element using a key can be achieved by traversing the list, locating the
node, and adjusting pointers.
3. Assume the below structure declaration and implement the given algorithm using C++
struct Student
int age;
string name;
Student *next;
}*head=NULL;
a. Create a new node with age=19 and name=’Abrham’
b. Initialize the new node with head
c. Check whether the list is empty or not
d. Check whether the node is the last node or not
Answer
#include <iostream>
#include <string>
using namespace std;
// Structure declaration
struct Student {
int age;
string name;
Student *next;
} *head = NULL;
int main() {
// Step a: Create a new node with age=19 and name='Abrham'
Student *newNode = new Student;
newNode->age = 19;
newNode->name = "Abrham";
newNode->next = NULL;
// Step b: Initialize the new node with head
newNode->next = head;
// Step c: Check whether the list is empty or not
if (head == NULL) {
cout << "The list is empty." << endl;
} else {
cout << "The list is not empty." << endl;
}
// Update the head to point to the new node
head = newNode;
// Step d: Check whether the node is the last node or not
if (newNode->next == NULL) {
cout << "The new node is the last node." << endl;
} else {
cout << "The new node is not the last node." << endl;
}
// Free the allocated memory (cleanup)
delete newNode;
head = NULL;
return 0;
}
Explanation of the Code:
1. Step a:
○ A new node is created using new Student.
○ The age and name fields of the node are assigned values 19 and "Abrham",
respectively.
2. Step b:
○ The next pointer of the new node is initialized to point to the head (which is
initially NULL).
3. Step c:
○ A check is performed to determine whether the list is empty (head == NULL).
4. Step d:
○ A check is performed to see if the next pointer of the new node is NULL,
indicating it is the last node.
5. Memory Management:
○ The dynamically allocated memory for the new node is freed after use. This is
important to avoid memory leaks.
In-lab Exercise
5. Write a C++ program to implement login profile, which help the organization to perform the
following functions:
a. Insert the record of login profile
b. Delete the record of an existing login profile
c. Find the record of an existing login profile
d. Display Report
Following information of each login profile will be stored Login ID: an integer value to store the
unique id for user Username: the username of each user. Password: password of each user
Answer
#include <iostream>
#include <string>
using namespace std;
// Define a struct for each login profile node
struct LoginProfile {
int loginID;
string username;
string password;
LoginProfile* next; // Pointer to the next node
// Constructor to initialize a new node
LoginProfile(int id, string user, string pass) {
loginID = id;
username = user;
password = pass;
next = NULL;
}
};
// Class to handle the linked list operations
class LoginManager {
private:
LoginProfile* head; // Pointer to the first node
public:
LoginManager() : head(NULL) {}
// Function to insert a new login profile
void insertProfile(int id, string user, string pass) {
LoginProfile* newProfile = new LoginProfile(id, user, pass);
newProfile->next = head;
head = newProfile;
cout << "Profile inserted successfully.\n";
}
// Function to delete a login profile by ID
void deleteProfile(int id) {
if (!head) {
cout << "The list is empty. Cannot delete.\n";
return;
}
if (head->loginID == id) {
LoginProfile* temp = head;
head = head->next;
delete temp;
cout << "Profile with ID " << id << " deleted successfully.\n";
return;
}
LoginProfile* current = head;
while (current->next && current->next->loginID != id) {
current = current->next;
}
if (current->next) {
LoginProfile* temp = current->next;
current->next = current->next->next;
delete temp;
cout << "Profile with ID " << id << " deleted successfully.\n";
} else {
cout << "Profile with ID " << id << " not found.\n";
}
}
// Function to find a login profile by ID
void findProfile(int id) {
LoginProfile* current = head;
while (current) {
if (current->loginID == id) {
cout << "Profile found:\n";
cout << "Login ID: " << current->loginID << "\n";
cout << "Username: " << current->username << "\n";
cout << "Password: " << current->password << "\n";
return;
}
current = current->next;
}
cout << "Profile with ID " << id << " not found.\n";
}
// Function to display all profiles
void displayProfiles() {
if (!head) {
cout << "No profiles to display.\n";
return;
}
LoginProfile* current = head;
cout << "List of Profiles:\n";
while (current) {
cout << "Login ID: " << current->loginID << ", Username: " << current->username
<< ", Password: " << current->password << "\n";
current = current->next;
}
}
// Destructor to free memory
~LoginManager() {
LoginProfile* current = head;
while (current) {
LoginProfile* temp = current;
current = current->next;
delete temp;
}
}
};
// Main function to demonstrate the program
int main() {
LoginManager manager;
int choice, id;
string username, password;
do {
cout << "\nLogin Profile Management\n";
cout << "1. Insert Profile\n";
cout << "2. Delete Profile\n";
cout << "3. Find Profile\n";
cout << "4. Display Profiles\n";
cout << "5. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter Login ID: ";
cin >> id;
cout << "Enter Username: ";
cin >> username;
cout << "Enter Password: ";
cin >> password;
manager.insertProfile(id, username, password);
break;
case 2:
cout << "Enter Login ID to delete: ";
cin >> id;
manager.deleteProfile(id);
break;
case 3:
cout << "Enter Login ID to find: ";
cin >> id;
manager.findProfile(id);
break;
case 4:
manager.displayProfiles();
break;
case 5:
cout << "Exiting the program.\n";
break;
default:
cout << "Invalid choice. Try again.\n";
}
} while (choice != 5);
return 0;
}
Post-lab Exercise
1. What is the benefit and drawback of using linked lists
Answer
Benefits of Using Linked Lists in C++
1. Dynamic Memory Allocation:
○ Linked lists use dynamic memory allocation, allowing efficient memory usage.
○ They can grow and shrink in size during runtime without the need for reallocating
or reorganizing memory.
2. Efficient Insertion/Deletion:
○ Adding or removing elements from a linked list is O(1) if you already have a
pointer to the node. This is particularly useful for applications where frequent
insertions or deletions are needed.
3. No Wasted Space:
○ Unlike arrays, linked lists do not require pre-allocating memory, so there's no
wasted memory due to over-allocation.
4. Flexibility:
○ Linked lists allow elements to be stored non-contiguously, which is helpful in
scenarios with fragmented memory.
5. Custom Data Structures:
○ Linked lists can be used as the foundation for implementing other data structures
such as stacks, queues, and graphs.
Drawbacks of Using Linked Lists in C++
1. Memory Overhead:
○ Each node requires extra memory for a pointer to the next node (and possibly the
previous node in doubly linked lists), which can be significant when storing many
small elements.
2. Slower Access Times:
○ Accessing an element in a linked list is O(n) since you must traverse the list
sequentially, unlike arrays, which allow O(1) access using an index.
3. Cache Unfriendliness:
○ Linked lists are not cache-friendly because elements are stored in
non-contiguous memory locations, leading to more cache misses compared to
arrays.
4. Complexity in Implementation:
○ Managing pointers and ensuring proper memory allocation/deallocation increases
complexity and the risk of errors like memory leaks and dangling pointers.
5. Debugging and Maintenance:
○ Debugging linked list operations can be more challenging compared to arrays
due to pointer manipulation.
