Linked list single class vs multiple classes

Question

In my second term as an computer science student almost the whole term we have focused on writing linked lists in different variations(stack, queue, ...). The design of these lists always came down to this

class List<T> {
    class ListElement {
        T value;
        ListElement next;
    }
    ListElement root;
}

with variations to which methods were implemented and how they worked (I have left out constructors and properties for simplicity here).

Some day I started learning scala and focusing on functional programming. This also came to the point where a linked list was written but in a different style of implementation.

class List[T]( head: T, tail: List[T])

Despite the different syntax and immutability this is in my opinion a different aproach. And I thought to myself "Well you could have implemented lists the same way in C# or Java with one class less than the aproach you learned".

I can see why you would implement a linked list like that in a functional language where recursion is not as dangerous as in C# or Java because at least for my way of thinking a recursive implementation of all the usual methods on a linked list for this design is very intuitive.

What I do not understand is why are linked lists in C# or Java typically implemented in the first fashion when you could implement them the other way with less code but equal verbosity? (I am not talking about the implementation of lists in the libraries of the language but about the lists you typically write as a programmer to be)

The only benefit I can see with the first approach is that you can hide the implementation from the user a bit better but is this the reason and also is this worth the additional class? I wouldn't even need to expose my implementation to the user as I could still implement my list internally different and maybe only have chosen to have a constructor like that and provide functionality to retreive the first element of the list as head and also the rest as tail.

Answer 1

The reasons for them to be "implemented in the first fashion" as you mentioned include

Performance.

Time and space complexity are the two most important concerns while writing algorithms or implementing data structures that support operations like search and sort. As you have mentioned, the lists created the recursive way aren't mutable! The very purpose of creating a list is attaining faster operations on that. So designers prefer the 'first fashion'.

Object orientation

While solving real world problems, the initial object oriented analysis and design (OOAD) matter a lot. With an object modelling that closely resembles the real world objects/things as much as they can, designers can achieve better solutions. The recursive approach seems to miss out this aspect

Scalability

Designers of APIs/Libraries keep scalability in mind when they draft the designs. A code written in the 'first fashion' is much more scalable, and easy to comprehend.

Other design concerns

This is not an exhaustive list of the reasons in any way. There are so many other factors and experience based learning that exist in the programming folklore, that lead to the choice of the first fashion.