Linked List

I will use VS Code with Polyglot Notebook.
Why? It is easier to show and visualize to others using Polyglot Notebook.
You are free to use any code editor or IDE of your choice.
I recommend VS Code because it allows for direct code execution without adhering strictly to C# syntax, facilitating easier visualization. Attempting to implement the same code in another editor may result in compile-time errors.
I will identify lines that cause errors, and you can remove those specific lines of code.

Create One Class Name CodeFrydev

If you are not familiar with classes, please follow this post first; only then will you be able to understand.
Create a property named UserName of data type string.
Create another property named Rank of data type int.

Your class will look as follows:

1
2
3
4
5
public class CodefryDev
{
    public string UserName {get;set;}
    public int Rank {get;set;}
}

Create An Object of the Codefrydev

The code below demonstrates how to create an instance of the Codefrydev class:

1
2
3
4
var myself = new CodefryDev(); 
// Below line of Code will only work on VS Code Using Polyglot Notebook. 
// You can Remove this line for other IDE
myself

Object Of Codefrydev With no any assigneed value

In an instance, we see that the object has two fields: one string with a null (default value in C#) and another int with a value of 0, as it should be.

Now, assign some values to the object:

1
2
3
4
5
6
7
Codefrydev myself = new Codefrydev();
myself.Rank = 1;
myself.UserName = "firstUser";

// The line below will only work in VS Code using Polyglot Notebook.
// You can remove this line for other IDEs.
myself

We will have an object with the UserName value firstUser and the Rank value 1.

Modifications in the Codefrydev Class

Introduce a field/property whose data type will be Codefrydev.

1
2
3
4
5
6
public class CodefryDev
{
    public string UserName { get; set; }
    public int Rank { get; set; }
    public CodefryDev RelatedPerson { get; set; }
}

Create an Object of the CodefryDev Class Again

Code for creating an instance of the CodefryDev class:

1
2
3
4
var myself = new CodefryDev(); 
// The line below will only work in VS Code using Polyglot Notebook.
// You can remove this line for other IDEs.
myself

It will show something like this:
As we see, the result is similar to before but with one extra field RelatedPerson having a null value since no value has been assigned.

Create Another User of CodefryDev

Code for the second user, which doesn’t interact with the first user:

1
2
3
4
var otherPerson = new CodefryDev(); 
// The line below will only work in VS Code using Polyglot Notebook.
// You can remove this line for other IDEs.
otherPerson

In VS Code, running the code will show something like this:

On assigning some values:

1
2
3
4
5
otherPerson.Rank = 2;
otherPerson.UserName = "secondUser";
// The line below will only work in VS Code using Polyglot Notebook.
// You can remove this line for other IDEs.
otherPerson

In VS Code, the output will look something like the image below:

Linking One Object to Another

Now, assign the otherPerson instance to the myself object’s RelatedPerson field as follows:

1
2
3
4
myself.RelatedPerson = otherPerson;
// The line below will only work in VS Code using Polyglot Notebook.
// You can remove this line for other IDEs.
myself

In VS Code, it will show something like this:
You will find that the myself value is not null and it points to RelatedPerson.
This, in a nutshell, is the main logic behind a linked list.
One object points to another object, which in turn points to another object, and so on.
For example, consider the snippet below:
- Creating another instance of the CodefryDev class with the name thirdPerson.
- Assigning values and linking to otherPerson.
  1 2 3 4 5
  var thirdPerson = new CodefryDev(); thirdPerson.Rank = 3; thirdPerson.UserName = "thirdUser"; otherPerson.RelatedPerson = thirdPerson; myself
- In VS Code, it will show something like this:
- This means the third user is linked with the second user, and the second user is linked with the first user.
- In a similar fashion, you can create another instance and link it.

Understanding the Main Logic of Linking Objects

Now that we understand the main logic of linking one object with another object, it’s clear that manually creating and linking instances repeatedly isn’t feasible. To solve this issue, I’ll introduce you to a new class that will handle all heavy lifting automatically.

Create a Class Named Node which will be the Data Type of LinkedList

This class will have two fields and a constructor. For more details about classes, you can follow class tutorials.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public class Node
{
    public int value;
    public Node next;

    public Node(int value)
    {
        this.value = value;
    }
}

Create Another Class Named LinkedList which will hold the Data Type Node

This class will handle all the methods and fields required for a linked list to perform all the heavy lifting.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class LinkedList
{
    public Node Head;
    private Node Tail;
    private int size;

    public void AddLast(int item)
    {
        var node = new Node(item); 
        if (Head == null) 
        {    
            Head = Tail = node;
        }
        else
        {
            Tail.next = node;
            Tail = node;
        } 
        size++;
    } 
}

In this example:

LinkedList class manages a linked list structure.
It includes a Head and Tail pointer of type Node to manage the start and end of the list.
AddLast method adds a new Node containing an int item to the end of the list, adjusting Tail and size accordingly.

This class has a Head field which points to the first object instance, similar to the myself or firstPerson object we had in the earlier example. Tail points to another instance of the Node class object if any, or it will be null by default. Size holds how many values have been added to the linked list. The AddLast method takes one parameter. Upon calling this method:

It creates a new object of the Node class with a specified value.
If it is the first time called (when Head is null), it assigns the new object to Head.
If it is not the first call, it assigns the new object to the Tail’s Next value and updates Tail to point to this newly created object.

Creating an Instance of the LinkedList Class

Let’s create an instance and add values to the linked list:

1
2
3
4
5
6
7
8
9
var ll = new LinkedList();
ll.AddLast(1);
ll.AddLast(2);
ll.AddLast(3);
ll.AddLast(4);
ll.AddLast(5);
// The line below will only work in VS Code using Polyglot Notebook.
// You can remove this line for other IDEs.
ll

In VS Code, it will show something like this:

Real LinkedList

This image represents a real linked list where each node (represented by Node objects) points to the next node, starting from the Head. Each node contains a value (Item) and a reference (Next) to the next node in the sequence.

AddFirst Method

To add a method AddFirst to the LinkedList class that inserts data at the beginning of the linked list, you can introduce the following code. This method is straightforward and operates similarly to AddLast, but instead of modifying the Tail to add at the end, it modifies the Head to add at the beginning:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public void AddFirst(int item)
{
    var node = new Node(item);

    if (Head == null)
        Head = Tail = node;
    else
    {
        node.next = Head;
        Head = node;
    }

    size++;
}

Explanation

node: Creates a new Node object with the specified item value.
if (Head == null): Checks if the linked list is empty. If so, sets both Head and Tail to the new node.
else: If the linked list is not empty:
- Sets the next field of the new node to point to the current Head.
- Updates the Head to be the new node.
size++: Increments the size of the linked list to keep track of the number of elements.

This method efficiently adds a new node at the beginning of the linked list, adjusting the Head pointer accordingly.

Similary Adding another methods To LinkedList class

For Removing First element of LinkedList

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public void RemoveFirst()
{
    if (Head == null)
        return;

    if (Head == Tail)
        Head = Tail = null;
    else
    {
        var second = Head.next;
        Head.next = null;
        Head = second;
    }

    size--;
}

Removing last Element

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public void RemoveLast()
{
    if (Head == null)
        return;

    if (Head == Tail)
        Head = Tail = null;
    else
    {
        var previous = GetPrevious(Tail);
        Tail = previous;
        Tail.next = null;
    }

    size--;
}

Get Previous Element

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public Node GetPrevious(Node node)
{
    var current = Head;
    while (current != null)
    {
        if (current.next == node) return current;
        current = current.next;
    }
    return null;
}

To Reverse Linked List

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public void Reverse()
{
    if (Head == null) return;

    var previous = Head;
    var current = Head.next;
    while (current != null)
    {
        var next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }

    Tail = Head;
    Tail.next = null;
    Head = previous;
}

Find if there is any loop

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public bool HasLoop()
{
    var slow = Head;
    var fast = Head;

    while (fast != null && fast.next != null)
    {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast)
            return true;
    }

    return false;
}

