Проверить, содержит ли связанный список‹Узел‹T›› определенный узел

Это происходит потому, что вы забыли переопределить метод Equals для класса Node.

Вам нужно что-то вроде следующей реализации:

public class Edge<T> 
{
    public double Speed { get; }
    public double Time { get; }
    public double Distance { get; }
    public T Source { get; }
    public T Destination { get; }

    public Edge(T source, T destination, double speed, double distance)
    {
        if (source == null) throw new ArgumentNullException(nameof(source));
        if (destination == null) throw new ArgumentNullException(nameof(destination));
        if (Math.Abs(speed) < 1E-9) throw new ArgumentException("speed must greater than zero", nameof(speed));
        if (Math.Abs(distance) < 1E-9) throw new ArgumentException("distance must greater than zero", nameof(speed));

        Source = source;
        Destination = destination;
        Speed = speed;
        Distance = distance;
        Time = Distance / Speed;
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Edge<T> objAsEdgeT))
        {
            return false;
        }

        return Math.Abs(Speed - objAsNodeT.Speed) < 1E-9
               && Math.Abs(Time - objAsNodeT.Time) < 1E-9
               && Source.Equals(objAsNodeT.Source)
               && Destination.Equals(objAsNodeT.Destination);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 13;
            hash = (hash*7) + Speed.GetHashCode();
            hash = (hash*7) + Time.GetHashCode();
            hash = (hash*7) + Source.GetHashCode();
            hash = (hash*7) + Destination.GetHashCode();
            return hash;
        }
    }
}

Некоторые примечания:

• Именование имеет первостепенное значение. Класс Node по существу представляет ребро. Таким образом, Edge было бы более подходящим именем класса. Подумайте об обратном: как трудно кому-то было бы прочитать и на самом деле понять фрагмент кода, связанный с узлами графа, и имя, которое мы выбрали, — ребро.
• Старайтесь использовать общие стили кодирования, чтобы ваш код был более читабельным. Например, для свойств мы используем Дело Паскаля.
• В этом случае вам не нужны общедоступные сеттеры.
• Вам не нужен конструктор по умолчанию. Какой смысл в том, что кто-то звонит new Edge<int>()? Не говоря уже о том, что вы получите исключение, поскольку все свойства получат соответствующие значения по умолчанию (двойное -> 0), а расстояние/скорость деления приведет к делению с нулем...
• Внутри конструктора мы должны убедиться, что получаемые нами значения имеют смысл. В противном случае мы получим объект в лучшем случае в бессмысленном состоянии. У нас не может быть ребра без узлов! Таким образом, null не является допустимым значением ни для источника, ни для пункта назначения. Кроме того, distance и speed должны быть больше нуля. Даже если бы speed имело какое-то значение, деление на distance и speed было бы бессмысленным, не говоря уже об исключении...

Причина действительно в том, что вы не реализовали метод Equals для класса Node, и я здесь, чтобы объяснить, почему.

Для того, чтобы понять, зачем вам нужен метод Equals, вам нужно понять, как работает класс LinkedList, который довольно прост: вы просто добавляете, а затем удаляете в нем объекты типа Node. Пока все хорошо, но поскольку вы используете этот объект в этом блоке кода
if (_adjacencyList[source].Contains(sourceEdge) ...) { throw new InvalidOperationException("addEdge: Edge already exists in Graph.\n"); }
, вы вызываете метод Contains. Теперь ваш объект LinkedList должен изучить данные, которые он содержит, и попытаться сравнить, если данная запись уже находится в списке, к сожалению, нигде не упоминается, как это сделать, поэтому он не знает, что делать. Хорошо, что люди, создавшие LinkedLists, подумали об этом и сказали: давайте иметь общий способ проверки равенства двух объектов любого типа данных, и именно так родился знаменитый метод Equals.
Теперь вы имеете право на это. скажем, подождите, разве Equals не определен по умолчанию для каждого класса? Ну, вы абсолютно правы, это так, но также и неправильно, реализация метода Equals по умолчанию не годится для нас, поскольку она проверяет ссылки на объекты и сравнивает их. Даже если вы создадите 2 объекта с одинаковыми данными, они будут иметь разные ссылки, и метод Equals для них не сработает (очевидно).

Продолжая историю связанного списка, связанный список будет использовать реализацию метода Equals по умолчанию, которая дает сбой, и поэтому вы пропустите случай множественных краев.