I have just started learning data structures and for the past two days I was going through linked lists.
I have implemented the basic/common operations on the linked lists and I would love for some feedback and discuss best practices.
P.S: I will also try the STL method, but for starters I did this.
/*
A list of the common operations in a linked list !
I will keep updating it as I learn new operations
*/
#include <iostream>
using namespace std;
struct node{
int data ;
node *next ;
} *head ;
class Lnklist{
public :
Lnklist() ; // initializes the head pointer to NULL at first
node* node_create(int) ;
void print() ;
void print_with_arg(node *) ;
void print_recursively(node *) ;
// insert operations
void insert_at_head(int) ;
void insert_at_last(int) ;
void insert_at_pos( int , int ) ;
// delete operations
void delete_at_head() ;
void delete_at_last() ;
void delete_at_pos(int) ;
// reversing the linked list
node* reverse_iteratively(node *) ;
void recursively_reverse(node *) ;
};
Lnklist::Lnklist(){
head = NULL ;
}
node* Lnklist::node_create( int num ){
// this allocates m/y and stores the data "num" there
node *temp = new node() ;
temp->data = num ;
temp->next = NULL ;
return temp ;
}
void Lnklist::print(){
cout << "\nElements : " ;
node *temp = head ;
while(temp != NULL){
cout << temp->data << " ";
temp = temp->next ;
}
cout << endl ;
}
void Lnklist::print_recursively(node *head){
if (head == NULL) {
return ;
}
cout << head->data << " " ;
print_recursively(head->next) ;
}
void Lnklist::insert_at_head( int num ){
node *temp = node_create(num) ;
temp->next = head ;
head = temp ;
// inserted
print() ;
}
void Lnklist::insert_at_last( int num ){
node *temp = node_create(num) ;
// now I need to traverse till the end of the linked list !!
node *traverse = head ;
while(traverse->next != NULL){
traverse = traverse->next ;
}
traverse->next = temp ;
// inserted at last
print() ;
}
void Lnklist::insert_at_pos(int pos , int num){
node *temp = node_create(num) ;
cout << "\nInserting " << num << " at " << pos << "nd position " << endl;
node *traverse = head ;
for (int i = 1; i < pos-1; ++i){
traverse = traverse->next ;
}
node *nth_node = traverse->next ;
temp->next = nth_node ;
traverse->next = temp ;
cout << "After insertion : " ;
print() ;
}
void Lnklist::delete_at_head(){
cout << "Before deletion : " ;
print() ;
node *temp = head ;
head = temp->next ;
delete temp ;
cout << "\nafter deletion : " ;
print() ;
}
void Lnklist::delete_at_last(){
cout << "\nBefore deletion : " ;
print() ;
node *traverse = head ;
while(traverse->next->next != NULL) {
traverse = traverse->next ;
}
traverse->next = NULL ;
cout << "\nAfter deletion : " ;
print() ;
}
void Lnklist::delete_at_pos(int pos){
cout << "\nBefore Deletion : " ;
print() ;
node *traverse = head;
for (int i = 1 ; i < pos - 1; ++i){
traverse = traverse->next ;
}
node *to_be_deleted = traverse->next ;
traverse->next = to_be_deleted->next ;
delete to_be_deleted ;
cout << "\nAfter Deletion at position " << pos << " : " ;
print() ;
}
node* Lnklist::reverse_iteratively(node *head){
node *current, *next_node, *previous ;
current = head ;
previous = NULL ;
while(current != NULL){
next_node = current->next ;
current->next = previous ;
// now I need to update my variables
previous = current ;
current = next_node ;
}
head = previous ;
return head ;
}
void Lnklist::print_with_arg(node *temp){
head = temp ;
print() ;
}
void Lnklist::recursively_reverse(node *head){
if (head == NULL) {
return ;
}
recursively_reverse(head->next) ;
cout << head->data << " " ;
}
int main(){
cout << "\n" ;
Lnklist obj ;
obj.insert_at_head(1) ;
obj.insert_at_head(2) ;
cout << endl << "Inserting at last : " << endl ;
obj.insert_at_last(4) ;
obj.insert_at_last(5) ;
cout << "\nInserting at a particular position : " << endl ;
obj.insert_at_pos(2, 10) ;
cout << "\nDeleting : " << "\n"
<< "\nDeleting at the head : \n " ;
obj.delete_at_head() ;
cout << "\nDeleting at the end : \n" ;
obj.delete_at_last() ;
cout << "\nDeleting at a position : " << 2;
obj.delete_at_pos(2) ;
cout << "\nReversing the linked list recursively_reverse : " ;
node *temp = obj.reverse_iteratively(head) ;
obj.print_with_arg(temp) ;
cout << "\nReversing the elements of the linked list using recursion : " ;
obj.recursively_reverse(head) ;
cout << "\n" ;
}
1 Answer 1
A few tips to start with:
Node and global variables:
struct node{ int data ; node *next ; } *head ;
A few issues with this struct: First, it declares a global pointer *head Notice that you have declared it at the top level scope, so the variable is a global, which defeats the purpose of a class, that is being able to have several instances of a type. If you declare another Lnklist, they would share this same variable. What you probably wanted was to nest this struct inside the list class. It would be a good idea placing it inside the private section of Lnklist. Second minor change would be renaming it to Node, to be consistent with the class naming convention:
class Lnklist {
public:
....
private:
struct Node {
int data;
Node* next;
}
Node* head;
};
Spacing:
This style of adding a space after every ; is very unusual (first time I've seen it, actually). That seems pointless, and doesn't improve readability. I recommend removing that extra space after semicolons.
Some people like to put a space after the parens in function parameter lists, such as in insert_at_last( int num ). I personally don't see a point in that, but I wont openly advise against this one.
Avoid using namespace:
That should never be done in a header file (.h). For a small program like this one, it shouldn't ever be an issue, but it can cause problems in a more realistic scenario. Read a full discussion here.
Const correctness:
Printing a list should not alter its contents, so those methods should be const to make that clear to the reader and enforce it at compile-time.
void print() const;
^^^^^
The const must also be added to the implementation.
Missing a destructor:
The lack of a destructor would force a user to manually delete all nodes in the list to prevent memory leaks. If you add a class destructor to Lnklist, once an instance of the class goes out of scope, the destructor would automatically cleanup for you. Read the link above to know more about C++ destructors.
Consider using templates:
At the moment, your list is only capable of storing integer numbers. As you might know, the Standard std::list<T> container is a template class, which allows it to store any type the user places between the < > when declaring a list (e.g. a list of strings: std::list<std::string>). Your next exercise could be converting this list to use C++ templates instead of ints.