CODEWITHSUNDEEP
c#doubly-linked-list
IdanAcker
IdanAcker

Reputation: 5

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

I have a homework to write a method that will remove the FIRST Node and return its value in a doubly linked list in O(1), and one more method to remove the LAST Node in doubly linked list and return its value in O(1). This is what I did so far.

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;
    }
}

Upvotes: 0

Views: 727

Answers (3)

user11476329
user11476329

Reputation:

Further more from the solution provided above, I would suggest that you alter the size of the doubly linked list as well so that you're more space complexity conscious as well as time complexity conscious. You can find my solution below that removes the first or the last node in a list as well as adjusting the count.

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--;
        }

Upvotes: 0

StackLloyd
StackLloyd

Reputation: 439

Here's a quick solution I came out with, trying to use your syntax:

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;
}

Upvotes: 0

lema
lema

Reputation: 480

There is already a class doubleList in C# that have these methods.

Check this link : https://learn.microsoft.com/fr-fr/dotnet/api/system.collections.generic.linkedlist-1?view=netframework-4.8

Upvotes: 2

Related Questions