JIYIK CN >

A linked list is a linear data structure. It is a collection of objects defined as nodes. But in a linked list, the nodes are stored in random locations in the memory and not in consecutive locations.

A node in a linked list consists of:

• Data item.

• The address of the next node.

class Node
{
    int data;
    Node *next;
};

This representation of the node is used to create each node in the list. The data field stores the element, while *nextis a pointer that stores the address of the next node.

The address of the first node is called the head, and the address of the last node is called the tail. The last node in a linked list points to the NULL. Therefore, when the list is empty, the head node points to NULLthe . Linked lists do not require a prior declaration of size and can be increased in size dynamically. Inserting and deleting elements in a linked list is very easy. We do not need to move all the elements; it is enough to just change the pointers of the previous and next elements.

Linked Lists vs Arrays

Linked lists have a natural advantage over arrays because we don’t have to allocate a lot of memory upfront, but since the memory is not allocated contiguously, linked lists are not cache-friendly. They allow easy insertion and removal of elements with the help of pointers, but the storage space for each node is also doubled due to the space required for pointers. Linked lists also do not provide random access to elements. So, it is clear that there is no single winner, and both linked lists and arrays have their own pros and cons.

Arrays should be used when we have a small list and know the maximum number of elements we may store, whereas linked lists should be used when there is a large list that changes regularly.

Linked list traversal algorithm

Let headbe the first node of the linked list.

• Initializes a pointer headto a node in a linked list curr.
• While currhas not yet reached the end of the list, i.e. curr! = NULL, do the following:
  • Prints the data stored in the current node.
  • curr=curr->next;

Linked list traversal diagram

• Initializes heada pointer to the node currwith data value equal to 2. Prints the value 2.

• Move the pointer currto the next node with value 4. Print the value 4.

• Move the pointer currto the next node with value 6. Print the value 6.

• Move the pointer currto the next node with value 8. Print the value 8.

• Move the pointer currto the next node whose value is equal to NULL. whileThe loop termination condition is reached. Therefore, we have visited all the nodes.

Linked list traversal implementation

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

class Node {
public:
    int data;
    Node* next;
    Node(int x) {
        this->data = x;
        this->next = NULL;
    }
};

void printList(Node* head)
{
    Node*curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
}

int main()
{
    Node* head = new Node(1);
    head -> next = new Node(2);
    head -> next-> next = new Node(3);
    head -> next-> next-> next = new Node(4);
    head -> next-> next-> next-> next = new Node(5);
    head -> next-> next-> next-> next-> next = new Node(6);
    printList(head);
    return 0;
}

Linked list traversal algorithm complexity

Time Complexity

• Average situation

To traverse the complete linked list, we have to visit every node. Therefore, if a linked list has nnodes, the average case time complexity of traversal is about O(n). The time complexity is about O(n).

• Best Case

The time complexity of the best case is O(n). It is the same as the time complexity of the average case.

• Worst case scenario

The worst case time complexity is O(n). It is the same as the best case time complexity.

Space complexity

The space complexity of this traversal algorithm is O(1), since currno additional space is required except for the pointer.