Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C++

Singly Linked Lists (SLL)

Explore the fundamentals of singly linked lists in C++, focusing on the node and linked list classes. Understand how nodes connect via pointers and how the head pointer manages the list's start. This lesson prepares you to implement singly linked lists and grasp their core operations, crucial for coding interviews.

We'll cover the following...

Introduction

A Linked-list is another data structure in C++ formed by nodes that are linked together like a chain. Each node holds data, along with a pointer to the next node in the list. The type of linked list where each node has only one pointer that stores the reference to the next value is called Singly Linked List (SLL). The following illustration shows a Singly Linked List.

As you can see, the absence of a backward pointer implies that there is a uni-directional link, i.e., the whole list points in one direction and cannot point backward. This is why it is called a singly linked list.

Do not worry if you feel slightly lost at this point. For now, you only need to concern yourself with the two classes required to implement a singly linked list:

  • The Node Class
  • The LinkedList Class

We’ll discuss these, one by one.

The Node Class

The Node class has two components:

  • Data
  • Pointer

Data is the value you want to store in the node. Think of it as the value at a specific index in a list. The data type can range from string or integer to a custom class.

The pointer refers us to the next Node in the list. It is essential for connectivity.

Here’s a typical definition of a Node class that stores integers:

C++
class Node {
public: 
  int data; //Data to store (could be int,string,object etc)
  Node* nextElement;  //Pointer to next element
  Node(){
  //Constructor to initialize nextElement of newly created Node
    nextElement=nullptr;   
  }
};

Explanation: As we discussed, the Node class has two variables. data contains your specified value and nextElement is the pointer to the next element of the list.

The LinkedList Class

The linked list itself is a collection of Node objects which we defined above. To keep track of the list, we need a pointer to the first Node in the list.

This is where the principle of the head pointer comes in. The head pointer points to the beginning of the list. This means that for any operations on the list, we need to traverse it from the head (the start of the list) to reach our desired list Node.

The implementation of the LinkedList class is shown below:

C++
class LinkedList {
public:
  Node* head;  // pointing to start of the list
  LinkedList(){
    head = nullptr;
  }
};

Explanation: The implementation is fairly simple. Initially, the linked list is empty, i.e., it does not contain any node. The head pointer has NULL value, i.e., the head pointer does not point to anything.

Next, we’ll look at all the functions which are present in a standard LinkedList class.