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

title	TARGET DECK	FILE TAGS	tags
Linked Lists	Obsidian::STEM	data_structure::linked_list	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).

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).

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).

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).

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).

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).

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).

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).

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).

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).

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).

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).

END%%

Bibliography

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