# Linked List

Arrays are like buckets that hold values.

### How to insert a node at the beginning of a Linked List?

```
class ListNode {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
function insertAtBeginning(head, newValue) {
const newNode = new ListNode(newValue);
// Set the next of the new node to the current head
newNode.next = head;
// Update the head of the linked list to be the new node
head = newNode;
return head;
}
// Example linked list: 1 -> 2 -> 3
let head = new ListNode(1, new ListNode(2, new ListNode(3)));
// Insert a new node with value 0 at the beginning
head = insertAtBeginning(head, 0);
```

## Intro

Store value of different type (in JS) at contiguous memory location. Strings are arrays as well.

### Advantages

- Fast access if you have index

### Disadvantages

- Adding or removal from the middle is slow, opposed to Linked List.

## Terms

- Subarray, [1,4,5,2] -> [4,5,2] is a subarray
- Subsequence, [1,4,5,2] -> [1,4,2] is a subsequence

The difference is that a subarray can't have any element in between, it has to be contiguous. A subsequence can be derived from the original array by deleting elements, but the order has to stay the same

## Time Complexity

- Access: O(1)
- Search: O(n)
- Search sorted: O(log n)
- Insert: O(n)
- Insert at the end (.push()): O(1)
- Remove: O(n)
- Remove at the end (.pop()): O(1)

## Look out for in interview

- Are there duplicates in the array? Would this affect the answer?
- Remember the bounds when using indexes
- .slice() and .concat() need O(n) time, prefer subarray

## Corner Cases

- Empty sequence
- Duplicates
- Sequence with repeated elements
- Sequence with 1 or 2 elements

## Techniques

Sliding Window - Subarray / Substring

Two Pointers