# Linked Lists/Java/Single

### 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

Data StructuresThis is the staging ground for computer science notes as part of the 2017 CS Study Plan.
Classes of data structures: Abstract Data Types Array-based and Link-based memory management: ArrayLists and Linked Lists Algorithmic Analysis of Data Structures: Algorithmic Analysis of Data Structures Advanced data structures: Advanced Data Structures
· Template:DataStructuresFlag · e |

ArraysSeries on Data Structures Python: Arrays/Python Java: Arrays/Java Categories: Category:Python Arrays
· Template:ArraysFlagBase · e |

Stacks and QueuesSeries on Data Structures
StacksQueues/Python StacksQueues/Python/LinkedStack
StacksQueues/Java StacksQueues/Java/LinkedStack
Postfix_Expressions#Stacks
· Template:StacksQueuesFlagBase · e |

Priority Queues and HeapsSeries on Data Structures
Priority Queues/Heap
· Template:PriorityQueuesFlagBase · e |

Linked ListSeries on Data Structures
· Template:LinkedListFlagBase · e |

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |

Search TreesSeries on Data Structures
Binary Search Trees Trees/OOP
(Note that heaps are also value-sorting trees with minimums at the top. See Template:PriorityQueuesFlag and Priority Queues.)
· Template:SearchTreesFlagBase · e |

Maps and DictionariesSeries on Data Structures
Maps Map implementations: Maps/AbstractMap Dictionary implementations: Dictionaries/LinkedDict
Hash Maps/OOP Hash Maps/Dynamic Resizing Hash functions: Hash Functions Hash map implementations: Hash Maps/AbstractHashMap
Skip Lists Java implementations: SkipList
Sets
· Template:MapsFlagBase · e |