What is Linked List | DSA in C++ - Software Development PDF Download

Introduction

When it comes to data structures, a linked list is a fundamental and widely used one. It is a linear data structure that consists of a sequence of elements, where each element contains a reference (or link) to the next element in the sequence. In this article, we'll explore linked lists in C++, discussing their implementation, operations, and providing examples to help you understand their functionality.

Implementing a Linked List

A linked list is composed of nodes, and each node contains two components: data and a pointer/reference to the next node. In C++, we can create a linked list using a class to represent the nodes and maintain the links between them.

Let's define our Node class:

class Node {

public:

    int data;

    Node* next;

};

The 'data' member represents the value stored in the node, and the 'next' pointer points to the next node in the list.

Creating a Linked List

To create a linked list, we need to manipulate the nodes and their links. We start by creating the first node, called the head, and assigning it a value. The head node serves as the starting point of the list. Here's an example of creating a linked list with three nodes:

Node* head = nullptr;

// Create the first node

head = new Node();

head->data = 1;

head->next = nullptr;

// Create the second node

Node* second = new Node();

second->data = 2;

second->next = nullptr;

head->next = second;

// Create the third node

Node* third = new Node();

third->data = 3;

third->next = nullptr;

second->next = third;

In this example, we created three nodes and linked them together by assigning the 'next' pointers accordingly. The resulting linked list would be: '1 -> 2 -> 3 -> nullptr'.

Traversing a Linked List

To access the elements of a linked list, we need to traverse it by following the links between nodes. Starting from the head node, we can iterate through the list until we reach the end (i.e., a node whose 'next' pointer is 'nullptr').
Here's an example of traversing a linked list and printing its elements:

Node* current = head;

while (current != nullptr) {

    cout << current->data << " ";

    current = current->next;

}

This code snippet prints the data value of each node in the linked list. In our example, the output would be: '1 2 3'.

Linked List Operations

Linked lists support various operations, including insertion, deletion, searching, and updating elements. Let's explore these operations through examples:

Insertion

To insert a new node at the beginning of the linked list, we need to create a new node, assign the desired value, and update the 'next' pointer to point to the current head node.

// Create a new node

Node* newNode = new Node();

newNode->data = 0;

// Update pointers

newNode->next = head;

head = newNode;

After inserting the new node, the linked list becomes: '0 -> 1 -> 2 -> 3'.

Deletion

To delete a node from a linked list, we need to update the links to bypass the node we want to remove. We also need to ensure memory deallocation to prevent memory leaks.

Let's say we want to delete the second node:

Node* temp = head->next;

head->next = temp->next;

delete temp;

After deleting the second node, the linked list becomes: '0 -> 2 -> 3'.

Searching

To search for a specific value in a linked list, we can iterate through the list and compare each node's data with the target value.

int target = 2;

Node* current = head;

while (current != nullptr) {

    if (current->data == target) {

        cout << "Found";

        break;

    }

    current = current->next;

}

if (current == nullptr) {

    cout << "Not found";

}

In this example, the output would be "Found" since the value 2 exists in the linked list.

Updating

To update the value of a node in a linked list, we need to find the node and modify its 'data' member.

int oldValue = 2;

int newValue = 4;

Node* current = head;

while (current != nullptr) {

    if (current->data == oldValue) {

        current->data = newValue;

        break;

    }

    current = current->next;

}

After updating the value from 2 to 4, the linked list becomes: '0 -> 4 -> 3'.

Sample Problems

Now let's solve a few sample problems to reinforce our understanding of linked lists:

Problem 1: Count the number of nodes in a linked list

int countNodes(Node* head) {

    int count = 0;

    Node* current = head;

    while (current != nullptr) {

        count++;

        current = current->next;

    }

    return count;

}

Problem 2: Check if a linked list contains a cycle

bool hasCycle(Node* head) {

    Node* slow = head;

    Node* fast = head;

    while (fast != nullptr && fast->next != nullptr) {

        slow = slow->next;

        fast = fast->next->next;

        if (slow == fast) {

            return true;

        }

    }

    return false;

}

Conclusion

Linked lists are powerful data structures that allow efficient dynamic memory allocation and flexible manipulation of data. In this article, we covered the basics of implementing and operating on linked lists in C++. By understanding the concepts and examples provided, you should now have a solid foundation to start using linked lists in your programs.