Data Structures in C# - Singly and Doubly Linked Lists

We have already covered the arrays and lists that provide us with fundamental ways to store data. However, both have some limitations, such as arrays having fixed sizes, and while the lists provide dynamic resizing, inserting or deleting elements at certain positions (especially at the beginning) can be highly inefficient due to the need to shift elements. This is where the linked lists come into play.

Linked Lists provide a distinctive approach to storing data with amazing advantages over arrays and lists. This article will explore the linked lists and learn how to use them in our programs.

What is a Linked List?

A linked list is a linear data structure that stores data randomly in the memory. Each element in this data structure is called Node. Each node has its data and the address to the next node. Unlike arrays and lists – that store data contiguously- the nodes are scattered in the memory and are accessed through their memory addresses. There is a sequential relationship between the nodes.

Types of Linked Lists

There are two types of linked lists:
1. Singly Linked Lists
2. Doubly Linked Lists

Singly Linked List

We call a linked list singly linked when a node only contains the address of its next node and has no access to its preceding node. It means that the access is unidirectional.

Doubly Linked List

A linked list is called a doubly linked list when it contains a reference to its preceding as well as the succeeding nodes. It allows you to traverse in forward as well as backward directions.

Advantages of Linked Lists

In addition to many more benefits, the linked lists provide us with the following advantages compared to arrays and lists:

• Dynamic Size: The size of the linked lists is not pre-defined. The nodes can be added or removed at run time without pre-allocation or resizing overhead.
• Efficient Insertion and Deletion at Arbitrary Positions: The insertion and deletion of nodes is quite easy in linked lists since there is no need to shift the large memory blocks. Once the node's position is found, it can easily be added or removed from the list, and its address in the neighboring nodes will be updated automatically.

Disadvantages of Linked Lists

Although linked lists are more dynamic than the typical lists, they still have some disadvantages:

Declaring a Linked List

To declare a linked list in C#, we use the generic class LinkedList<T>. We can store any type of data in a linked list since it works with the generic data types. Also, this class handles the node structure and links automatically.

Syntax:

LinkedList <datatype> = new LinkedList<datatype>();

Example:

using System;
using System.Collections.Generic;
class DataStructures {
  static void Main() {
    LinkedList<int> numbers = new LinkedList<int>();

  }
}

Adding Nodes to the Linked List

Nodes can be added to a linked list at the beginning as well as the end. The LinkedList<T> class provides us with built-in functions to do that.

Adding a Node at the Beginning

The AddFirst() method allows you to add a node at the beginning of the list.

Syntax:

linkedlist_name.AddFirst(item);


Example:

using System;
using System.Collections.Generic;
class DataStructures {
  static void Main() {
    LinkedList<int> numbers = new LinkedList<int>();
    numbers.AddFirst(1);
  }
}


Adding a Node at the End
The AddLast() method allows you to add a node at the end of the linked list. 
Syntax: 

linkedlist_name.AddLast(item);


Example:

using System;
using System.Collections.Generic;
class DataStructures {
  static void Main() {
    LinkedList<int> numbers = new LinkedList<int>();
    numbers.AddFirst(1);   //Adds node at the beginning.
    numbers.AddFirst(2);   //Adds node before 1. 
    numbers.AddFirst(10);  //Adds node before 2. 
    numbers.AddLast(100);  //Adds node in the end. 
  }
}


Inserting a Node After Another Node
You can also insert a node after a particular node with the help of the AddAfter() method. 
Syntax:

linkedlist_name.AddAfter(node, value);


Example:

using System;
using System.Collections.Generic;
class DataStructures {
  static void Main() {
    LinkedList<int> numbers = new LinkedList<int>();
    var node = numbers.AddFirst(100); //Storing the value of the node in a variable.
    numbers.AddAfter(node, 50); //Adding a new node after the specified node. 
  }
}


Adding a Node Before Another Node
With the AddBefore() method, you can add a new node before another node. 
Syntax:

linkedlist_name.AddBefore(node, item);


Example:

using System;
using System.Collections.Generic;
class DataStructures {
  static void Main() {
    LinkedList<int> numbers = new LinkedList<int>();
    var node = numbers.AddFirst(100); //Storing the value of the node in a variable.
    numbers.AddBefore(node, 50); //Adding a new node before the specified node. 
  }
}


Removing the Nodes From the Linked Lists
The LinkedList<T> also provides us with the built-in methods to remove the nodes from a linkedlist. 
Removing the First Node
The RemoveFirst() method removes the first node from a linkedlist. Syntax:

linkedlist_name.RemoveFirst();


Example:

using System;
using System.Collections.Generic;
class DataStructures {
  static void Main() {
    LinkedList<int> numbers = new LinkedList<int>();
    numbers.AddFirst(1);
    numbers.AddFirst(2);
    numbers.AddFirst(3);
    numbers.AddFirst(4);
    numbers.AddFirst(5);
    
    numbers.RemoveFirst(); //Removes 1. 
  }
}


Removing the Last Node
The RemoveLast() method lets you remove the last node from a linked list. 
Syntax:

linkedist_name.RemoveLast();


Example:

using System;
using System.Collections.Generic;
class DataStructures {
  static void Main() {
    LinkedList<int> numbers = new LinkedList<int>();
    numbers.AddFirst(1);
    numbers.AddFirst(2);
    numbers.AddFirst(3);
    numbers.AddFirst(4);
    numbers.AddFirst(5);
    
    numbers.RemoveLast(); //Removes 5. 
  }
}


Removing a Node By Value
With the Remove() method, you can easily remove a node by its value. 
Syntax:

linkedlist_name.Remove(value);


Example:

using System;
using System.Collections.Generic;
class DataStructures {
  static void Main() {
    LinkedList<int> numbers = new LinkedList<int>();
    numbers.AddFirst(1);
    numbers.AddFirst(2);
    numbers.AddFirst(3);
    numbers.AddFirst(4);
    numbers.AddFirst(5);
    
    numbers.Remove(3); //Removes 3. 
  }
}


Checking if the List Contains a Node
To find out if a linked list contains a value, we use the Contains() method. It returns true if the value exists. 
Syntax:

linkedlist_name.Contains(value);


Example:

using System;
using System.Collections.Generic;
class DataStructures {
  static void Main() {
    LinkedList<int> numbers = new LinkedList<int>();
    numbers.AddFirst(1);
    numbers.AddFirst(2);
    numbers.AddFirst(3);
    numbers.AddFirst(4);
    numbers.AddFirst(5);
    
    Console.WriteLine(numbers.Contains(3)); //Returns True. 
  }
}


Iterating Through a Linked List
You can iterate through a linked list and perform operations on the nodes with the help of a foreach loop. 
Example:

using System;
using System.Collections.Generic;
class DataStructures {
  static void Main() {
    LinkedList<int> numbers = new LinkedList<int>();
    numbers.AddFirst(1);
    numbers.AddFirst(2);
    numbers.AddFirst(3);
    numbers.AddFirst(4);
    numbers.AddFirst(5);
    
    foreach(int number in numbers)
    {
        Console.WriteLine(number); // Returns 5, 4, 3, 2, 1
    } 
  }
}


When you run the above code, you will see that the counting is printed in reverse order. Can you think of a way to print it in ascending order? If yes, try to do it for practice.