Linked Lists (Week 3)

What does a Node contain?

-Data

-Next pointer

-Prev pointer (depends)

Describe “Singly Linked List”

-Null-terminated (at front and tail)

-Head/Tail access

-Only next pointer

Describe “Doubly Linked List”

-Null-terminated (at front and tail)

-Head/Tail access

-Next and Prev pointer

What are Sentinel nodes?

-Dummy nodes that hold no value

-Found at the front and end of list

Advantage of Sentinel nodes?

-Same code for deleting and inserting at beginning and end of list

Difference between Arrays and Linked List?

Arrays have a fixed size and allow random access, while linked lists are dynamic in size and require sequential access.

What is the runtime of Insertion Sort algorithm?

-Average and worst: O(n²)

-Best case (sorted): O(n)