Singly linked lists are heavily used in functional programming, and Lisp is famous for them. The reason why singly linked lists are so neat is that they are an inductive datatype that describes a sequence: A list is either empty or an element followed by a list.
Dynamic arrays can be more appropriate than linked lists, depending on the context. Because dynamic arrays multiply the buffer size by a certain factor upon every reallocation, growth of the array is amortized O(1). In addition, dynamic arrays get the benefit of the cache because the elements are contiguous.
5 comments
[ 3.1 ms ] story [ 22.8 ms ] thread