1. Singly Linked Lists
The objective of this lab session is to acquire skills in working with singly linked lists. The task is to first
implement the following operations:
1) Create an empty linked list; // do so in the constructor.
2) bool IsEmpty(); // checks whether the list is empty or not. Returns true if empty and false otherwise.
3) InsertAtFront(value); // takes input from a user and inserts it at front of the list
4) Void PrintList();
5) InsertSorted(value); //If we want to maintain a sorted list, we should implement this function
6) Search(value); This function shall search value in a list. If found, we will need to store two addresses:
a. Address of the node in which the searched value is found in a pointer variable named Loc_;
we will store NULL in Loc_ in case value is not found.
b. Address of the node which is logical predecessor of value in a list.
i. The Search() provides functionality for other operations such as insertion in a sorted
list, deleting a value, modifying a value, printing it etc.
7) Delete(value); // searches value and then deletes it if found.
8) DestroyList(); // Distroys all nodes of the list leaving the list in empty state.
Declare Node Class: The data structure that will hold the elements of the list is called Node.
Declare it as follows:
class ListNode{
public:
int data;
ListNode *next;
};
Declare class Linked List:
Now, declare your main class LinkedList. Inside
this class, you shall define all key functions to implement all operations
of a linked list.
class LinkedList{
public:
ListNode *start; // special variable which stores address of head
node.
ListNode *PredLoc_; //to be used by Search(value) method to store
address of logical predecessor of value in a list.
ListNode *Loc_; //to be used by Search(value) method to store address
of the node containing the searched value in a list. If it is not found it
contains NULL.
}
1) Creating a LinkedList
In order to create an empty list, assign NULL value to start pointer
variable.
LinkedList(){
start=NULL;
The objective of this lab session is to acquire skills in working with singly linked lists. The task is to first
implement the following operations:
1) Create an empty linked list; // do so in the constructor.
2) bool IsEmpty(); // checks whether the list is empty or not. Returns true if empty and false otherwise.
3) InsertAtFront(value); // takes input from a user and inserts it at front of the list
4) Void PrintList();
5) InsertSorted(value); //If we want to maintain a sorted list, we should implement this function
6) Search(value); This function shall search value in a list. If found, we will need to store two addresses:
a. Address of the node in which the searched value is found in a pointer variable named Loc_;
we will store NULL in Loc_ in case value is not found.
b. Address of the node which is logical predecessor of value in a list.
i. The Search() provides functionality for other operations such as insertion in a sorted
list, deleting a value, modifying a value, printing it etc.
7) Delete(value); // searches value and then deletes it if found.
8) DestroyList(); // Distroys all nodes of the list leaving the list in empty state.
Declare Node Class: The data structure that will hold the elements of the list is called Node.
Declare it as follows:
class ListNode{
public:
int data;
ListNode *next;
};
Declare class Linked List:
Now, declare your main class LinkedList. Inside
this class, you shall define all key functions to implement all operations
of a linked list.
class LinkedList{
public:
ListNode *start; // special variable which stores address of head
node.
ListNode *PredLoc_; //to be used by Search(value) method to store
address of logical predecessor of value in a list.
ListNode *Loc_; //to be used by Search(value) method to store address
of the node containing the searched value in a list. If it is not found it
contains NULL.
}
1) Creating a LinkedList
In order to create an empty list, assign NULL value to start pointer
variable.
LinkedList(){
start=NULL;
