Deque

public class DoublyNode<T>
{
public DoublyNode(T data)
{
Data = data;
}

public T Data { get; set; }

// FIXED: Changed ‘DoubleNode’ to match the actual class name ‘DoublyNode’
public DoublyNode<T>? Previous { get; set; }
public DoublyNode<T>? Next { get; set; }
}

using System;
using System.Collections;
using System.Collections.Generic;

namespace SimpleAlgorithmsApp
{
public class Deque<T> : IEnumerable<T>
{
private DoublyNode<T>? head; // head/first element
private DoublyNode<T>? tail; // last/tail element
private int count; // number of elements in the list

// adding an element to the back
public void AddLast(T data)
{
DoublyNode<T> node = new DoublyNode<T>(data);

if (head == null)
{
head = node;
tail = node; // FIXED: If empty, tail must also point to the new node
}
else
{
tail!.Next = node; // Safe bang operator used because tail won’t be null here
node.Previous = tail;
tail = node;
}
count++;
}

// adding an element to the front
public void AddFirst(T data)
{
DoublyNode<T> node = new DoublyNode<T>(data);

if (head == null)
{
head = node;
tail = node; // FIXED: If empty, tail must also point to the new node
}
else
{
node.Next = head;
head.Previous = node;
head = node;
}
count++;
}

public T RemoveFirst()
{
if (count == 0 || head == null)
throw new InvalidOperationException(“Deque is empty.”);

T output = head.Data;
if (count == 1)
{
head = null;
tail = null;
}
else
{
head = head.Next;
head!.Previous = null;
}
count–;
return output;
}

public T RemoveLast()
{
if (count == 0 || tail == null)
throw new InvalidOperationException(“Deque is empty.”);

T output = tail.Data;
if (count == 1)
{
head = null;
tail = null;
}
else
{
tail = tail.Previous;
tail!.Next = null;
}
count–;
return output;
}

// FIXED: ‘Public’ changed to lowercase ‘public’
public T First
{
get
{
if (IsEmpty || head == null)
throw new InvalidOperationException(“Deque is empty.”);
return head.Data;
}
}

public T Last
{
get
{
if (IsEmpty || tail == null)
throw new InvalidOperationException(“Deque is empty.”);
return tail.Data;
}
}

public int Count => count;
public bool IsEmpty => count == 0;

public void Clear()
{
head = null;
tail = null;
count = 0;
}

// FIXED: Handled potential NullReferenceException using generic EqualityComparer
public bool Contains(T data)
{
DoublyNode<T>? current = head;
EqualityComparer<T> comparer = EqualityComparer<T>.Default;

while (current != null)
{
if (comparer.Equals(current.Data, data))
return true;
current = current.Next;
}
return false;
}

// FIXED: Eliminated infinite recursion/StackOverflowException
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}

public IEnumerator<T> GetEnumerator()
{
DoublyNode<T>? current = head;
while (current != null)
{
yield return current.Data;
current = current.Next;
}
}
}
}

public void AddFirst(T data)
{
DoublyNode<T> node = new DoublyNode<T>(data);

if (head == null)
{
// FIXED: Explicitly handle the empty-list state
head = node;
tail = node;
}
else
{
// Link the new node to point forward to the current head
node.Next = head;
// Link the current head to point backward to the new node
head.Previous = node;
// Move the head pointer to the new node
head = node;
}

count++;
}

public void AddLast(T data)
{
DoublyNode<T> node = new DoublyNode<T>(data);

if (head == null)
{
// FIXED: Explicitly link both structural pointers for an empty state
head = node;
tail = node;
}
else
{
// Safe to use the null-forgiving operator (!) since head != null guarantees tail != null
tail!.Next = node;
node.Previous = tail;
tail = node; // Move the tail pointer to the newly appended node
}

count++;
}

public T RemoveFirst()
{
// 1. Added head == null check to satisfy modern compiler null-safety analysis
if (count == 0 || head == null)
throw new InvalidOperationException(“The deque is empty.”);

T output = head.Data;

if (count == 1)
{
head = null;
tail = null;
}
else
{
head = head.Next;
// 2. Added the null-forgiving operator (!) because we’ve proven head isn’t null
head!.Previous = null;
}

count–;
return output;
}

public T RemoveLast()
{
// 1. Added tail == null check to satisfy modern compiler null-safety analysis
if (count == 0 || tail == null)
throw new InvalidOperationException(“The deque is empty.”);

T output = tail.Data;

if (count == 1)
{
head = null;
tail = null;
}
else
{
tail = tail.Previous;
// 2. Added the null-forgiving operator (!) because we’ve proven tail isn’t null
tail!.Next = null;
}

count–;
return output;
}

Deque<string> usersDeck = new Deque<string>();
usersDeck.AddFirst(“Alice”);
usersDeck.AddLast(“Kate”);
usersDeck.AddLast(“Tom”);

foreach (string s in usersDeck)
Console.WriteLine(s);

string removedItem = usersDeck.RemoveFirst();
Console.WriteLine(“\n Removed: {0}\n”, removedItem);

foreach (string s in usersDeck)
Console.WriteLine(s);