Implementation of singly linked list in C/C++

What is a Linked List ?

In simple words linked list is a list of elements. Each element has some memory address and hence we can also say it is a list of addresses. We can insert new element in a linked list in constant O(1) time either at the start of the list or at the end of the list based on our requirement. But accessing an element in linked list takes O(N) time in worst case where N is the size of the linked list whereas accessing an element in an array just takes O(1) time since array has sequential memory addresses.

How to code ?

Lets represent each element in our list as a Node. Each node in the list has 2 components one is data and other is a pointer to the next node. We can create the node as follows. Lets assume we are going to create the list of integers, so each node contains integer data and pointer to the next node.

struct Node 
{
    int data;
    struct Node *next;
};
typedef struct Node Node;

Now we create a class LinkedList as below.

class LinkedList
{
private:
    Node* head;
    Node* createNewNode(int data);
public:
    LinkedList();
    ~LinkedList();
    void insert(int data);
    int getElementAt(int index);
};

In the above code we have created a class LinkedList with member variable head. This 'head' always points to the start node in the list. We have just declared constructor, destructor, insert() and getElementAt() methods. Now we are going to implement all of these below.

LinkedList::LinkedList() // constructor
{
    // Initializing the head pointer to NULL
    head = NULL;
}

Node* LinkedList::createNewNode(int data) // this is a helper function
{
    // This method allocates memory for new Node and stores the data and returns the address of newNode
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void LinkedList::insert(int data)
{
    Node* newNode = createNewNode(data);
    if(head == NULL)
    {
        head = newNode;
        return;
    }

    // this implementation inserts the new node at the beginning of the list, it takes constant time
    newNode->next = head;
    head = newNode; // make newNode as head
}

In the above code snippet, in the constructor we have initialized the head to NULL i.e. when LinkedList object is created the head pointer will be set to NULL which means the list is empty initially. 
New elements can be added to the linked list by calling insert(int data) method. The responsibility of this method is to create new node and store the new element data in that and then rearrange the head pointer. This implementation always inserts the new element at the beginning of the list which is taking constant time for insertion. If your requirement is to insert the new element at the end of the list, one approach is each time start at the head and traverse the list till the end and then insert the new element at the end but this approach is not efficient as it takes O(N) time for insertion. The better approach would be to maintain another pointer called tail which always points to the last element and inserts the new element as next element of tail and update the tail to the new node [Try it yourself]. 

Now we will see how to retrieve the element at some given index.

int LinkedList::getElementAt(int index) // index ranges from 0 to N-1 (N is the size of the list)
{
    int i = 0;
    Node* temp = head;
    while(i <= index && temp != NULL)
    {
        i++;
        temp = temp->next;
    }
    if(temp == NULL)
    {
        printf("Given index is greater than the size of the list\n");
        return -1; // return some error
    }
    return temp->data;
}

In the above code getElementAt(int index) method returns the index th element in the list. In this logic we have created a temp pointer and assigned head to it and then traversed the list till we reach index th element or end of the list whichever comes earlier. Here we are traversing the list through temp pointer (without changing head) in order to preserve the state of head as it is. The time complexity is O(N) where as in case of arrays you can access the any element in just constant O(1) time. 

Lets implement destructor. We need to deallocate all the nodes in the list for emptying the linked list.

LinkedList::~LinkedList()
{
    if(head == NULL)
        return;

    Node* temp = head;
    Node* next;
    while(temp != NULL)
    {
        next = temp->next;
        delete temp; // deallocate
        temp = next;
    }
}

The destructor traverses the list and frees the memory one by one. 
NOTE: Lets say you are writing a helper method to empty the list, the same destructor code can be written but at the end you should assign the head pointer to NULL as head = NULL, otherwise the program may give segmentation fault when you try to insert or access elements of list after emptying the list because the head will become dangling pointer.

Now lets write some code to use the above LinkedList class by inserting some elements into the list.

int main()
{
    LinkedList ll;// constructor is called here

    ll.insert(20);
    ll.insert(45);
    ll.insert(48);
    ll.insert(28);

    printf("Element at index 2 is %d\n", ll.getElementAt(2));
   
    return 0;
}

As per the above code the linked list contains elements in the following order.
28  48  45  20
And the element at index 2 is 45.

That's it. Cheers :)