Get Kth Element from End of Linked List

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public int GetKthFromTheEnd(int k)
{
    if (Head == null) return;

    var a = Head;
    var b = Head;
    for (int i = 0; i < k - 1; i++)
    {
        b = b.next;
        if (b == null)
            throw new InvalidOperationException();
    }
    while (b != Tail)
    {
        a = a.next;
        b = b.next;
    }
    return a.value;
}

Full Source Code should look like this.

Souce Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
using System;
public class LinkedList
{
    public Node Head;
    private Node Tail;
    private int size;

    public void AddLast(int item)
    {
        var node = new Node(item); 
        if (Head == null) 
        {    
            Head = Tail = node;
        }
        else
        {
            Tail.next = node;
            Tail = node;
        } 
        size++;
    } 
    public void AddFirst(int item)
    {
        var node = new Node(item);

        if (Head == null)
            Head = Tail = node;
        else
        {
            node.next = Head;
            Head = node;
        }

        size++;
    }
    public void RemoveFirst()
    {
        if (Head == null)
            return;

        if (Head == Tail)
            Head = Tail = null;
        else
        {
            var second = Head.next;
            Head.next = null;
            Head = second;
        }

        size--;
    }
    public void RemoveLast()
    {
        if (Head == null)
            return;

        if (Head == Tail)
            Head = Tail = null;
        else
        {
            var previous = GetPrevious(Tail);
            Tail = previous;
            Tail.next = null;
        }

        size--;
    }
    public Node GetPrevious(Node node)
    {
        var current = Head;
        while (current != null)
        {
            if (current.next == node) return current;
            current = current.next;
        }
        return null;
    }
    public void Reverse()
    {
        if (Head == null) return;

        var previous = Head;
        var current = Head.next;
        while (current != null)
        {
            var next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }

        Tail = Head;
        Tail.next = null;
        Head = previous;
    }
    public bool HasLoop()
    {
        var slow = Head;
        var fast = Head;

        while (fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast)
                return true;
        }

        return false;
    }
    public int GetKthFromTheEnd(int k)
    {
        if (Head == null) throw new InvalidOperationException();

        var a = Head;
        var b = Head;
        for (int i = 0; i < k - 1; i++)
        {
            b = b.next;
            if (b == null)
                throw new InvalidOperationException();
        }
        while (b != Tail)
        {
            a = a.next;
            b = b.next;
        }
        return a.value;
    } 
}

Thats all for now Will see you any another post.

Linked List#

Create One Class Name CodeFrydev#

Create An Object of the Codefrydev#

Modifications in the Codefrydev Class#

Create an Object of the CodefryDev Class Again#

Create Another User of CodefryDev#

Linking One Object to Another#

Understanding the Main Logic of Linking Objects#

Create a Class Named Node which will be the Data Type of LinkedList#

Create Another Class Named LinkedList which will hold the Data Type Node#

Creating an Instance of the LinkedList Class#

AddFirst Method#

Explanation#

Similary Adding another methods To LinkedList class#

Full Source Code should look like this.#

Previous Chapter Class#