Data Structures

Introduction

A linked list is a collection of nodes and is a linear data structure. The elements are not stored in contiguous memory locations. Each node has a single descendant. There is no memory wastage as we can create and delete nodes at the run time.

In a singly linked list, each node points to its next node. A node consists of two things:

Data (integer, character, boolean, etc.)
Pointer to the next node

The below figure demonstrates a singly linked list:

The last node points to NULL. The first node of the linked list is the head and the last node is the tail.

Creating a Linked List

Let us now learn how to create a singly linked list in C++.

Let us begin by creating a node as follows:

#include <iostream>
using namespace std;

class Node{
  public:
  //Node has two things:
  int data;     //1. data
  Node* next;   //2. Pointer to the next node

  //creating a constructor
  Node(int data){
    this->data = data;
    this->next = NULL;
  }
};

int main() {
  return 0;
}

Now, a collection of such nodes will give us a linked list as follows:

#include <iostream>
using namespace std;

class Node{
  public:
  //Node has two things:
  int data;     //1. data
  Node* next;   //2. Pointer to the next node

  //creating a constructor
  Node(int data){
    this->data = data;
    this->next = NULL;
  }
};

int main() {
  //creating nodes dynamically
  Node* first = new Node(10);  //This creates a node with data 10 and pointing to null
  Node* second = new Node(20);
  Node* third = new Node(30);

  //linking nodes to form a linked list
  first->next = second;
  second->next = third;
  return 0;
}

Now, let us do some basic questions to understand linked lists better.

Question-1

Print all the elements of a linked list.

Approach: We will make a temp node, equal to the head of the linked list. We traverse till the temp node becomes equal to null. While traversing, we print the data of the current node.

Note: To move to the next node, we do temp = temp->next. temp++ will not work here as nodes are not contiguous memory locations.

Tip: Always copy the head node in a temp node and then perform operations on temp. Do not perform operations directly on the head of the linked list. This will ensure that we keep track of the original linked list.

Dry Run:

temp = temp->next

Code:

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

Question-2

Find the length of a linked list.

Approach: We copy the head of the linked list in a temp node. We run a loop till the temp is not equal to NULL. We also initialize a length variable with zero. Each time we move the temp node, we increment the length variable by one.

Try doing the dry run of the code on your own!

Code:

int lengthOfLinkedList(Node* head){
  Node* temp = head;
  int length = 0;
  while(temp != NULL){
    length++;
    temp = temp->next;
  }
  return length;
}

I hope you can understand the basics of nodes and linked lists through this article. The two questions discussed here will teach you how to access each node of a linked list.

See you soon in the next blog post!

Introduction to Singly Linked List

Table of contents

Introduction

Creating a Linked List

Question-1

Question-2