13

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?

  • 6
    The question What would be the disadvantage to defining a class as a subclass of a list of itself? asks about a slightly different problem, but most of the answers apply here as well: you're better of creating a Stack with a List as private member rather than inheriting from List. – amon Dec 13 '17 at 12:35
  • 7
    Yes this is a bad design since it will prevent you changing the internal representation of the stack to something other than a linked list (e.g. an array). You're also exposing operations which stacks do not usually support. Use composition instead of inheritance. – Lee Dec 13 '17 at 12:38
  • 2
    Do you want to extend LinkedList? You may want to heed the advice of a certain Joshua Bloch (who played a major role in designing the Java collections framework) when he said "Prefer composition over inheritance" - Maybe have a LinkedList inside your stack class, but not actually extend it? – corsiKa Dec 13 '17 at 16:53
  • 1
    I'd say it cannot satisfy the Liskov substitution principle, because "a stack is a kind of linked list" is not a true statement. "Stack" is really an interface (I mean conceptually, not the Java construct). A stack can be implemented with a linked list. Like others have said, you would use a private data member of type LinkedList that does the heavy lifting behind the scenes (composition). That way users of your code can't accidentally use a Stack where they needed a List or vice versa. – Jasmijn Dec 13 '17 at 19:17
  • 1
    It seems what would be saner would be the opposite. If I were doing this I would probably have a linked list class implement a "stack" interface as its fully capable of doing so. Otherwise this is the wrong way around as a stack is a concept, a linked list is an implementation which can act as a stack among other things. – Vality Dec 13 '17 at 21:09
31

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.

  • 9
    What is the History Rule? I failed to find it in the internet. – Zapadlo Dec 13 '17 at 13:44
  • 10
    When manipulating an object of a subtype, and observing it through methods of the supertype, it must be impossible to observe a history that could not also be observed with an object of the supertype. This rule ist the one that makes the LSP applicable to non-functional languages. All the other stuff had already been known long before that. The pre- and postcondition rules are reformulations of the co- and contravariance rules for function types. The history rule makes all of this applicable to mutable data. Without it, the LSP would only be useful for purely functional languages. – Jörg W Mittag Dec 13 '17 at 13:49
  • 2
    I think the explanation in the Wikipedia article is reasonably good: wikipedia.org/wiki/Liskov_substitution_principle But as always, you should really read the original source. – Jörg W Mittag Dec 13 '17 at 14:01
  • @JörgWMittag: While I would think it reasonable for types to include in their contract guarantees about what "history" will or will not be observed, I don't think that it should be necessary that every supertype be capable of producing every sequence of observations that might be possible on an object of the subtype--merely that the supertype document the possibility that consumers of the supertype might observe such sequences. – supercat Dec 13 '17 at 17:25
1

Since everything was already addressed by Jörg W Mittag, I just elaborate a bit on the following part:

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

Basically, when there is a question whether some hierarchy violates LSP, it depends on what contract you pose. So, what contract does add_after have? If it sounds, however crazy, like "Add a node at the n-th position or at the top", than you're fine, the post-condition is met, LSP is not violated. Otherwise it's an LSP violation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.