Data Structures Concepts: Lists, Dictionaries, Trees, Graphs

Posted on Jan 21, 2026 in Computer Engineering

Lists

Ordered (different from sorted) and linear.

Duplicates allowed.

Implementation: Array list: good for iteration, resizable; add = slide to right, remove = slide to left to close gap. Linked list: nodes & pointers, no shifting, grows dynamically, good for lots of insertions/deletions.

Core operations: add(newEntry), add(pos, newEntry), remove(pos, newEntry), replace(pos, newEntry), getEntry(pos), contains(entry), toArray(), getLength – numberOfEntries, isEmpty(), clear(). Helper methods: ensureCapacity, makeRoom, removeGap, toArray.

Dictionaries

Concept: Holds key–value pairs. Each key is unique.

Implementations: unsorted array/linked: entries are in no order; searching requires traversal. Sorted array/linked: kept in sorted order by key, allows faster searching; have to shift or adjust pointers when inserting/removing.

Operations (unsorted): add → put entry at back of array / front of linked list. remove → find key by traversal, then remove. getVal = traverse.

Core operations: add, remove, getVal, contains, clear, isEmpty, getSize, key/value iterator (different because of key/value pairs and position matters).

Comparable Interface

Objects can compare themselves using compareTo.

Iterator

An iterator allows easy traversal, may throw UnsupportedOperationException (UOE). Methods: hasNext() = checks if more, next() = returns next, remove() = often disabled because the iterator cannot edit the collection.

Trees

Tree: made up of nodes. Real-world examples (RWE): family tree, computer file systems.

Interfaces: TreeInterface → basic operations; TreeIterator → defines traversal orders; BinaryTreeInterface → adds methods specific to binary trees (setRootData, setTree).

Terminology: root = top node of tree; edge = connection between parent & child node; child = node directly below a parent; leaf = node with no child; subtree = any node & all descendants; height = number of levels.

Traversals: Preorder: Root, Left, Right. Postorder: Left, Right, Root. Inorder: Left, Root, Right (used for BST). Level order: left-to-right by level (uses a queue in implementation).

Remove from BST: no children (leaf) → remove node; one child → remove node & promote child; two children → find largest value in left subtree (rightmost in left), swap value into node being removed, delete the node you took the replacement from. Difference from linear structures: hierarchical, not linear.

Helper Methods

BinaryNode Helpers: getLeftChild(), getRightChild(), setLeftChild(BinaryNode child), setRightChild(BinaryNode child), isLeaf(), copy(), getHeight(), getNumberOfNodes().

BinaryTree Helpers: initializeTree(T rootData, BinaryTree leftTree, BinaryTree rightTree), setTree(T rootData, BinaryTree leftTree, BinaryTree rightTree).

BST Helpers: findEntry(BinaryNode root, T entry), addEntry(BinaryNode root, T newEntry), removeEntry(BinaryNode root, T entry), removeNode(BinaryNode node), findLargest(BinaryNode root), findSmallest(BinaryNode root).

Traversal Helpers: preorderTraverse(BinaryNode node, List list), inorderTraverse(BinaryNode node, List list), postorderTraverse(BinaryNode node, List list), levelOrderTraverse(BinaryNode root).

Efficiencies

Array List (AList): Access by position: O(1). Add at end: amortized O(1) (or O(n) when resizing). Add at position: O(n). Remove at position: O(n). Contains: O(n).

Linked List (LList): Access by position: O(n). Add at end: O(1) if tail reference used, otherwise O(n). Add at position: O(n). Remove at position: O(n). Contains: O(n).

Unsorted Array Dictionary: add: O(1), remove: O(n), getValue / contains: O(n).

Sorted Array Dictionary: add: O(n) (shift to make room), remove: O(n), getValue / contains: O(log n) with binary search (or O(n) worst case if not using binary search appropriately).

Unsorted Linked Dictionary: add: O(1), remove: O(n) (find + bypass), getValue/contains: O(n) (linear traversal).

Graphs

Graph: vertices (nodes) + edges; may have cycles. Directed = edges have direction (arrows). Weighted = edges have values (distances/cost). Undirected = edges have no direction. Unweighted = edges have no value/cost.

Path = sequence of edges connecting vertices; cycles start/end at the same vertex.

Traversals: Depth-First Traversal (DFT): uses a stack, go deep before backtracking (similar to pre-order). Breadth-First Traversal (BFT): uses a queue, level order, layer by layer.

Difference: Trees have no cycles; graphs can. Tree = hierarchical with (usually) one path between nodes; graphs = network-like, can have many paths.

References

Linked List: Head reference → O(1) add/remove at front. Tail reference (if used) → O(1) add at end.

Unsorted Linked Dictionary: Head reference → O(1) insertion.

Array List: numberOfEntries reference → O(1) add at end.

Unsorted Array Dictionary: Head of chain → O(1) add.

Binary Tree / BST: Root reference → O(1) access to the tree, but operations depend on tree height.

Helper Methods (continued)

Unsorted Array Dictionary: linearSearch(K key), ensureCapacity(), removeGap(int index).

Sorted Array Dictionary: locateIndex(K key), makeRoom(int index), removeGap(int index), binarySearch(K key) (if included).

Unsorted Linked Dictionary: findNode(K key), insertAtFront(Node newNode), findPreviousNode(K key), removeFirstNode(), removeAfterNode(Node prevNode).

Sorted Linked Dictionary: findSortedInsertPosition(K key), insertSorted(Node newNode), findPreviousNode(K key).

Quiz

Encapsulation = template of methods that need to be defined. Abstraction = shows essential things to the user. Polymorphism = ability to be flexible and maintain different data behaviors.

Stacks

Stacks: LIFO. Front of list = top, back of array = top of stack. EmptyStackException may be thrown.

Vector: add = back, resizes as needed, can access via index. Program stack: top frame is always running.

Queues

Queues: FIFO structure. Operations: enqueue, dequeue, getFront. Linked queue: first node = front. Priority queue: not FIFO. Deque: uses doubly linked nodes because removal at both ends would be O(n) otherwise.

List Notes

ArrayList = capacity + 1 because array starts at 0 but conceptual list can be 1-based; add = O(n) when shifting entries. LinkedList = sized dynamically, no remove-gap to remove entry; adding a new entry typically goes to the back.

Dictionary Notes

Dictionaries: operations are all based on key. Iterator: hasNext, next, remove (often disabled). Unsorted array: array bags add. Array dictionary remove = array list remove. Linked dictionary data should not be entry due to dereferencing. Unsorted linked dictionary add = linked bag add.