Data Structures: Lists and Implementations

Vocabulary flashcards covering List ADT concepts, Array Lists, Singly Linked Lists, Circular Linked Lists, and Doubly Linked Lists along with their operations and runtimes.

List ADT

An abstract data type specifying an ordered data structure of items in a contiguous, 0-aligned fashion with no gaps starting at index 0, defining behavior rather than implementation details.

Array List

A List ADT implementation that stores data contiguously in a backing array starting at index 0.

Size (Array List)

The total number of elements currently stored inside an Array List.

Capacity (Array List)

The total length of the backing array allocated for an Array List.

Amortized Time Complexity

The average time spent per operation over a sequence of calls, such as $O(1)^*$ for Array List Add Back, where rare $O(n)$ resizing operations are spread out over many fast operations.

Array List Add Front

An operation that shifts all existing elements forward by one index to insert a new element at index 0, requiring $O(n)$ time.

Array List Remove Back

An operation that decrements the size variable and replaces the last element with null for security and garbage collection, running in $O(1)$ time.

Node (Singly Linked List)

A fundamental building block of a linked list containing data (T data) and a reference pointer to the next node (Node<T> next).

Singly Linked List with Tail

A linked list implementation storing data in a chain of nodes while maintaining explicit pointers to both the head and tail nodes.

SLL Add Front

An operation that creates a new node, sets its next pointer to the current head, and updates the head pointer to the new node, running in $O(1)$ time.

SLL Add Back

An operation that uses the tail pointer to attach a new node after the current tail node and updates the tail reference, running in $O(1)$ time.

SLL Remove Back

An operation that iterates from head to the second-to-last node to update the tail pointer, running in $O(n)$ time because a singly linked list lacks a pre-tail pointer.

Circular Linked List (CLL)

A variant of a linked list where the next pointer of the last node points back to the head node, eliminating the need for a tail pointer.

CLL Add Back

An operation performed in two steps by calling Add Front and then moving head to head.next, operating in $O(1)$ time.

CLL Remove Front

An operation that overwrites the head node's data with data from the second node and points head.next to the third node (head.next.next), executing in $O(1)$ time.

Applications of Circular Linked Lists

Non-stop looping applications such as media playlists and traffic light state machines.

Doubly Linked List Node (DLLNode)

A node structure containing T data, a reference pointer to the next node (DLLNode<T> next), and a reference pointer to the previous node (DLLNode<T> prev).

DLL Remove Back

An operation that updates tail = tail.prev and sets tail.next = null so the garbage collector can reclaim the old tail, taking $O(1)$ time.

DLL Add At Index

An operation that instantiates a new node and rearranges next and prev pointers of adjacent nodes, requiring $O(\frac{n}{2}) \rightarrow O(n)$ time in the worst case.

Get At Index (Array List vs SLL)

An operation executing in $O(1)$ time for Array Lists via direct indexing, but requiring $O(n)$ traversal time for Singly Linked Lists.