如何从双向链表中删除第一个和最后一个节点？

Question

我有一个作业要写一个方法来删除第一个节点和 return 它在 O(1) 的双向链表中的值，还有一个方法来删除双向链表中的最后一个节点列出并 return 它在 O(1) 中的值。这就是我到目前为止所做的。

class DoubleList<T>
{
    DNode _start;
    DNode _end;

    public void AddFirst(T value)
    {
        DNode tmp = new DNode(value);
        tmp._next = _start;
        tmp._prev = null;
        if (_start != null)
        {
            _start._prev = tmp;
        }
        _start = tmp;
        if (_start._next == null)
            _end = tmp;
    }

    public void AddLast(DoubleList<T> doubleyList, T value)
    {
        DNode tmp = new DNode(value);
        if (_start == null)
        {
            AddFirst(value);
            return;
        }
        DNode lastNode = GetLastNode(doubleyList);
        lastNode._next = tmp;
        tmp._prev = lastNode;
        _end._next = tmp;
        _end = tmp;
    }
}

Answer 1

C# 中已经有一个 class doubleList 具有这些方法。

检查此 link ：https://docs.microsoft.com/fr-fr/dotnet/api/system.collections.generic.linkedlist-1?view=netframework-4.8

Answer 2

这是我提出的一个快速解决方案，尝试使用您的语法：

public DNode RemoveHead()
{
    // "Save" the current head to return it at the end
    DNode head = _start;

    if (_start != null)
    {
        // The start becomes the element next to the current one
        _start = _start._next;

        // The first node has to have no "previous" one
        if (_start != null) _start._prev = null;
    }

    return head;
}

public DNode RemoveTail()
{
    // "Save" the current tail to return it at the end
    DNode tail = _end;

    if (_end != null)
    {
        // The end becomes the element previous to the current one
        _end = _end._prev;

        // The last node has to have no "next" one
        if (_end != null) _end._next = null;
    }

    return tail;
}

Answer 3

除了上面提供的解决方案之外，我还建议您也更改双向链表的大小，以便您更加 space 具有复杂性和时间复杂性意识。您可以在下面找到我的解决方案，它删除列表中的第一个或最后一个节点以及调整计数。

public void RemoveFirst()
        {
            if (Head == null && Tail == null) throw new InvalidOperationException();

            Head = Head.Next;
            Head.Previous = null;
            Count--;
        }

public void RemoveLast()
        {
            if (Head == null && Tail == null) throw new InvalidOperationException();

            Tail = Tail.Previous;
            Tail.Next = null;
            Count--;
        }

如何从双向链表中删除第一个和最后一个节点？

How can I remove the first and last Node from doubly linked list?

c#

doubly-linked-list