4
\$\begingroup\$

This is supposed to create a single linked list class with head and tail pointers, along with insertion, delete, and search functions.

I tested it on my machine and it seems to run without errors or warnings.

#include <iostream>

using  std::cout;
using  std::cin;
using  std::endl;

struct node {
    int key;
    struct node *next;
};

class linked_list {
    private:
        struct node *head;
        struct node *tail;
    public:
        linked_list() {
            head = nullptr;
            tail = nullptr;
        }

        void create(int key) {
            struct node *temp;
            temp = new struct node;
            temp->key = key;
            temp->next = nullptr;
            head = temp;
            tail = head;
        }


        void insert(int key) {
            if (key < head->key) {
                insert_beginning(key);
            }
            else if ((head->next == nullptr) || (key > tail->key)) {
                insert_end(key);
            }
            else {
                insert_middle(key);
            }
        }

        void insert_beginning(int key) {
            if (head->next == nullptr) {
                tail = head;
            }
            struct node *temp;
            temp = new struct node;
            temp->key = key;
            temp->next = head;
            head = temp;
        }

        void insert_end(int key) {
            struct node *temp;
            temp = new struct node;
            temp->key = key;
            temp->next = nullptr;
            if (head->next == nullptr) {
                head->next = temp;
                tail = temp;
            }
            else {
                tail->next = temp;
            }
            tail = temp;
        }


        void insert_middle(int key) {
            struct node *temp;
            temp = new struct node;
            temp->key = key;

            struct node *current = head;
            struct node *prev = current;

            while (current->key < temp->key) {
                prev = current;
                current = current->next;
            }
            prev->next = temp;
            temp->next = current;
        } 

        void delete_node(int key) {
            if (head == nullptr) {
                cout << "List is empty\n";
                return;
            }

            if (head->key == key) {
                if (head->next == nullptr) {
                    delete(head);
                    head = tail = nullptr;
                }
                struct node *temp = head;
                head = head->next;
                delete(temp);
            }
            else {
                struct node *current = head;
                struct node *prev = current;

                while ((current->key != key) && (current->next != nullptr)) {
                    prev = current;
                    current = current->next;
                }

                if ((current->key != key) && (current->next == nullptr)) {
                    cout << "Key not found\n";
                }
                else if ((current->key == key) && (current->next == nullptr)) {
                    tail = prev;
                    prev->next = nullptr;
                    delete(current);
                }
                else {
                    prev->next = current->next;
                    delete(current);
                }

            }
        }

        void search_node(int key) {
            if (head->key == key || tail->key == key) {
                cout << "Node found\n";
                return;
            }
            struct node *current = head;
            while ((current->key != key) && (current->next != nullptr)) {
                current = current->next;
            }

            if (current->key == key) {
                cout << "Node found\n";
            }
            else {
                cout << "Node not found\n";
            }
        }

        void print_nodes(void) {
            struct node *current = head;
            while (current != nullptr) {
                cout << current->key << '\n';
                current = current->next;
            }
        }
};


int main(void) {
    linked_list list;

    list.create(0);

    for (int i = 1; i < 20; ++i) {
        list.insert(i);
    }

    list.search_node(5);
    list.search_node(0);
    list.search_node(-1);

    list.delete_node(19);
    list.delete_node(0);

    list.print_nodes();

    return 0;
}
\$\endgroup\$

1 Answer 1

Reset to default
3
\$\begingroup\$

This is a pretty good start! The writing is very clear, and it's pretty easy to understand what's going on. I see a few things you could do differently.

Ease of Use

I notice that to use this class, a caller would need to instantiate a linked_list, call create() exactly once, and then call insert() repeatedly to insert the nodes. I think you're giving callers a lot of credit to think they'll remember all those steps each time. As it stands right now, if a caller accidentally calls create() twice, you'll leak memory! The node from the first call will be unhooked from the list, but not freed.

There are a few ways you could make this easier. You could either make a second constructor that takes a key and creates a new list with a single node in it. But an empty list can be useful, so I wouldn't make it the only constructor.

A better way would be to simply move the code from create() into insert() and add a condition around it. Something like this:

void insert(int key) {
    if (head == nullptr)
    {
        struct node *temp;
        temp = new struct node;
        temp->key = key;
        temp->next = nullptr;
        head = temp;
        tail = head;
    }
    else if (key < head->key)
    {
        // ... etc.

This way a caller can simply instantiate a linked_list and start inserting nodes.

Give Your Class Some Privacy

You've done the right thing by making head and tail private. That prevents a user of this class from messing them up. It seems like insert_beginning(), insert_middle(), and insert_end() should also be private since calling them from the outside could put an object in a bad state. For example, a user of the class could call insert_beginning() with a key that's greater than the key currently in head. But even better than that would be to simplify the logic for insertion as described in the next section.

Simplify

It's interesting that you have 3 different insertion methods. There's a special case for inserting at the head and inserting at the tail of the list. That could be an optimization in some cases, or it could be a performance hit doing a bunch of extra checking that isn't normally needed. Without profiling, it's hard to say for sure. But it does complicate the code. Personally, I think making the code more straightforward will have a bigger payoff, so I would suggest making a single insert() method that handles all the cases.

The insertion can be broken down into 2 steps: 1) find where to insert the node, 2) actually insert it and make all the links before and after work properly. I would do it something like this:

void insert(int key) {
    // Find the predecessor node
    struct node* prev = nullptr;
    struct node* curr = head;
    
    while ((curr != nullptr) && (key > curr->key))
    {
        prev = curr;
        curr = curr->next;
    }
    
    // Create the new node
    struct node* newNode = new struct node;
    newNode->key = key;
    newNode->next = nullptr;
    
    // Insertion
    if (curr == nullptr)
    {
        tail = newNode;
    }
    else
    {
        newNode->next = curr;
    }
    
    if (prev == nullptr)
    {
        head = newNode;
    }
    else
    {
        prev->next = newNode;
    }
}

You can use similar logic for search_node() and delete_node().

Errors

You have no destructor for this class, so it never gets cleaned up, leaking memory every time it's used. You really should add one.

Tests

It's great that you've written some code to test out your class. You should make a few more tests that test harder edge cases. For example, when writing the insert() method above, I ran it with your tests and it worked. Then I changed the test to generate 20 random numbers, and it started dropping a few. That's because my logic was bad in one spot, and if the key was less than the first node, the key would not get properly inserted. So a test for things out-of-order is important here!

\$\endgroup\$
2
  • \$\begingroup\$ Thanks. If I want to move the 3 insertions to private, I only have to copy paste them there, right? No other changes need to be done I believe. I had originally used rand() for testing but couldn't keep it since I can't use search or delete on numbers I don't know. \$\endgroup\$ Commented Nov 18, 2017 at 21:23
  • \$\begingroup\$ Yes, you only need to move those functions into the private section. (You can add as many private, public, or protected sections as you like. I've seen people do it for every single method. But I prefer just having 1 of each.) As for testing, it makes sense to do both - a sequential set where you can search for a specific node, and maybe another one with random values. (If you do go with random numbers, I recommend using a fixed random seed so the sequence is reproducible. Having tests that do something different on every run can lead to bugs.) \$\endgroup\$ Commented Nov 19, 2017 at 1:15

You must log in to answer this question.