What are Linked Lists?

A linked list is a sequence of nodes, where each node stores a value and a reference (or pointer) to the next node.

What's a node? A node, in the context of linked lists, is an object with two global variables. One variable stores a specific value such as an integer or string. The other variable stores a reference to the next node.

• Data variable: Stores the value of the element.

• Reference variable: References the next node of the list.

Linked Lists are good for inserting or removing elements anywhere, and for quickly inserting or removing from the front. But they're bad for finding (searching) a specific element quickly, and they take up more memory than an array.

Linked List Implementation

# Define Node Class
class Node: 
    def __init__(self, val):
        self.val = val
        self.next = None

# Create Node Objects 
a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')

# Link Nodes Together
a.next = b
b.next = c
c.next = d

# Interate Linked List & Print It's Values
def print_list(head):
    current = head
    while current is not None:
        print(current.val) # print value
        current = current.next # update reference

print_list(a)

Linked List Visual Explanation

Creating Nodes

When you make a new object or node in Python like a = Node('a'), it gets stored in this place called the heap. It's like a big pile of memory for you to use. But unlike arrays where all the items are next to each other in memory, items in the heap are all over the place. So, when you make a new object, it goes to an available spot in the heap. And if you don't need it anymore, that spot becomes available again.

The diagram above shows all the created nodes with their associated memory addresses. For example, the node a is at memory location 1010.

Linking By Reference

When you set a.next = b you're not copying b's value into a, you're just storing b's memory address in a. So now a points to the same spot in memory where b is. This way a and b are linked together. This is depicted in the diagram above where there's an arrow from a pointing to b.

That's how you make a linked list! When linking by reference, think of it as giving a post-it note with the address of b, and sticking it on a, so you know where to find b when you ask a for the next value.

Head

The head of the linked list is the first element of the list. So in this example, a is the head of the linked list, it's the starting point where the list begins. It's the first node that you would see if you were to traverse the list. It's like the main entrance or the main gate to access the linked list.

Tail

The tail of a linked list is the last element of the list. It's the last stop, the end of the road, the final destination on the list. You can identify the tail by checking if the .next value of the current element is set to None.

In this example, d is the tail of the list because its next value is set to None, which means you've reached the end of the list and you should stop iterating.

Conclusion

Knowing about linked lists is important for any developer to solve day-to-day problems efficiently. It's also good to know for job interviews because it's a common topic that is often tested! Understanding linked lists will also help you understand more advanced data structures such as trees and graphs.

Thanks for reading!