Let's create a Singly Linked List
Tags: datastructures, linkedlist
Published: 2021-03-10 08:16:38

**This post originally posted in my bog site that you can find [here](https://www.rasikag.com/posts/lets_create_a_singly_linked_list)**

Today I am focusing on how to create a minimalistic Singly Linked List. A linked list is a data structure that contains a sequence of data linked with each other. Each element in the link can contain a value and reference to the next element in the link. The elements we called as Nodes.

We can present the Linked List as below picture. You can see, apart from the last node, all are pointing to its’ next node.

![img01](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yhl76ymaimke48kl10rd.jpg)

The starting node is called as Head Node and the last node is Tail Node. As I explain earlier every node can keep data and the next item’s reference.If we want to go to the 3rd node we need to start from the 1st node keep going until we reach the 3rd node.

Okay, let’s start coding a Linked List(I am using C# here).

First, we create a Node class that keeps data and the next element. I will start will `int` datatype and later I will change this to keep generic data type.

```csharp
public class Node
{
    public Node(int value)
    {
        Value = value;
    }

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

}
```

Here we are keeping data in `Value` property and next Node object will keep in `Next` property.

Now we can start to create a `LinkedList` class.

```csharp
public class LinkedList: ICollection<int> {
}
```

We are using `ICollection` interface. With that, we can leverage the inbuild enumeration functionality.

Next, we are adding public Head and Tail properties. Using those we can return Head and Tail of the Linked List any time and these are public variables. Also, we have 2 private variables as `head` and `tail` to keep Nodes internally.

```csharp
public class LinkedList: ICollection<int>
{
    private Node head
    {
        get;
        set;
    }
    private Node tail
    {
        get;
        set;
    }
    public int Head { get {return head.Value;}}
    public int Tail { get { return tail.Value;}}
    public int Count
    {
        get;
        private set;
    }
}
```

This `Count` property from `ICollection` implementation.

There are 2 ways to add value to the linked list. We can add a value to the head or add a value to the tail. Let’s start with adding a value to the tail.

### Add to Tail

Here is the code to add value to the tail.

```csharp
public void AddTail(int value)
{
    var node = new Node(value);

    if (Count == 0) // A
    {
        head = node;
    }
    else
    {
        tail.Next = node; // B
    }
    tail = node; // C
    Count++;
}
```

Let me explain this code. To demonstrate let’s assume the below code.

```csharp
LinkedList linkedList = new LinkedList();
for (int i = 0; i < 5; i++)
{
    linkedList.AddTail(i);
}
```

**When** `i = 0`

`head` and `tail` are `null`. Also `Count` is `0` . So, it will go inside `// A` block and set head to that node. Also, it will set `tail` to that node.

![img02](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/am78kv3yt9qr5usbcg00.PNG)

**When** `i = 1`

Now we create the second `Node` variable. Because Count is 1 it will go to `// B` and set the tail’s `Next` property to this node. It implies that `head` ‘s Next property also.

Then `tail` variable referencing the same node also. Let’s put in to picture.

![img03](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bgzj3zkm5cex4ye2bdc2.PNG)

When `i = 1` tail also referring the head. Once we set the `tail.Next` to new node that means head’s `Next` also be the new node. I added colors with comment reference to each block that what happen in each block.

> This is possible because every time we assign a variable to a object, we are passing the reference of that object.


Until for loop break, this will happen. Let me put it into a picture.

![img04](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xmqgmph06wymneeg8k0y.PNG)

The important point that need to mentioned here that always the tail node’s `Next` property will be `null` .

Any time, Head and Tail variables will give the head and tail values. Once we are adding values to the tail, most reason value always is in the tail.

### Add to Head

This is the reverse methodology of add to tail. Once we adding values to head, that means most reason value will be in the head. The least reason value will be in the tail.

Here is the code block to add value to the head method.

```csharp
public void AddHead(int value)
{
    Node temp = head; // A
    head = new Node(value); // B
    head.Next = temp; // C
    Count++;
    if (Count == 1)
    {
        tail = head; // D
    }
}
```

To simulate this code block let’s use our usual `for` loop example.

```csharp
LinkedList linkedList = new LinkedList();
for (int i = 0; i < 5; i++)
{
    linkedList.AddHead(i);
}
```

**When** `i=0`

Our `head` and `tail` is equal to `null` at this moment. In the `//A` code block we assign our current head to `temp` variable and at this moment it is `null`. Then we create a new node that assigning that value and assign it to `head`. So once we execute `//B` means always our latest value will be in the head. Then our previous node will assign to `head`’s `Next` .

In this moment //D block will be executed and the initial value will assign to `tail`.

> Keep note that this will be only executed when `i=0`

Let’s show this in a picture.

![img05](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r5b8oxuxaeidq252no88.PNG)

**When** `i = 1`

Now is the fun part happen. First, we assign the current head to a temp variable. In the `head` variable, it only contains one `node`. Then we create a new node and assign it to `head`. Then current `head` ‘s Next will assign the temp variable. Because of that head will always have the latest variable.

Let’s get that into a picture.

![img06](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hnymflkpsd35odjpbgij.PNG)

**When** `i = 2`

The same thing is going on when i = 2. For more clarity, I will add a picture of it.

![img07](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y1yxgvysqm80fn2aq0at.PNG)

This will be repeated until `for` loop end.

At this point, we added the main functionality for the `LinkedList` class. Only we have to implement the `ICollection` interface.

Here are the methods to remove the first item and the last item from Linked List.

```csharp
public void RemoveFirst()
{
    if (Count != 0)
    {
        head = head.Next;
        Count--;
        if (Count == 0)
        {
            tail = null;
        }
    }
}
public void RemoveLast()
{
    if (Count != 0)
    {
        if (Count == 1)
        {
            head = null;
            tail = null;
        }
        else
        {
            Node current = head;
            while (current.Next != tail)
            {
                current = current.Next;
            }
            current.Next = null;
            tail = current;
        }
        Count--;
    }
}
```

I hope this covers all the topics that need to cover on a singly linked list. Hope you guys learned something from this.

---

I will wrap up this post from here. If you have anything to ask regarding this please leave a comment here. Also, I wrote this according to my understanding. So if any point is wrong, don’t hesitate to correct me. I really appreciate you.
That’s for today friends. See you soon. Thank you.