Data Structures and Algorithms - Lecture Notes

These flashcards cover key concepts from Data Structures and Algorithms lecture notes, focusing on sorting methods, list implementations, dictionaries, and hashing.

Radix Sort

A sorting algorithm that sorts numbers into buckets without using comparisons.

ADT Sorted List

An Abstract Data Type that stores entries in order determined by their values.

getPosition(anEntry)

Returns a positive position if found, or a negative position where it would be inserted if not found.

LinkedSortedList

A linked implementation of a sorted list with firstNode and numberOfEntries.

Recursive add method

A method that inserts a new entry at the correct spot and rebuilds links as recursion unwinds.

Efficiency Comparison

Compares the efficiency of array-based and linked sorted lists where add, remove, and getPosition are O(n).

SortedList

A class implemented on top of a ListInterface for sorted list operations.

Dictionary

A collection that stores key-value pairs, which may include distinct or duplicated keys.

Dictionaries in Java

Java's Map interface provides operations such as put, get, and remove for key-value mappings.

Hashing

Maps a search key to an array index using a hash function for efficient key lookup.

Load Factor (λ)

Measures how full a hash table is, impacting the performance of dictionary operations.

Rehashing

The process of resizing the hash table and re-inserting all entries when a load factor exceeds the threshold.