Introduction to Linked Lists in C# | CodeSignal Learn

Introduction to Linked Lists in C# | CodeSignal Learn

Introduction to Linked Lists

Hello there! Today, we will explore Linked Lists, a core data structure crucial for organized data management and establishing relationships between data. We will mark some essential milestones: an introduction to Linked Lists, their real-world applications, their implementation in C#, and the different operations you can perform on them. By the end of this lesson, you will be well-equipped to implement and operate Linked Lists using C# . Let's get started!

Understanding the Concept

A Linked List is a linear data structure similar to arrays. But, unlike arrays, they are not stored in contiguous memory locations. Each element in a Linked List is part of a node . A node comprises data and a reference (or link) to the next node in the sequence. This structure facilitates efficient insertions and deletions. The head is also an essential concept in Linked Lists. It is the first node in the list and serves as a reference to the entire list. The head is a null reference if the Linked List is empty. Singly linked lists come up quite often in coding interviews. Interviewers from tech giants, start-ups, and just about every company testing your coding abilities will pose challenges based on this concept. Here's another interesting point: While singly linked lists might not be extensively used in real-world applications, they form the foundational knowledge for understanding doubly linked lists, which are indeed quite common. A singly linked list contains nodes with a single link pointing to the next node, whereas a doubly linked list has nodes with links to both the next and the previous nodes.

Implementing Linked Lists - Creating Node

To begin implementing Linked Lists, we first need to understand the structure of a node, the building block of a Linked List. In C#, we'll create a class to serve as a blueprint for a node . A Node class mainly consists of data (the data you want to store) and next (the reference to the next node). In our case, we'll create a Node class to store integer data, with a constructor to initialize the node. C# class Node {public int Data; public Node Next; public Node(int data) {Data = data; Next = null;}} Fantastic! You now know how to set up a node in a Linked List.

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Implementing Linked Lists - Append Method

In this section, we'll learn how to add a new node at the end of our Linked List. We'll implement an Append method in our LinkedList class for this. class Node { public int Data; public Node Next; public Node(int data) { Data = data; Next = null; } } public class LinkedList { private Node _head; public void Append(int data) { Node node = new Node(data); if (_head == null) { _head = node; } else { Node last = _head; while (last.Next != null) { last = last.Next; } last.Next = node; } } } The code checks if _head is null, which would be the case for an empty list. If that's true, _head is set to the new node, meaning this new node is the first and only node in the list. If the linked list is not empty (_head is not null), the code enters a while loop, which runs as long as the Next attribute of the current node it's examining is not null (i.e., there are still nodes in the list). This loop is used to navigate to the end of the list. The new node is then appended after the last node in the list.

Implementing Linked Lists - AddFirst Method

Now, what if we want to add a new node at the beginning of our list? We'll write a method AddFirst to achieve this operation. public void AddFirst(int data) { Node node = new Node(data); if (_head != null) { node.Next = _head; } _head = node; } It simply reassigns the head.

Implementing Linked Lists - Delete Method

Removing a node from a Linked List is also an essential functionality. We will add a Delete method to our LinkedList class to remove a node with a particular data value. public void Delete(int data) { if (_head == null) return; if (_head.Data == data) { _head = _head.Next; return; } Node current = _head; while (current.Next != null) { if (current.Next.Data == data) { current.Next = current.Next.Next; return; } current = current.Next; } } We traverse the list like in the Append method, searching for a node with specific data. If found, it is removed from the list by retargeting the previous node to the node after the target.

C#

class Node
{
    public int Data;
    public Node Next;

    public Node(int data)
    {
        Data = data;
        Next = null;
    }
}

public class LinkedList
{
    private Node _head;

    public void Append(int data)
    {
        Node node = new Node(data);

        if (_head == null)
        {
            _head = node;
        }
        else
        {
            Node last = _head;
            while (last.Next != null)
            {
                last = last.Next;
            }
            last.Next = node;
        }
    }
}

C#

public void Delete(int data)
{
    if (_head == null) return;

    if (_head.Data == data)
    {
        _head = _head.Next;
        return;
    }

    Node current = _head;
    while (current.Next != null)
    {
        if (current.Next.Data == data)
        {
            current.Next = current.Next.Next;
            return;
        }
        current = current.Next;
    }
}