The skip list is composed of multiple node layers, the nodes are linked with different jump between the values so you can quickly find your desired value.
| Condition | Access | Search | Insertion | Deletion |
|---|---|---|---|---|
| Average | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) |
| Worst | O(n) | O(n) | O(n) | O(n) |