Even if linked lists and double linked lists aren't all that universally useful by themselves, they teach all the basics about taversing data structures by refe

Even if linked lists and double linked lists aren't all that universally useful by themselves, they teach all the basics about taversing data structures by references / pointers that more complex trees and graphs require. A linked list is just a degenerate tree with at most one child for each parent. So I think teaching that isn't a bad decision.