Linked List Data Structure

A linked list is a data structure that is made up of a group of nodes that are connected to eachter.

A node often contains:

Some data.
A pointer to the next node in the linked list.

The head of the linked list is a pointer to the first node in the list.

While the tail of a linked list is a pointer to the last node

Here's an example of a linked list of numbers:

Example of a Linked List with a head and tail

Implementation

In Python, the above linked list can be implemented below:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


node_1 = Node(2)
node_2 = Node(3)
node_3 = Node(8)
node_4 = Node(6)

head = node_1
node_1.next = node_2
node_2.next = node_3
node_3.next = node_4
tail = node_4

# Print the first 2 and last node
print(head.data)
print(head.next.data)
print(tail.data)

1class Node:
2    def __init__(self, data):
3        self.data = data
4        self.next = None
5
6
7node_1 = Node(2)
8node_2 = Node(3)
9node_3 = Node(8)
10node_4 = Node(6)
11
12head = node_1
13node_1.next = node_2
14node_2.next = node_3
15node_3.next = node_4
16tail = node_4
17
18# Print the first 2 and last node
19print(head.data)
20print(head.next.data)
21print(tail.data)
22

We are left with head and tail to access data in the linked list.

Linked List Big O Overview

Operation	Time
Insert	O(n)
Append	O(1)
Prepend	O(1)
Delete	O(1)
Lookup	O(n)

Note to get to another node, for example the third node, we must iterate through each node's next pointer until we reach the third one.

Linked List Pros

Append to the end of the list in constant time

new_node = Node(data)
tail.next = new_node
tail = new_node

Similarly, prepend in constant time

new_node = Node(data)
new_node.next = head
head = new_node

A linked list doesn't need a preset size since new nodes can be added any time.

Linked List Cons

The main con with a linked list is that accessing any other node costs O(n) time.

Another con is that since nodes in the list aren't necessarily in contiguous location in memory, which makes it not cache-friendly.

8 Essential Linked Lists Coding Interview Problems

Master Linked Lists by trying the coding challenges below.

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.