2
\$\begingroup\$

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" ; 
}
\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

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.

\$\endgroup\$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.