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

Singly Linked Lists (SLL)

Explore the concept of singly linked lists in C#, focusing on the Node and LinkedList classes. Understand how nodes link unidirectionally through pointers and how the head pointer tracks the list's start to perform operations effectively.

We'll cover the following...

Introduction

A “linkedlist” is another data structure in C# formed by nodes that are linked together like a chain. Each node holds data along with the address to the next node in the list. The type of linked list where each node has one pointer that stores the reference to the next value. It is called a singly linked list (SLL). The following illustration shows a singly linked list.

As seen above, the absence of a backward pointer implies that there is a unidirectional 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 will discuss these classes one by one.

The Node class

The Node class has two components:

  • Data
  • Address

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 address refers you to the next node in the list. It is essential for connectivity.

Here is 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;  //Address to the next element
  Node(){
  //Constructor to initialize the nextElement of newly created Node
    nextElement=null;   
  }
}

Explanation: As 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 is defined above. To keep track of the list, you need a pointer to the first node in the list.

This is where the principle of the head pointer is relevant. The “head pointer” points to the beginning of the list. This means that for any operations on the list, you need to traverse it from the head (the start of the list) to reach your 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 = null;
  }
};

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