- What is a linked list
- When and why you should use it
- How it is implemented in C# and how do they work
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.
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.
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.
• 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.
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(); } }} |
