Arrays VS Linked List Flashcards
(25 cards)
Access/delete time for Arrays
For the last element, O(1)
For any element at index i (i < n), O(n)
Access/delete time for Linked List
If a predecessor is located, O(1)
Locate time for an Array
For an unsorted list, O(n)
For a sorted list, O(log n)
Locate time for a Linked List
O(n)
When should you use an Array?
When size doesn’t change substantially. Arrays have a fixed size upon initialisation
When should you use a linked list?
When the list will grow and shrink. Linked lists have no fixed size
How can you access an element in an Array?
Element at index i can be accessed directly
How can you access a node in a linked list?
When accessing the i-th item, it requires a list traversal from the beginning
How does an array use memory?
It uses an implicit ordering scheme, with items following A[i] being stored as A[i+1]
How does a linked list use memory?
It requires additional memory for references
What is an array efficient for?
Insertion and deletion at the end of the array
What is a linked list efficient for?
Insertion and deletion at the front of the array (locate operation not needed)
What is an issue with implementing a Stack using an array?
Limited size, so there may be problems with pushing an item onto a full stack.
What is an advantage and disadvantage of implementing a Stack using a linked list?
Advantage: ‘unlimited’ size
Disadvantage: extra-memory references
What is the time complexity of the Push and Pop operations of a stack?
Constant time O(1)
When would you use a Stack?
- To reverse or parse data
- Perform backtracking
- Imitate recursion
What happens if the maxLength has been reached on a queue?
The queue is ‘wrapped around’, meaning the location at index 0 is used for enqueue
What is the issue with implementing a Queue as an array?
It will have a limited size, meaning there may be problems with Enqueue if the queue becomes full
What is an advantage and disadvantage of implementing a Queue using a linked list?
Advantage: ‘unlimited size’
Disadvantage: uses extra-memory references
What is the time complexity for the enqueue and dequeue operation for a Queue?
O(1)
What is different about the Priority Queue’s dequeue?
It removes the element with the largest key, which will have been placed first in the queue
What is the time complexity for inserting a new element to an unsorted sequence implemented as an array and linked list?
O(1)
What is the time complexity for inserting a new element to a sorted sequence implemented as an array and linked list?
O(n)
What is the time complexity for deleting an element from an unsorted sequence implemented as an array and linked list?
O(n)
