data structure

Linked list data structure for beginners

In this article, I am going to discuss about the Linked list data structure.

In my previous article of data structure series, I have described the list data structure.

The list is a simple data structure, but one major drawback is its time complexity during data insertion or deletion at any specific index. 

A list stores data in contiguous memory locations and because of that, insertion or deletion in a particular index requires shifting of its elements to the back and forth.

The linked list data structure overcomes this problem.

A linked list is a chain of elements, attached by pointer references.

Each of the elements in a linked list is called a node. Each node has two parts.

The first part carries the data, and the second part contains a pointer that points to the address of the next node.

Language preference

We can use any of the popular programming languages to create a linked list. I am using C++ for the examples in this article.

Code for a sample linked list node in C++

We are going to use a C++ structure to create a node. To know more about C++ structures, please visit here.

The code is below.

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

In the above example, I have created a struct named node. The struct has an integer variable named data and a pointer of type node named next. 

The complete code is as below.

#include <iostream>

using namespace std;

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

class linked_list {
    private:
        node *head, *tail;
    public:
        linked_list() {
            head = NULL;
            tail = NULL;
        }
};

int main()
{
    linked_list l;
    return 0;
}

In the above code, there are two pointers named head and tail. As the names describe the head pointer will point to a linked list’s first node, and the tail pointer will indicate the last node of the linked list.

Linked list node pointing to another node

Add a node in a linked list data structure

Adding a node has two steps. At first, we have to create the node and assign that node to a temporary variable. Then, we have to 

make the last node of the present linked list to point the newly created node and make the tail pointer to indicate the new node.

Please see the below code to understand the complete process.

/* I have created a public function that takes a single parameter */

add_new(int num) {

 node *temp = new node;
 temp->data = num;
 temp->next = NULL;

 if ( head == NULL ) {
      head = temp;
      tail = temp;
 } else {
      tail->next = temp;
      tail = tail->next;
    } 
}

/* We have to write below code in the main section to add node */

int main()
{
    linked_list l;
    l.add_new(3);
    l.add_new(5);
    return 0;
}

Let me describe the tricky part of the add_new() function. 

    if ( head == NULL ) {
        head = temp;
        tail = temp;
    } 

To add a new node, we have to check if the linked list is empty or not.

In the if condition, we are checking if the head pointer is NULL. Because it can be null only if the linked list has no element.

So if it is null, then we will point both the head and tail pointers to the newly created node, which would be the first node in the linked list.

else {
        tail->next = temp;
        tail = tail->next;
}

In the else section, we are pointing the present tail’s next pointer to the newly created node. This way the new node gets linked to the linked list.

After that, we are pointing the tail pointer to the newly created node. The tail pointer indicates the last node of the linked list.

The complexity of adding a node at the end of a linked list is always a constant O(1).

Add a node in the front of a linked list

To add a node in front of a linked list, we need to manipulate the head pointer.

The code is below.

add_in_front(int num) {
    node *temp = new node;
    temp->data = num;
    temp->next = NULL;
    if ( head == NULL ) {
        head = temp;
        tail = temp;
    } else {
        temp->next = head;
        head = temp;
    }    
}

Here, we have to check two conditions. First, if the linked list is empty, then the new element will be the first node and both head and tail will point to the same node. Same we are checking in the if condition.

If the list is not empty then, the next pointer of the temporary node will point to the head pointer or the beginning of the linked list. And then, the head pointer will indicate to the newly added node.

Remove a node from the beginning of a linked list data structure

To remove a node from the beginning of a linked list, first, we have to check if our linked list is empty or not.

If the list is empty, then we won’t perform any operation. But if the list is not empty, then we have to point the head pointer to the next node and free up the space of the first node. 

The code is below.

int remove_from_beginning() {

 node *temp;
 if (head == NULL) {
     return 0;
 } else {
     temp = head;
     if ( temp->next != NULL) {
         head = temp->next;
     } else {
         head = NULL;
         tail = NULL;
     }
     delete temp;
 }
}

The time complexity of removing a node from the beginning is O(1).

Remove a node from the end of a linked list

To remove a node from the end of a list, we have to check if the link is not empty. Or, if the linked list has a single item or not.

After performing these checks if we find that the linked list has multiple nodes then, we have to iterate through the list till we reach the end. And also, we have to keep track of the previous node, because we can not track the previous node from the next node.

The code is below.

int remove_from_end() {

 node *ptr, *prev;
 ptr = head;

 if ( head == NULL ) {
     return 0;
 } else {
     if ( ptr->next == NULL ) {
         head = null;
         tail = null;
         delete prt;
         return 0;
      }
 }

 while( ptr->next != NULL ) {
     prev = ptr;
     ptr = ptr->next;
 }

 tail = prev;
 delete ptr;
 return 0;
}

Enumerate a linked list

while( ptr->next != NULL ) {
    ptr = ptr->next;
}

Leave a Comment

seven + three =