Linked Lists, Stacks and Queues Study Notes

Topic 5 – Linked Lists, Stacks, and Queues
  • Covers dynamic data structures including linked lists, stacks, and queues.
  • Explores differences between array and linked implementations.
Last Lecture Review
  • Analysis of Algorithms
  • Importance of time vs. space complexity.
  • Understanding Big O notation for measuring algorithm efficiency.
  • Iterators
  • Discussed the Iterable and Iterator interfaces in Java.
  • Memory Management in Java
  • Types of references: pointers vs. pass-by-value/reference.
  • Importance of garbage collection in memory management.
Assessment Items
  • Assignment 1: Vehicle Rental Service (15%)
  • Due on Canvas by Sunday 6 April at 23:59.
  • For extension requests, follow institutional procedures on adverse circumstances.
  • Mid-Semester Test: (10%)
  • Duration: 60 minutes with multiple-choice questions.
  • Scheduled for Monday 7 April during lecture, includes GPAS responses.
  • Permitted materials: 1 page of A4 double-sided notes; no devices allowed for SENG1120.
Chapter Objectives (Linked Lists, Stacks, and Queues)
  • Differentiate linked lists, stacks, and queue ADTs.
  • Perform operations on linked list elements, stacks, and queues.
  • Implement both array-based and list-based stacks and queues.
Linked Lists
  • Definition: A dynamic, linear abstract data type (ADT) where each element (node) points to the next.
  • Key Components:
  • Head Pointer: Points to the first node.
  • Tail Pointer: Points to the last node.
  • Null Reference: Indicates non-existent objects.
  • Insertion: Requires careful pointer adjustments to maintain structure integrity.
  • Types:
  • Singly Linked List: Nodes connected in one direction.
  • Doubly Linked List: Nodes have pointers to both next and previous nodes.
Advantages of Linked Lists
  • Flexibility in dynamic memory allocation compared to fixed arrays.
  • Support for constant-time unsorted insertion without predefined length requirements.
Common Linked List Operations
  • Insertion:
  • Can occur at the beginning, end, or an arbitrary index.
  • Deletion: Process must be meticulous to prevent pointer errors.
  • Merging/Joining: Linked lists can be merged efficiently.
Sentinel Nodes
  • Special nodes used to simplify edge cases during linked list operations (head and tail).
  • They help maintain a continuous list structure, eliminating null references.
Stacks
  • Structure: Like a linked list but adheres to LIFO (Last-In-First-Out) principle, elements are added/removed from one end only.
  • Key Operations: push for insertion and pop for deletion.
  • Utilizes policies to determine order of operations (FIFO for queues vs. LIFO for stacks).
  • Common uses include managing function calls (call stack) and browser history.
Queues
  • Definition: A linear data structure that follows FIFO (First-In-First-Out) principle.
  • Operations: enqueue for adding elements and dequeue for removing elements. Includes a peek operation to access the front element without removal.
  • Applications in scheduling tasks, managing print jobs, and handling customer service requests.
Implementation of Stacks and Queues
  • Array-Based Implementation: Utilizes arrays to back stacks and queues, though may involve element shifting.
  • Deque: Allows insertion/removal at both ends, enabling versatility for various data operations, applicable in sliding windows and task scheduling.
Where they are Used
  • Linked Lists: Common in applications requiring dynamic data, like music playlists or memory management.
  • Stacks: Found in undo functionalities, expression evaluations, and history management.
  • Queues: Used in print queues, customer service systems, and process execution tasks.