Linked List Implementation in C# | Data Structure Using C#

Linked List Implementation in C#
 
 
 
Building your own linked list class in C# is not appreciated as the standard libraries provide a solid implementation in LinkedList generic class. Then why do we have this article? Why are we bothering about implementing linkedList in C# when it is already there? In this article I going to look at :
  • What is a linked list
  • When and why you should use it
  • How it is implemented in C# and how do they work
 
So first thing, what is a linked list?

In simple words, a liked list is another data structure in which every element is linked to next element in the list. The following image shows how a linked list looks like. There are two variables associated with a linked list: 1. Head (which points to the first element of the list) and 2. Tail (which points to the last element of the list). Tail variable is not necessary in case of singly linked list.

Linked List Implementation in C#

What are the benefits of using a linked list?

Why can we just use an array to store element? Why do we require a linked list?
An array can be used when we already know how many elements will be stored. But what if we have variable number of elements to be stored? In this case we use a linked list.

Because linked list can be of arbitrary size. We can add as many elements to the list as we want. There is no upper bound on number of stored element in the list. In liked list, it is easy to remove an element which is sometime very hard in case of an array. Then why not just use linked list all time instead of array?
 

For linked list the penalty comes as access speed. In array we can access any of the element just by using element’s index. But in case of linked list we have to traverse the list until we find the desired element.

How linked list works?

• Adding a new element to the list: Just allocate memory for new element and add this node to the chain. You can add it at front of the list or at the end of the list.
• Searching an element: To search whether or not a particular element is present in the list or node, we start with the head node and keep searching till either we reach to the end of the list or the element is found.
• Removing an element: Use the search procedure to search for particular node and then remove it from the chain.

A simple linked list implementation using C# generics

First we need to define linked list element. In C# we use a class for this, instead of struct (in languages like C and C++, struct is used for defining a node of a linked list). The reason for using a class is that classes in C# are passed by reference just like pointers in C/C++. When we make a copy of a reference, just the reference is copied not the original item.
Initially when the list is empty, both head and tail variables are null. When there is only one element in the list, both head and tail points to the same element.

 
1
2
3
4
5
6
7
8
9
10
class LinkedListNode<T>
    {
        public T Data;
        public LinkedListNode<T> Next;
 
        public LinkedListNode(T value)
        {
            this.Data = value;
        }
    }

Adding an Element
In adding to the list we need to check if the list is empty, if it is, the new element becomes the head. Otherwise we will add the new element to the end of the tail.

 
1
2
3
4
5
6
7
8
9
10
11
12
13
public void Add(T newNode)
        {
            LinkedListNode<T> Listelement = new LinkedListNode<T>(newNode);
            if (Head == null)
            {
                Head = Listelement;
            }
            else
            {
                Tail.Next = Listelement;
            }
            Tail = Listelement;
        }

Removing an element
Check if it is the head or tail node to be removed. For other any other element, search for the element in the list and then remove it.

 
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
public void Remove(LinkedListNode<T> node)
        {
            if (node == null)
                throw new Exception("LinkedListElement<T> null is not a valid argument");
 
            if (node == Head)
                Head = node.Next;
            if (node == Tail)
            {
                LinkedListNode<T> temp = Head;
                while (temp.Next != node)
                {
                    temp = temp.Next;
                }
                Tail=temp;
            }
 
            if (node.Next != null)
            {
                LinkedListNode<T> temp = Head;
                while (temp.Next != node)
                {
                    temp = temp.Next;
                }
                temp.Next = node.Next;
            }
        }

Searching for an Element
Iterate through the list till you find the element or reach to the end of the list.

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public LinkedListNode<T> Find(T node)
        {
            return Find(node, Head);
        }
 
        public LinkedListNode<T> Find(T node, LinkedListNode<T> start)
        {
            LinkedListNode<T> iterator = start;
            while (iterator != null)
            {
                if (iterator.Data.Equals(node)) return iterator;
                iterator = iterator.Next;
            }
            return null;
        }

The full code of the linked list implementation is listed below:

 
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
132
133
134
135
using System;
 
namespace DataStructure
{
 
    class LinkedListNode<T>
    {
        public T Data;
        public LinkedListNode<T> Next;
 
        public LinkedListNode(T value)
        {
            this.Data = value;
        }
    }
 
    class LinkedList<T>
    {
 
        public LinkedListNode<T> Head;
        public LinkedListNode<T> Tail;
 
        public LinkedList()
        {
            Head = null;
            Tail = null;
        }
 
        public void Add(T newNode)
        {
            LinkedListNode<T> Listelement = new LinkedListNode<T>(newNode);
            if (Head == null)
            {
                Head = Listelement;
            }
            else
            {
                Tail.Next = Listelement;
            }
            Tail = Listelement;
        }
 
        public void Remove(LinkedListNode<T> node)
        {
            if (node == null)
                throw new Exception("LinkedListElement<T> null is not a valid argument");
 
            if (node == Head)
                Head = node.Next;
            if (node == Tail)
            {
                LinkedListNode<T> temp = Head;
                while (temp.Next != node)
                {
                    temp = temp.Next;
                }
                Tail=temp;
            }
 
            if (node.Next != null)
            {
                LinkedListNode<T> temp = Head;
                while (temp.Next != node)
                {
                    temp = temp.Next;
                }
                temp.Next = node.Next;
            }
        }
 
        public LinkedListNode<T> Find(T node)
        {
            return Find(node, Head);
        }
 
        public LinkedListNode<T> Find(T node, LinkedListNode<T> start)
        {
            LinkedListNode<T> iterator = start;
            while (iterator != null)
            {
                if (iterator.Data.Equals(node)) return iterator;
                iterator = iterator.Next;
            }
            return null;
        }
 
    }
 
 
 
    class linked_list
    {
        public static void Main(string[] args)
        {
            LinkedList<string> ls = new LinkedList<string>();
            ls.Add("Good");
            ls.Add("day");
            ls.Add("to you!");
 
            // Print the contents of the entire list
            LinkedListNode<string> print_it = ls.Head;
 
            int Lp = 0;
            while (print_it != null)
            {
                Console.WriteLine("{0} {1}", Lp++, print_it.Data);
                print_it = print_it.Next;
            }
 
            LinkedListNode<string> search_it = ls.Find("day");
 
            if (search_it != null)
            {
                Console.WriteLine("\nFound: {0}\n", search_it.Data);
                Console.WriteLine("deleting...\n");
                ls.Remove(search_it);
            }
            else
                Console.WriteLine("Not found!");
 
            // Print the contents of the entire list
            print_it = ls.Head;
 
            Lp = 0;
            while (print_it != null)
            {
                Console.WriteLine("{0} {1}", Lp++, print_it.Data);
                print_it = print_it.Next;
            }
            Console.ReadKey();
 
        }
    }
 
}

READ  WhatsApp Account Lifetime Subscription Working Trick

Leave a Reply

Your email address will not be published. Required fields are marked *