Linked List – Data Structures and Algorithms using C#

In Previous article, Data Structures and Algorithms using C# – Array  we saw that although arrays provide good performance for static collections of data, they had certain disadvantages as data storage structures. In an un-ordered array, searching is slow, whereas in an ordered array, insertion is slow. In both kinds of arrays, deletion is slow. Also, the size of an array can’t be changed after it’s created.

array-vs-linked list

In this article we’ll look at a data storage structure that solves some of these problems: the linked list. Linked lists are probably the second most commonly used general-purpose storage structures after arrays.  In fact, you can use a linked list in many cases in which you use an array, unless you need frequent random access to individual items using an index.

Definition:

A linked list is a linear data structure where each element is a separate object.
Linked list elements are not stored at contiguous location, the elements are linked using pointers.

Each node of a list is made up of two items – the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

Linked List

Types of Linked List
  1. Single Linked List
  2. Double Linked List
  3. Circular Linked List
Implementation

The below code demonstrates a simple linked list. The only operations allowed in this list are

  1. Inserting an item at the beginning of the list
  2. Inserting an item at the end of the list
  3. Deleting the item at the beginning of the list
  4. Iterating through the list to display its contents

Each node in a linked list consists of at least two parts:

  1. Data
  2. Pointer to the next node

In C#, we can represent a node of Linked List using a class. See the below code:

1
2
3
4
5
6
7
8
9
10
11
public class Node
{
        public object value { get; set; }
        public Node next { get; set; }
 
        public Node(Object value)
        {
            this.value = value;
            this.next = null;
        }
}
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
public class LinkedList
    {
        public Node head { get; set; }
        //Node head;
        public LinkedList()
        {
            head = null;
        }
 
        public void InsertAtBegining(T value)
        {
            Node newNode = new Node(value);
            if (head == null)
            {
                head = newNode;
            }
            else
            {
                newNode.next = head;
                head = newNode;
            }
 
        }
 
        public void InsertAtEnd(T value)
        {
            Node newNode = new Node(value);
            if (head == null)
            {
                head = newNode;
            }
            else
            {
                Node node = head;
                while (node.next != null)
                {
                    node = node.next;
                }
                node.next = newNode;
            }
        }
 
        public void DeleteAtBegining(T value)
        {
            if (head == null)
                return;
            Node temp = head;
            head.next = head.next.next;
            temp = null;
 
        }
 
        public void DisplayLinkedList()
        {
            Node node = head;
            while (node != null)
            {
                Console.Write(node.value +"-->");
                node = node.next;
            }
            Console.WriteLine();
        }
    }
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
class Program
    {
 
        static void Main(string[] args)
        {
            LinkedList ls = new LinkedList();
            Console.WriteLine("Empty Linked List");
            int p = 10;
            ls.DisplayLinkedList();
            Console.WriteLine("Start Adding Elements");
            ls.InsertAtBegining(p);
            Console.WriteLine("Insert At Begining an Element");
            ls.DisplayLinkedList();
            ls.InsertAtBegining(2);
            Console.WriteLine("Insert At Begining an Element");
            ls.DisplayLinkedList();
            ls.InsertAtEnd(3);
            Console.WriteLine("Insert At End an Element");
            ls.DisplayLinkedList();
            ls.InsertAtBegining(4);
            Console.WriteLine("Insert At Begining an Element");
            ls.DisplayLinkedList();
            ls.InsertAtEnd(5);
            Console.WriteLine("Insert At End an Element");
            ls.DisplayLinkedList();
        }
   }

So, it was all about Linked List Data Structure, if you have any query then please comment below and let us know. If you liked this article, then please follow us on Facebook to get notification for new posts.

Happy Learning 🙂

Rahul is a Data Geek, technology enthusiast, a passionate writer, thinker with passion for computer programming.  He loves to explore technology and finds ultimate joy when writing about trending technology, geek stuff and web development.