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) time, where n is the number of nodes in the Linked List. The same thing holds for writing, inserting and deleting.
Read/Write Time O(n)
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:
You can also delete quickly if you're standing at a node:
Insert/Delete Time O(1) if you're already standing at the node.
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()