Linked Lists Flashcards
1
Q
Basics
A
- Very similar to an array, but different in how they are stored in memory
- Besides the value of a linked list, a node also has a pointer to the next element:
- The value is stored in some memory slot
- The pointer is stored in the next memory slot to the value (a back-to-back slot). Points to anywhere in memory (not a back-to-back memory slot) that has the value of the next node
- The final node points to a null address, so the memory slot next to the final value is a null address
2
Q
Singly Linked List
A
- When every node has one pointer to the next node
- Has two properties: value and next
- The first element is referred to as the head
- The last element is known as the tail, whose next property points to null
- Typically only exposes its head to the user
3
Q
Doubly Linked List
A
- When every node has two pointers, one to the previous node, and the other to the next node
- Has three properties: value, prev, and next
- The first element is referred to the head, whose prev property points to null
- The last element is known as the tail, whose next property points to null
- Exposes its head and tail to the user
4
Q
Circular Linked List
A
- It has no clear head or tail because its tail points to its head, forming a closed circle
- Can be a singly circular linked list or a doubly circular linked list
5
Q
Space-time complexities 1
A
- Getting and setting an element depends on the node position and type of linked list:
* The head: O(1) T, O(1) S
* The middle: O(N) T, O(1) S
* The tail: O(N) T in singly, O(1) T in doubly, O(1) S - Initializing a linked list is a linear operation. It’s O(N) ST
- Built-in operations that traverse a linked list have the same space-time complexities as the traversing operation. It’s O(N) T, O(1) S
6
Q
Space-time complexities 2
A
- Copying a linked list is a linear operation. It’s O(N) ST
- Inserting and removing a value in a linked list depends on the node position and type of linked list:
* The head: O(1) T, O(1) S
* The middle: O(N) to access + O(1) T, O(1) S
* The tail: O(N) to access + O(1) T in singly, O(1) T in doubly; O(1) S