<aside> 📚

L3: Point to Where You Are Going — Links covers arrays vs linked lists, amortised analysis of variable-length arrays, singly linked lists (Java implementation, add/remove/search), implementing stacks and queues with linked lists, Java's doubly linked list with dummy node, practical uses of linked lists, and skip lists.

</aside>

📋 At a Glance

• [x] Understand array advantages and disadvantages
• [x] Master amortised analysis of variable-length arrays
• [x] Implement singly linked list operations in Java
• [x] Implement stacks and queues using linked lists
• [x] Understand doubly linked lists and the dummy node trick
• [x] Know when to use linked lists (and when not to)
• [x] Understand skip lists and their complexity

<aside> 📅

Week 2 (w/c 2 Feb) — Lecture 3 of 26 | Tutorial 2 applies

</aside>

<aside> 💡

Key principle: Linked lists are the simplest non-contiguous data structure and serve as a foundation for understanding more complex linked structures like trees and graphs. In practice, arrays are almost always better — but understanding linked lists is essential.

</aside>

1. Arrays: Review and Amortised Analysis

Array properties:

• Uses a contiguous chunk of memory
• Access time is Θ(1) with a very small constant factor
• 95% of the time, arrays give the best performance
• Disadvantages:
  • Fixed length (variable-length arrays exist but at extra cost)
  • Insertion/deletion to/from the middle is Θ(n)

Variable-length array resizing: