Doubly Linked List

Doubly Linked List in C#: A Fun and Practical Guide

1. What is a Doubly Linked List?
2. Creating a Doubly Linked List Class
3. Insertion Operations
   • Insert at the Beginning
   • Insert at the End
   • Insert after a spefific Node
4. Deletion Operations
5. Traversal
   • Forward Traversal
   • Backward Traversal
6. Search Node
7. Complexity Analysis
8. Use Cases
9. Conclusion

1. What is a Doubly Linked List?

In a Doubly Linked List, each node contains two links - the first link points to the previous node and the next link points to the next node in the sequence.The prev pointer of the first node and next pointer of the last node will point to null.

Let us start by defining the Node class using C#:

public class Node<T>
{
    public T Data { get; set; } 
    public Node<T> Next { get; set; }
    public Node<T> Prev { get; set; }

    public Node (T data)
    {
        Data = data;
        Next = null;
        Prev = null;
    }
}

2. Creating a Doubly Linked List Class

public class DoublyLinkedList<T>
{
    private Node<T> head;
    private Node<T> tail;

    private int size;
    public DoublyLinkedList()
    {
        head = null;
        tail = null;
        size = 0;
    }

    public int Size() => size;
}

3. Insertion Operations

Insert at the Beginning

public void AddFirst(T data)
{
     Node<T> newNode = new Node<T>(data);
     if (head == null)
     {
         head = tail = newNode;
     }
     else
     {
         newNode.Next = head;
         head.Prev = newNode;
         head = newNode;
     }

     size++;
}

Insert at the End

public void AddTail(T data)
 {
     Node<T> newNode = new Node<T>(data);
     if (head == null)
     {
         head = tail = newNode;
     }
     else
     {
         tail.Next = newNode;
         newNode.Prev = tail;
         tail = newNode;
     }
     size++;
}

Insert after a specific Node

public void InsertAt(T data, int index)
{
     if (index < 0 || index> size)
     {
         throw new ArgumentOutOfRangeException("Index", index, "Index must be non - negative");
     }
     if(index == 0)
     {
         AddFirst(data);
         return;
     }
     else if (index == size)
     {
         AddTail(data);
         return;
     }
     else
     {
         Node<T> current = head;
         for (int i = 0; i < index - 1; i++)
         {
             current = current.Next;
         }
         Node<T> newNode = new Node<T>(data);
         newNode.Next = current.Next;
         newNode.Prev = current;
         current.Next.Prev = newNode;
         current.Next = newNode;
         size++;
     }
}

4. Deletion Operation

public void Delete(T Data)
 {
     Node<T> current = head;

     while (current != null)
     {
         if (current.Data.Equals(Data))
         {
             //if the node is not the head
             if (current.Prev != null)
             {
                 current.Prev.Next = current.Next;
             }
             else
             {
                 head = current.Next;
             }

             if (current.Next != null)
             {
                 current.Next.Prev = current.Prev;
             }
             else
             {
                 tail = current.Prev;
             }
             size--;
             return;
         }

         current = current.Next;
     }
     Console.WriteLine("Node with data {0} not found", Data);
}

5. Traversal

Forward Traversal

public void PrintForward()
{
    Node<T> current = head;
    while (current != null)
    {
        Console.Write(current.Data + " ");
        current = current.Next;
    }
    Console.WriteLine();
}

Backward Traversal

public void PrintBackward()
{
    Node<T> current = tail;
    while (current != null)
    {
        Console.Write(current.Data + " ");
        current = current.Prev;
    }
    Console.WriteLine();
}

6. Search Node

public void Find(T Data)
{
     Node<T> current = head;
     while (current != null)
     {
         if (current.Data.Equals(Data))
         {
             Console.WriteLine("Found: " + Data);
             return;
         }
         current = current.Next;
     }
     Console.WriteLine("Not Found: " + Data);
}

7. Complexity Analysis

Operation	Time Complexity	Space Complexity
Insertion	O(1)/O(n)	O(1)
Deletion	O(1)	O(1)
Search	O(n)	O(1)
Traverse	O(n)	O(1)

8. Use Cases

• Browser history management
• Music/Video playlists
• Undo/Redo functionality
• Navigation systems

9. Conclusion

Doubly Linked Lists provide enhanced flexibility compared to single linked lists at the cost of additional memory usage.They are particularly useful in scenarios requiring bidirectional traversal and frequent modifications.When implementing DLLs, careful pointer management is crucial to avoid broken links and memory leaks.