From charlesreid1

Lists

Singly-linked list:

  • This is covered even in introductory computer science course - the linked list is so important that it is the first data structure that computer science students build that is not part of the API. In Python, these details are so abstracted that even advanced Python users might not know how to implement low-level arrays of memory. (Cython users will though.)
  • The LinkedList class implements a Node class that consists of a single piece of data and a single link to the next node.
  • These classes are often implemented, initially, as storing primitive types like integers, or hard-coding a type for the objects.
  • The next level of abstraction is to implement them as storing a generic Object type. This works fine for simple examples, but in practice it requires messy type-checking and bad abstractions. Okay for older versions of Java.
  • Optimal is to use diamond syntax and write class in terms of templated/generic type. Same idea as templating in C++ (link: Cpp/Templates).

Doubly-linked

  • The Java Collections API implements a doubly-linked list.
  • Double linked list requires buffer nodes header and trailer, or alpha and omega

Abstract Data Type

For more info on abstract data types (ADT) see Abstract Data Types

Flags