Linked List Variants Flashcards
(24 cards)
Array (int) Memory
4n
(4 bytes per int)
Singly Linked List (SLL) (int) Memory
(4+8)n
4 (int) + 8 (next pointer) = 12 bytes per node
(data + next pointer)
Doubly Linked Lists (DLL) (int) Memory
(4+16)n
4 (int) + 8 (next) + 8 (prev) = 20 bytes per node
(data + next + prev pointer)
Linked Lists Space
No unused space (only nodes you need)
Dynamic Array Space
Usually half unused after resize
Array Space
Fixed size, can waste space
What are the running times for Singly Linked List (SLL)? (IF, RF, IB, RB)
Insert Front (IF): O(1)
Remove Front (RF): O(1)
Insert Back (IB): O(n)
Remove Back (RB): O(n)
What are the running times for SLL with Tail? (IF, RF, IB, RB)
Insert Front (IF): O(1)
Remove Front (RF): O(1)
Insert Back (IB): O(1)
Remove Back (RB): O(n)
What are the running times for Doubly Linked List (DLL)? (IF, RF, IB, RB)
Insert Front (IF): O(1)
Remove Front (RF): O(1)
Insert Back (IB): O(1)
Remove Back (RB): O(1)
What are the running times for DLL with Tail? (IF, RF, IB, RB)
Insert Front (IF): O(1)
Remove Front (RF): O(1)
Insert Back (IB): O(1)
Remove Back (RB): O(1)
What are the running times for DLL Circular?
Insert Front (IF): O(1)
Remove Front (RF): O(1)
Insert Back (IB): O(1)
Remove Back (RB): O(1)
What are the running times for SLL Circular without Tail?
Insert Front (IF): O(n)
Remove Front (RF): O(n)
Insert Back (IB): O(n)
Remove Back (RB): O(n)
What are the running times for Static Array? (IF, RF, IB, RB)
Insert Front (IF): O(n)
Remove Front (RF): O(n)
Insert Back (IB): O(1)
Remove Back (RB): O(1)
What are the running times for Dynamic Array? (IF, RF, IB, RB)
Insert Front (IF): O(n)
Remove Front (RF): O(n)
Insert Back (IB): O(1/n)
Remove Back (RB): O(1/n)
What are the pros and cons of Singly Linked List (SLL)?
Pros: Simple, low memory usage.
Cons: Slow back insert/remove.
What are the pros and cons of SLL with Tail?
Pros: Fast insert at back.
Cons: Still slow remove at back.
What are the pros and cons of Doubly Linked List (DLL)?
Pros: Fast both ends (insert/remove).
Cons: More memory (prev pointers needed).
What are the pros and cons of DLL with Tail?
Pros: Perfect for deques (push/pop both ends fast). Cons: Slightly more complexity.
What are the pros and cons of DLL Circular?
Pros: Traverse endlessly, no nullptr ends. Cons: Management slightly trickier.
What are the pros and cons of Static Array?
Pros: Fast random access. Cons: Fixed size, wasted space.
What are the pros and cons of Dynamic Array?
Pros: Grows automatically, random access fast. Cons: May waste half memory, resizing slow sometimes.
Which data structures are best for implementing a Stack (LIFO)?
Singly Linked List (SLL)
Doubly Linked List (DLL)
Static Array (push/pop at back)
Dynamic Array (push/pop at back, amortized O(1))
Which data structures are best for implementing a Queue (FIFO)?
Singly Linked List with Tail
Doubly Linked List with Tail
(Dynamic Array acceptable for small queues)
Which data structures are best for implementing a Deque (Double-Ended Queue)?
Doubly Linked List with Tail
Doubly Linked List Circular
(Dynamic Array possible but less ideal due to shifting elements)
