Let’s Linked List in case you get asked about it during a coding interview.

What is a Linked List?

A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a reference to the next node in the list. The first node is called the head, and the last node is called the tail. Linked lists can be used to implement various data structures, such as stacks, queues, and hash tables.

Creating a Linked List in C#

To create a linked list in C#, we’ll define a LinkedList class that contains a reference to the head node. We’ll also define a Node class that contains the value and a reference to the next node.

Here’s the code for the Node class:

public class Node
{
    public int Value { get; set; }
    public Node Next { get; set; }
}

This class has two properties: Value to hold the value of the node, and Next to hold a reference to the next node.

Next, let’s create the LinkedList class:

public class LinkedList
{
    public Node Head { get; set; }

    public void AddFirst(int value)
    {
        var node = new Node { Value = value };
        node.Next = Head;
        Head = node;
    }

    public void AddLast(int value)
    {
        var node = new Node { Value = value };
        if (Head == null)
        {
            Head = node;
        }
        else
        {
            var current = Head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = node;
        }
    }

    public void Remove(int value)
    {
        if (Head == null)
        {
            return;
        }

        if (Head.Value == value)
        {
            Head = Head.Next;
            return;
        }

        var current = Head;
        while (current.Next != null)
        {
            if (current.Next.Value == value)
            {
                current.Next = current.Next.Next;
                return;
            }
            current = current.Next;
        }
    }
}

This class has a Head property that holds a reference to the first node in the list. We’ve also defined three methods: AddFirst, AddLast, and Remove.

The AddFirst method adds a new node to the beginning of the list. It creates a new Node object with the specified value sets its Next property to the current Head, and then sets the Head to the new node.

The AddLast method adds a new node to the end of the list. It creates a new Node object with the specified value and then traverses the list until it finds the last node. It then sets the Next property of the last node to the new node.

The Remove method removes a node with the specified value from the list. If the Head node has the specified value, it sets the Head to the next node. Otherwise, it traverses the list until it finds a node with the specified value and removes it by setting its Next property to the node after it.

Using the Linked List

To use the linked list, you can create an instance of the LinkedList class and then call its methods to add, remove, or traverse the nodes. Here’s an example:

var list = new LinkedList();

list.AddFirst(1);
list.AddFirst(2);
list.AddLast(3);
list.AddLast(4);

list.Remove(2);

var current = list.Head;
while (current != null)
{
    Console.WriteLine(current.Value);
    current = current.Next;
}

In this example, we’ve created a new instance of the LinkedList class and added four nodes to it using the AddFirst and AddLast methods. We then remove the node with the value 2 using the Remove method.

Finally, we traverse the list by starting at the Head node and iterating through the list until we reach the end. For each node, we print its value to the console using Console.WriteLine.

When you run this code, the output should be:

1
3
4

This is because the node with the value 2 has been removed from the list.

Conclusion

In this tutorial, you’ve learned how to create a linked list in C# using a LinkedList class and a Node class. You’ve also learned how to add and remove nodes from the list, as well as how to traverse the list. I hope this has been helpful in understanding how linked lists work in C#.