Linked List Overview

Today in this section, I will talk about Linked Lists. But let's first understand Linked lists here. The purpose of a linked list is to provide a collection wherein you can add/remove items easily. A Linked List has one address section apart from the data section wherein it stores the reference of the next node and so on. In case of doubly linked list. On both the ends there are previous and next references of a data element, so it can move in the list forwrd and backward.

There are the following features of linked lists:

  • Adding/Removing elements is fast.
  • Good at enumeration.
  • No index based access to elements.
  • Linked Lists are not very good when it comes for memory consumption.

Now, in the following example I have a linked list code. But, one thing to remember here is that with a Linked List you can't use a collection to set up the values. In the following screenshot I have highlighted the APIs which Linked Lists offer out of the box.

add after

  1. using System.Collections;    
  2. using System.Collections.Generic;    
  3. using System.Collections.ObjectModel;    
  4. using System.Linq;    
  5. using System;    
  6.     
  7. namespace Collections    
  8. {    
  9.    internal class LinkedList    
  10.     {    
  11.         private static void Main(string[] args)    
  12.         {    
  13.             var monthsofYear = new LinkedList<string>();    
  14.             monthsofYear.AddLast("January");    
  15.             monthsofYear.AddLast("February");    
  16.             monthsofYear.AddLast("April");    
  17.             monthsofYear.AddLast("May");    
  18.             monthsofYear.AddLast("June");    
  19.             monthsofYear.AddLast("July");    
  20.             monthsofYear.AddLast("August");    
  21.             monthsofYear.AddLast("September");    
  22.             monthsofYear.AddLast("October");    
  23.             monthsofYear.AddLast("November");    
  24.             monthsofYear.AddLast("December");    
  25.                 
  26.             
  27.             foreach (var month in monthsofYear)    
  28.             {    
  29.                 Console.WriteLine(month);    
  30.             }    
  31.     
  32.             Console.ReadLine();    
  33.         }    
  34.     
  35.             
  36.     
  37.     }    
  38.     
  39. }   
So, if you see the code then I have missed the month March in the collection. Now, let's assume if I need to add the same in the collection, then how do we do that? So, for doing that, what we need to do is to use the API AddAfter on the element as shown in the following snippet. Now, one more point to note here is that a LinkedList<T> is a collection of LinkedListNode<T> which means I need to find the reference item first and then pass it to the constructor.
  1. using System.Collections;    
  2. using System.Collections.Generic;    
  3. using System.Collections.ObjectModel;    
  4. using System.Linq;    
  5. using System;    
  6.     
  7. namespace Collections    
  8. {    
  9.    internal class LinkedList    
  10.     {    
  11.         private static void Main(string[] args)    
  12.         {    
  13.             var monthsofYear = new LinkedList<string>();    
  14.             monthsofYear.AddLast("January");    
  15.             monthsofYear.AddLast("February");    
  16.             //find the reference    
  17.             LinkedListNode<string> feb = monthsofYear.Find("February");    
  18.             //pass the reference    
  19.             monthsofYear.AddAfter(feb, "March");    
  20.             monthsofYear.AddLast("April");    
  21.             monthsofYear.AddLast("May");    
  22.             monthsofYear.AddLast("June");    
  23.             monthsofYear.AddLast("July");    
  24.             monthsofYear.AddLast("August");    
  25.             monthsofYear.AddLast("September");    
  26.             monthsofYear.AddLast("October");    
  27.             monthsofYear.AddLast("November");    
  28.             monthsofYear.AddLast("December");    
  29.                 
  30.             
  31.             foreach (var month in monthsofYear)    
  32.             {    
  33.                 Console.WriteLine(month);    
  34.             }    
  35.     
  36.             Console.ReadLine();    
  37.         }    
  38.     
  39.             
  40.     
  41.     }    
  42.     
  43. }   
Then, this will produce the desired output as shown below.

output

However, one point to note here this is that that is not an efficient way of using LinkedList although AddAfter() is very efficient because in this case we have used the Find() method that will scan the entire list until it finds the desired element. But, in this case I had no choice since I didn't keep the reference stored upfront. Also, one more important point to note here is that if the Linked List contains the same value more than once in the list, then Find() will only find the first one.

Now, for removing the node you can use Remove(""), but again this is not very efficient since this will scan the List. However, you can also directly use RemoveFirst() or RemoveLast() if your intention is to remove the item that one or you can pass the reference of that node likewise. So, this was the Linked List. In the next section, we'll cover some other collection.

Thanks!