What are the two pieces of data in an individual Linked List node called?
head: (the data value)
tail: (address of next node)
NOTE: When referring to linked list as a whole (not just a single node), it is somewhat common to refer to everything after the head as the tail, including all other later nodes in the list as a part of it.
What are the two most common pointers associated with the entirety of a Linked List?
The head pointer - points to the first node in the linked list
The tail pointer - points to the last node in the linked list, updated with each append
What are the advantages of a Linked List vs a Dynamic Array?
What are the disadvantages of Linked List vs a Standard or Dynamic Array?
The worst-case scenario for a prepend or append operation on a Linked List will not exceed O(1).
The worst-case scenario for the same operations on a Dynamic Array is O(n), especially prepends which involve re-copying the entire populated array.
The lookup for any specific indices on an Array will always be O(1).
The lookup for a specific location in a Linked List will be O(n) because we must traverse the list in order from the beginning to find it.
Additionally, traversing the Linked List is not cache-friendly because each node can be located anywhere in memory.
Last changeda month ago