Data Structures

Linked List

Lesson

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 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:

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

Read/Write Time O(n)O(n)

Insert/Delete Time O(n)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:

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

Insert/Delete Time O(1)O(1) if you're already standing at the node.

Mark as Completed:
Submits:
test
Test your code to get an output here!