notebook/notes/data-structures/linked-lists.md

---
title: Linked Lists
TARGET DECK: Obsidian::STEM
FILE TAGS: data_structure::linked_list
tags:
  - data_structure
  - linked_list
---

## Overview

%%ANKI
Basic
What does it mean for a linked list to be singly linked?
Back: Each entry in the list has a `next` pointer only.
Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
<!--ID: 1715534735171-->
END%%

%%ANKI
Basic
What condition is used to check if a singly linked list is empty?
Back: Its empty if the head of the list is `NIL`.
Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
<!--ID: 1715534735173-->
END%%

%%ANKI
Cloze
The {head} of a linked list refers to {its first element}.
Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
<!--ID: 1715534735177-->
END%%

%%ANKI
Cloze
The {tail} of a linked list refers to {its last element}.
Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
<!--ID: 1715534735180-->
END%%

%%ANKI
Basic
What does it mean for a singly linked list to be circular?
Back: The tail points to the head.
Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
<!--ID: 1715534735184-->
END%%

%%ANKI
Basic
What is the runtime of inserting an element at the front of a singly linked list?
Back: $O(1)$
Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
<!--ID: 1715534735187-->
END%%

%%ANKI
Basic
What is the runtime of finding the $k$th element of a singly linked list?
Back: $O(n)$
Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
<!--ID: 1715534735190-->
END%%

%%ANKI
Basic
What does it mean for a linked list to be doubly linked?
Back: Each entry in the list have `next` and `prev` pointers.
Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
<!--ID: 1715534735193-->
END%%

%%ANKI
Basic
What condition is used to check if a doubly linked list is empty?
Back: Its empty if the head of the list is `NIL`.
Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
<!--ID: 1715534735196-->
END%%

%%ANKI
Basic
What does it mean for a doubly linked list to be circular?
Back: The tail points to the head, and the head points to the tail.
Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
<!--ID: 1715534735199-->
END%%

%%ANKI
Basic
What is the runtime of prepending an element to a doubly linked list?
Back: $O(1)$
Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
<!--ID: 1715534735202-->
END%%

%%ANKI
Basic
What is the runtime of finding the $k$th element of a doubly linked list?
Back: $O(n)$
Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
<!--ID: 1715534735205-->
END%%

## Bibliography

* Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).