Lists & Arrays
A list is a data structure that stores a value T and a
reference to the next list item (Singly Linked List) or
stores references to both the previous and next list items
(Doubly Linked List).
Typescript Implementation:
export class ListNode<T> {
public value: T;
public next: ListNode<T>;
}An array is a data structure that stores a pre-defined number
of values T.
items: number[]Comparison
The differences between a list and an array are in that
when using an array we have to know how many items we want
to store at allocation time and there are times when this is
inconvenient (possible solution is array resizing), whereas
when using a list we can add items dynamically. The
tradoff is that when using an array, we can access an
element in O(1) time where as when using a list we can
access an element in O(N) time.
| Array | Linked List | |
|---|---|---|
| Cost of accessing elements | O(1) | O(n) |
| Insert/Remove from beggining | O(N) | O(1) |
| Insert/Remove from end | O(1) | O(1) |
| Insert/Remove from middle | O(N) | O(n) |