A linked list is a linear data structure where each element is a separate object.

Singly Linked List

• Each node contains a value and a reference field to link to the next node.

Access an element => O(n)

• Unlike the array, we are not able to access a random element in a constant time, we have to traverse from the head one by one => O(n)

Add/Delete => O(n) to find prev, O(1) to add an element after

To ad an element (unlike the array), we only need a ref to prev (O(n)), we can then have next point to the new element and element->next point to prev->next.

• Add at the end is O(n) unless we store the tail.
• Add at k is O(k) since we have to go find k.

Doubly Linked List

Each node of this list has a val, a next, and a prev.

2PT