C++ Linked List

Howdy, this blog post should explain what a linked list is and provide a Github link to my implementation of a linked list.

Definition

What is a linked list? It basically is a list of nodes, each node contains data(In my case a int32_t) and a pointer to the next node. Thanks to Wikipedia here is a visualization of what I mean
I also want to mention that the data which a node contains can be anything you wish. In my example I used a int because it is the quickest, additionally if you use for example a object as data, then you have to add the

bool operator==(const Object& other) const
{
    return (importantVariable == other.importantVariable) && (moreImportantVariable == other.moreImportantVariable);
}

As already mentioned a linked list works with pointers to the next object (singly linked list), this means a linked list is not layed out in a continues block of memory but it is scattered across the memory unlike arrays which indeed live in a continues block of memory. This also means that the size of a linked list is variable and can be changed during runtime unlike a array.

Operations

The linked list starts with the head and grows in direction of the end. The head is always our starting point.

Add a node to the end
1. We cann add elements to the end of our linked list. In order to do so we have to start from the head of our linked list and iterate over it untill we hit the last node which will be indicated if the next element is a nullptr. Based on that description we can see that the Big O to add a Node to the end of the list is n.
2. Example:
```
void insertNodeAtEnd( int32_t value )
{
      Node* currNode = this;

      // We iterate over the list to find the last node
      while ( currNode->next != nullptr )
      {
          currNode = currNode->next;
      }

      // At this point we reached the end
      Node* newNode  = new Node( value );
      currNode->next = newNode;
}
```

Add a node to the beginning(new head)

In order to add a node to the beginning we simply create a new node and let it point to the old head. Which gives us the Big O of 1.
Example:

Node* insertNodeAtHead( int32_t value )
{
     // We know that we have to add the new node at the beginning
     // We just need to adjust the next element of the new node to point to
     // the last head
     Node* newNode = new Node( value );
     newNode->next = this;

     return newNode;
}

Delete a node
1. Deleting a node simply means first of all to iterate over the list and find the specific node we want to delete. If we find that node we have to make sure that the previous node points to the node after the deleted one.
  1. Initial situation: prevNode --> NodeToBeDeleted --> nextNode
  2. Final situation: prevNode --> nextNode we just changed the pointer to point to the nextNode
2. Example: The code bellow also checks if the head is going to be deleted then we simply return a new head.
```
    Node* deleteNode( int32_t value )
    {
        // If the head node contains the value we want to delete
        if ( data == value )
        {
            Node* newHead = next;
            delete this;
            return newHead;
        }

        Node* currNode = this;

        while ( currNode->next != nullptr )
        {
            if ( currNode->next->data == value )
            {
                // We save the address of the node which is to be deleted in tmp
                Node* tmp = currNode->next;

                // We adjust the next of the current node pointing to the node
                // after the to be deleted one Basically we just skip the node
                // in between
                currNode->next = currNode->next->next;
                delete tmp;
                return this;
            }

            currNode = currNode->next;
        }

        return this;
    }
```
1. Short comparison to a vector: In a vector, elements are stored in a contiguous block of memory. When you delete a value from the middle of a vector, all elements to the right of the deleted element need to be shifted by one position to fill the gap. This involves copying and moving data, which can be an expensive operation, especially for large vectors. The time complexity for such an operation is O(n), where 'n' is the number of elements in the vector. In other words, it can take more time as the vector grows larger.
  In a Linked List elements (nodes) are not stored in contiguous memory locations; instead, each node contains a reference (pointer) to the next node. When you delete a value from the middle of a linked list, you only need to update the pointers to skip the node to be deleted. This operation involves changing a few references, and it doesn't require shifting the remaining elements. As a result, the time complexity for deleting a node in a linked list is typically O(1) if you have a reference to the node to be deleted. This means the operation takes roughly the same amount of time, regardless of the size of the linked list.
  So to summarize is, a vector needs to shift its elements if we delete somewhere except the end, a linked list only needs to change some pointers. But the trade-off is that, a linked list does not provide random access, we always have to iterate over the whole list to find our node.

This are the most important functions. The other functions I included in my code basically all work the same. Iterating and checking if next != nullptr.

Possible Interview Questions

I will add implementation and description of it later maybe.

Reverse a linked list
Detect loop in a linked list

Return Nth node from the end in a linked list

I solved this with two versions I think both of them are used in many sources.

The first version simply takes the size of the linked list and subtracts the nth number lets call the result resIndex. After that we just call resIndex times the ->next node.

// The 0th element would be the end
Node* getNthNodeFromEnd( int32_t n )
{
  int32_t listLen = getSize();
  if ( n > listLen )
  {
      std::cout << "N larger than size of linked list\n";
      return nullptr;
  }

  int32_t nthElement = listLen - n;
  Node*   currNode   = this;
  // Starting at one because we are at the head alrady
  for ( int32_t i = 1; i < nthElement; ++i )
  {
      currNode = currNode->next;
  }

  return currNode;
}

The second solution is more interesting it includes two pointers a lazy one and a not so lazy one.
The idea is start from head and let the runner call n times ->next after that we simply move both pointers untill the runner->next is a nullptr.

Node* getNthNodeFromEndDoublePointer( int32_t n )
{
 if( n > getSize() )
 {
     std::cout << "N larger than size of linked list" << std::endl;
     return nullptr;
 }

 Node* lazy = this;
 Node* runner = lazy;
 for( int32_t i = 0; i < n; ++i )
 {
     runner = runner->next;
 }

 while( runner->next != nullptr )
 {
     runner = runner->next;
     lazy = lazy->next;
 }

 return lazy;
}

Remove duplicates from a linked list

Resources

Link to code GitHub. The github link contains the code of my implementation of a linked list, it should cover the basics.
Linked List Image Wikipedia.
Possible Interview questions FreeCodeCamp.