Linked Lists have a 1st element, a 2nd element, and so on. This makes them similar to Arrays, but they're structured very differently. Each node in a Linked List has a value `val` and a pointer to the next node `next`. The very start of the Linked List is called the "head". Here's an accurate drawing of a Linked List: People like to use shorthand, so you'll often see them drawn like this instead, with the values drawn inside of the nodes: It's generally slow to read from a Linked List because yo

Linked List

Linked Lists have a 1st element, a 2nd element, and so on. This makes them similar to Arrays, but they're structured very differently.

Each node in a Linked List has a value `val` and a pointer to the next node `next`. The very start of the Linked List is called the "head". Here's an accurate drawing of a Linked List:

\spoiler{

\image{1, 140}
}



People like to use shorthand, so you'll often see them drawn like this instead, with the values drawn inside of the nodes:
\image{2, 90}






It's generally slow to read from a Linked List because you need to start at the first node and step through many other nodes. For example, here's how you read the 4th element in the linked list:

```
head.next.next.next.val # 4
```
\image{3,90}


 
Reading takes worst-case $O(n)$ time, where $n$ is the number of nodes in the Linked List. The same thing holds for writing, inserting and deleting.


\tip3{Read/Write Time} $O(n)$

\tip3{Insert/Delete Time} $O(n)$




So why bother using a Linked List, if they seem slower than Arrays? The idea is that you can quickly  insert and delete an element, if you're already standing at a node in the Linked List.


You can insert quickly if you're standing at a node:


\image{5, 140}



You can also delete quickly if you're standing at a node:



\image{4, 100}



\tip3{Insert/Delete Time} $O(1)$ if you're already standing at the node.










Data Structures

Linked List