I think using existential types will give you data-hiding like this. (Disclaimer: I'm still learning about them, and making up this syntax.) Say my abstract data type is

    DijkstraLib =
    there exists GraphState with {
        construct: List(Edge) -> GraphState
        getDist: GraphState -> Vertex -> Vertex -> Num
    }

Now we can write two different implementations of this type that use a different data structure for graph. The data structure will be opaque to the client (even though the client obtains and passes around graph objects!). Like so:

    -- Library
    type CachingDijkstraLib : DijkstraLib
    with GraphState = (HashMap((Vertex, Vertex), Num), List(Edge))
    with {
        construct(a_list) = (HashMap.empty, a_list)
        ...
    }

    -- Client
    DL = CachingDijkstraLib : DijkstraLib
    some_obj = DL.construct(edge_list)
    DL.getDist(some_obj, u, v)
    DL2 = SomeOtherDijkstraLib : DijkstraLib
    some_other_obj = DL2.construct(edge_list)
    DL2.getDist(some_other_obj, u, v)

The types of some_obj and some_other_obj could be completely different, and neither would be accessible to the client. For example, the client couldn't assume some_obj is a pair and try to get its first element. It would also be an error to call e.g. DL2.getDist(some_obj, ...).

The A in ADT can stand for both abstract and algebraic, so it's an unhelpful abbreviation in contexts where both algebraic and abstract datatypes are relevant.

Functional programming languages tend to have good support for algebraic types (which I think you mean) but they can often do data-hiding too! In Haskell, for example, you do this by not exporting the data constructors for your type, so they can only be used within the module that defines the type.

We do have data hiding in functional programming, even if we would not have modules, which we do, we do have type classes, and for example in OCaml you can hide constructors if that's your jam.

It's not like when I use a sorting function that the implementors couldn't swap it out for a caching one or a parallel one.

One of the amazing things I remember is changing an int to a float in a very well used "struct" that was touching thousands of functions but because the functions in Haskell usually so extremely general I didn't have to change a single other line (Number type is heavily used and doesn't incur an extra performance cost, which it very much does in Java).

In fact we can be even more precise or loose in what assumptions need to be made via dependent types in functional programming languages like Agda.

I encourage you to take a look at any popular Haskell-framework to see how it's done in practice.