COMP1850 Lecture 9.2: Linked-List Based Data Structures

Vocabulary flashcards for linked list variations.

Circular Linked List

A linked list where the Tail points back to the Head, creating a continuous traversal.

Applications of Circular Linked Lists

Used for round robin scheduling, turn-based games, and circular/ring buffers in real-time systems.

Doubly Linked List (DLL)

A linked list where each node has two pointers: one to the next node and one to the previous node.

Applications of Doubly Linked Lists

Situations requiring backward traversal, frequent addition/deletion, playlists, prioritized queues, and undo/redo functions.

Stacks and Queues

Specializations of linked lists using a restricted set of operations.

Stack (LIFO)

Last-In-First-Out structure where the last item added is the first item removed.

push()

add a new item at the Top

pop()

remove the Top item from the stack

peek()

view the Top item from the stack

isEmpty()

check whether the stack is empty or not

Queue (FIFO)

First-In-First-Out structure where the first item added is the first item removed.

Uses of Queues

scheduling tasks, buffering data, traversing other data structures

enqueue()

add item to the Back

dequeue()

remove item from the Front

peek()

view the item at the Front

isEmpty()

check if the queue is currently empty

size()

check how many items are in the queue

Stack (Memory)

Memory allocated statically at compile time, managed as a stack.

Heap (Memory)

Memory allocated dynamically at run-time, managed as a linked-list of available chunks.