Object-oriented – Stack extending LinkedList. A violation of Liskov Substitution Principle

designliskov-substitutionobject-orientedobject-oriented-designsolid

A class LinkedList exists with functions such as add_first(), add_last(), add_after(), remove_first(), remove_last() and remove()

Now there is a class Stack that provides functionalities such as push(), pop(), peek() or top(), and to implement these methods it extends the LinkedList class methods. Is this a violation of Liskov Substitution Principle?

For example, consider the case add_after() to add a node at the nth position of a Linked List. This can be done in the base class but not in the Stack class. Are postconditions being weakened here or do you modify the add_after() method to add to the top of the Stack?

Also, if not a violation, is this bad design? And how would you implement the Stack functionality using the LinkedList class?

Best Answer

Now there is a class Stack that provides functionalities such as push(), pop(), peek() or top(), and to implement these methods it extends the LinkedList class methods. Is this a violation of Liskov Substitution Principle?

No. It is perfectly fine to add methods in a subtype.

For example, consider the case add_after() to add a node at the nth position of a Linked List. This can be done in the base class but not in the Stack class.

This is a violation of the LSP. The LSP says that instances of a subtype must be substitutable for instances of a supertype without changing the desirable properties of a program. If a subtype removes a method, then any code that calls that method will crash (or get a NoMethodError exception, or something along those lines). Clearly, "not crashing" is a desirable property.

Are postconditions being weakened here or do you modify the add_after() method to add to the top of the Stack?

Modifying the add_after() method in this way is a violation of the History Rule (the most important of the rules!) and thus doesn't help fixing the violation of the LSP.

And how would you implement the Stack functionality using the LinkedList class?

By using composition.

NOTE: Everything I wrote above only applies to languages which confuse subtyping and subclassing! The LSP is about subtyping, not subclassing. In a language which does not confuse the two, it would be perfectly acceptable to make Stack a subclass of LinkedList, as long as you do not make it a subtype of LinkedList.

Related Solutions

Design Principles – Violation of the Liskov Substitution Principle?

Yes, it is a violation of the LSP. Liskov Substitution Principle requires that

Preconditions cannot be strengthened in a subtype.
Postconditions cannot be weakened in a subtype.
Invariants of the supertype must be preserved in a subtype.
History constraint (the "history rule"). Objects are regarded as being modifiable only through their methods (encapsulation). Since subtypes may introduce methods that are not present in the supertype, the introduction of these methods may allow state changes in the subtype that are not permissible in the supertype. The history constraint prohibits this.

Your example breaks the first requirement by strengthening a precondition for calling the Close() method.

You can fix it by bringing the strengthened pre-condition to the top level of the inheritance hierarchy:

public class Task {
    public Status Status { get; set; }
    public virtual bool CanClose() {
        return true;
    }
    public virtual void Close() {
        Status = Status.Closed;
    }
}

By stipulating that a call of Close() is valid only in the state when CanClose() returns true you make the pre-condition apply to the Task as well as to the ProjectTask, fixing the LSP violation:

public class ProjectTask : Task {
    public override bool CanClose() {
        return Status != Status.Started;
    }
    public override void Close() {
        if (Status == Status.Started) 
            throw new Exception("Cannot close a started Project Task");
        base.Close();
    }
}

Object-oriented – How to verify the Liskov substitution principle in an inheritance hierarchy

It's a lot more simple than that quote makes it sound, accurate as it is.

When you look at an inheritance hierarchy, imagine a method which receives an object of the base class. Now ask yourself, are there any assumptions that someone editing this method might make which would be invalid for that class.

For example originally seen on Uncle Bob's site (broken link removed):

public class Square : Rectangle
{
    public Square(double width) : base(width, width)
    {
    }

    public override double Width
    {
        set
        {
            base.Width = value;
            base.Height = value;
        }
        get
        {
            return base.Width;
        }
    }

    public override double Height
    {
        set
        {
            base.Width = value;
            base.Height = value;
        }
        get
        {
            return base.Height;
        }
    }
}

Seems fair enough, right? I've created a specialist kind of Rectangle called Square, which maintains that Width must equal Height at all times. A square is a rectangle, so it fits with OO principles, doesn't it?

But wait, what if someone now writes this method:

public void Enlarge(Rectangle rect, double factor)
{
    rect.Width *= factor;
    rect.Height *= factor;
}

Not cool. But there's no reason that the author of this method should have known there could be a potential problem.

Every time you derive one class from another, think about the base class and what people might assume about it (such as "it has a Width and a Height and they would both be independent"). Then think "do those assumptions remain valid in my subclass?" If not, rethink your design.

Best Answer

Related Solutions

Design Principles – Violation of the Liskov Substitution Principle?

Object-oriented – How to verify the Liskov substitution principle in an inheritance hierarchy

Related Topic