Single linked list with C++

A linked list can be imagined with a sequence of something. In our case, let's think of it as integers. So, if I for example have a list of 6 integers being 12, 8, 3, 2, 6 and 38 we could represent the linked list as.

Where the blue boxes are nodes. These nodes can be represented individually as.

A little notice here is that Data refers to something that is stored, in this case an integer. While the pointer is a reference to something that comes next. In other words, our node right here is an object that has two sections. One for Data and the other for the pointer. The C++ code for this could be.

struct node {

       node(int x, node* y) : data(x), next(y){}

       int data;

       node* next;

};

In this case, the constructor takes in a integer variable x and a node pointer y. x is set equal to data, while the node pointer next is set to y. When it comes to the C++ code for the linked list we can start out a class called LinkedList. This class will use the node structure.

class LinkedList {

public:

       LinkedList() {

             head = nullptr;

             size = 0;

       }

       void add_front(int x) {

             node* new_node = new node(x, head);

             head = new_node;

             size++;

       }

       void get_front() {

             std::cout << head->data << std::endl;

       }

private:

       node* head;

       int size;

};

This class has 2 variables in private and 3 functions in public. We can first see the constructor LinkedList() that sets head equal to nullptr and the size to 0. This is because the constructor will be the first thing called when we take the class in use. Which is also when we want to start a new linked list. From there we can see the function add_front(), which takes in an integer as the parameter. It then goes on to construct a new pointer called new_node that sends the integer and head to the struct we made for nodes.

This because we're creating a new node with the values we sent through add_front(). Let's imagine that we sent the integer 5 through the function. Our node will then look like.

Also, size increases with 1 for everytime we use the function add_front(). Anyhow, head was originally set equal to nullptr through the constructor. But, now that we ran the add_function() we also sat head equal to the new node we created, called new_node. Which means that the new node with data = 5 is now the head. The function get_front() will print out the head node, through the access of the data variable.

Furthermore, we will need more functions for our single linked list. For example, we can add in functions such as is_empty() to check if the list is empty.

bool is_empty() {

       return(head == nullptr ? true : false);

}

This one is pretty straight forward. Inside the function we'll be returning a boolean value, either true or false. This could be read as "If head equals nullptr (Doesn't point to something), then it's true. Else, it'll be false".

In order to delete any nodes from the list we can add a new function that we'll call remove_front(). Inside this function we'll take on the concept of making a temporarily node called old that we set equal to head, then head will be set equal to old->next. Lastly, we'll delete old.

void remove_front() {

       if (is_empty()) {

             std::cout << "List is empty! Can't delete anything" << std::endl;

       }

       else {

             node* old = head;

             head = old->next;

             delete old;

             size--;

       }

}
Here we can also see that the is_empty() function is used within our remove_front() function, in order to check if the list is empty or not.

Lastly, we can make a get_size() function that'll return the size of the list.

void get_size() {

       std::cout << "Size of the list is: " << size << std::endl;

}

Now that we have a complete program we'll be able to run it with several function in int main().

int main(){

       LinkedList list;

       list.add_front(5); // Adds 5

       list.add_front(6); // Adds 6

       list.add_front(8); // Adds 8

       list.get_front(); // This one will display 8

       list.remove_front(); // Deleting 8

       list.get_front(); // 6 is front

       list.get_size(); // The size is 2

       return 0;

}

This can visually be seen as.

After deleting the front.

There's also an possibility to change the logic from FIFO to LIFO (Last in, First out), by changing the logic of the nodes from being next till previous.