Till now, we have covered a lot of basic data structures like Arrays, Strings, Stacks, and Queues. Now, it is time to move to a bit more complex Data Structure. Linked Lists is like the gateway to start learning about a bit more advanced data structures.

In the following article, we will have a look at What are Linked Lists, how is it different from an array, its basic syntax, and its time-complexities. So, let's get started.

Introduction

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

As you can see, in a single node there are two divisions. The first part stores the data and the second part stores a pointer. The pointer contains address of the next node. You must wonder what is a node and how do you create one? Well, This is how you do it.

class Node {                
public:
    int data;              // stores the data in the node
    Node* next;       // a pointer called as next that points to an object of data type Node. 
};

Class is a whole big concept within itself. For now, our focus must not be on class but on what we are doing inside it. For now, you can think of a class as a concept that is used to create user defined data types.

Syntax and Basic Functions

Node is a custom data type that we need to implement a linked list. As we can see in the above code, our node consists all the things that we need, an integer and a pointer. Now that we have our node. Let's have a look at the different functions like adding, searching and deleting data from the nodes.

Let's create 3 nodes and assign it some data.

Node *first = new Node();
first->data = 1;

Node *second = new Node();
second->data = 2;

Node *third = new Node();
third->data = 3;

first->next = second;   // the first node will point to the second node.
second->next = third;  // the second node will point to the third node.
third->next = NULL;    // the third node is the last node so it points to nothing.

Next, let's have a look at how we can traverse a Linked List. This is where pointers come in use.

Since we know, our first node is called as first. We will use a temporary Node which will traverse the whole Linked List like this.

Node *temp = first;    // points to the start of the list.
while(temp!=NULL)   // while loop runs till we reach the end of the list
{
  // Time Complexity of Traverse: O(N)
   cout<<temp->data<<" ";
   temp=temp->next;   // temp points to the next object in the list.
}

The time complexity to traverse the Linked List would be O(N). N is the number of nodes in the list.

Next up, let's have a look at how we can insert nodes in the list. In the first code snippet, we just created an object and assigned a value to it. What if we wanted to push a new value in the list. So there are 3 ways to do it.

1) Insert in the front

2) Insert in the middle

3) Insert in the end

Talking about DSA and problem solving, we never implement Linked Lists from scratch. We just use a vector<> and use all its functions like insertion and deletion. Vectors are internally implementd as a doubly linked list. Out of the above 3 functions, we majorly use the 3rd function and that is the push_back function.

Suppose, the vector is implemented as a single linked list internally, then the vector.push_back() function would be implemented in the following manner.

void push_back(Node** head, int val)  // pass a pointer to the head node and the value we want to insert in the list
{
   //  Time Complexity of Insert: O(N)
   Node* temp = new Node();  // create the new node
   temp->data = val;   // assigning data 
   temp->next=NULL;  // since we are inserting in the end, our new node will point to a null value
   Node* traverser = *head;  // use this pointer to reach the last node of current list
   while(traverser->next!=NULL)
   {
        traverser=traverser->next;   
   }
   traverser->next=temp;   // make the next pointer of the current node point to the newly created node. 
   return;
}

The next function that we would look at is accessing an element in the Linked List. The accessing element operation is a bit costly in the Linked Lists because we don't have [] operator to access an element by its index. We need to traverse the whole list and find out. Here is a code on how we can do it.

bool getElement(int val, Node* head) { // Time Complexity of Search: O(N)

Node traverser = head; // use this pointer to reach the end of current list while(traverser!=NULL) // untill we reach the end { if(traverser->data==val)return true; // return true if we have found the value traverser=traverser->next;
} return false; // return false otherwise. }

Linked List Vs Arrays

Linked Lists and Arrays are somewhar similar and somewhat different from each other. Let's have a look at the advantages and disadvantages of Linked Lists over Arrays.

• Advantages

  1. Dynamic size
  2. Ease of insertion/deletion

• Disadvantages

  1. Random access is not allowed. We have to access elements sequentially.
  2. Extra memory space for a pointer is required with each element of the list.
  3. Arrays have better cache locality that can make a pretty big difference in performance.
  4. It takes a lot of time in traversing and changing the pointers.
  5. It will be confusing when we work with pointers.

Code

Here is the complete code of all the functions that we have discussed till now.

#include<bits/stdc++.h>
using namespace std;

class Node {                
public:
    int data;              // stores the data in the node
    Node* next;       // a pointer called as next that points to an object of data type Node. 
};

void push_back(Node** head, int val)  // pass a pointer to the head node and the value we want to insert in the list
{
   //  Time Complexity of Insert: O(N)
   Node* temp = new Node();  // create the new node
   temp->data = val;   // assigning data 
   temp->next=NULL;  // since we are inserting in the end, our new node will point to a null value
   Node* traverser = *head;  // use this pointer to reach the last node of current list
   while(traverser->next!=NULL)
   {
        traverser=traverser->next;   
   }
   traverser->next=temp;   // make the next pointer of the current node point to the newly created node. 
   return;
}

bool getElement(int val, Node* head)
{
   //  Time Complexity of Search: O(N)

   Node* traverser = head;  // use this pointer to reach the end of current list
   while(traverser!=NULL)   // untill we reach the end
   {
        if(traverser->data==val)return true;  // return true if we have found the value
        traverser=traverser->next;   
   }
return false;   // return false otherwise.
} 

int main()
{
    Node *first = new Node();
    first->data = 1;

    Node *second = new Node();
    second->data = 2;

    Node *third = new Node();
    third->data = 3;

    first->next = second;   // the first node will point to the second node.
    second->next = third;  // the second node will point to the third node.
    third->next = NULL;   // the third node is the last node so it points to nothing.

    Node *temp = first;    // points to the start of the list.
    while(temp!=NULL)   // while loop runs till we reach the end of the list
    {
  // Time Complexity of Traverse: O(N)
        cout<<temp->data<<" ";
        temp=temp->next;  // temp points to the next object in the list.
    }  
    push_back(&first,5);

    bool x = getElement(2,first);
}

Different Types of Linked Lists.

As our current node stands, we are using an integer and a pointer to store the address of the next node. Since we are pointing to a single Node which is ahead of us, we call this as a Singly Linked List

There are 2 more types of Linked Lists. Doubly Linked Lists and Circular Linked Lists.

As the name suggests, in a doubly linked list the node has three data members. One to store the data, the second is a pointer to the next node, and the third is a pointer to the previous node. The class Node would look something like this for a doubly linked list.

class Node {                
public:
    int data;              // stores the data in the node
    Node* next;       // a pointer called as next that points to an object of data type Node
   Node* prev;
};

A circular linked list is a list where the last node of the list points to the head of the list. So it creates a circle. Something like this

Conclusion

So this concludes our article on Basics of Linked List. We have covered the topics that are necessary for you to get a basic understanding of this data structure. We looked into insertion, searching, and traversal of a linked list. We also saw the difference between arrays and Linked lists.

I encourage you to go on your IDE and create a singly linked list from scratch. This will boost up your confidence in using pointers. If you are a beginner struggling with pointers, then do check this out.