If you are learning data structures, a **Linked List** is one of the data structures you should know, albeit not so common, linked lists are similar to *Lists (or arrays)*; you probably never heard or used them until now, but in the right context they prove to be useful.

In this article, you will learn:

- What linked lists are.
- Performance of linked lists.
- Types of linked lists.
- How to Implement your own linked list.

## What are linked lists?

A **linked list** is a sequence of data elements, which are connected together via links. Each element *(node)* in a linked list contains a connection to another data element in form of a pointer.

### You should know:

That every element in a linked list is called a Node, and every node contains a **data** (value to be stored) and **next** (reference to the next node) fields.

A linked list therefore is a collection of nodes, with the last node pointing to `None`

## Performance of linked lists.

In a linked list, the time complexity for the operations is given as:

- Indexing - O(n)
- Insertion - O(1)
- Deletion - O(1)
- Search - O(n)

Space complexity however is O(n).

## Types of linked lists.

There are 3 main types of linked lists;

- Singly-linked lists: Each node consists of only one pointer to the next (which we are learning)
- Doubly-linked lists: Each node contains two pointers, a pointer to the next node and a pointer to the previous node.

- Circular-linked lists: In a circular linked list the last node points to the first node or any other node before it thereby forming a loop

# Implementing a linked list in Python

This comes in 2 parts, creating our list Node, and the Linked List itself. So, first thing first, create a class to represent each *Node* of the linked list

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

*As you can see each node contains just 2 fields, the data, and next*.

Next, create a class to represent your linked list :

```
class LinkedList:
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for n in nodes:
node.next = Node(data=n)
node = node.next
```

### Putting it all together

Let's update each of our classes with a **repr** function so our new code looks like this :

```
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __repr__(self):
return self.data
class LinkedList:
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for n in nodes:
node.next = Node(data=n)
node = node.next
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
```

The code above would rightly allow us to create a linked list, notice that in the LinkedList `init`

function if the node is not passed we initialized it to `None`

.

```
my_list = LinkedList()
firstNode = Node("1")
my_list.head = firstNode
secondNode = Node("2")
firstNode.next = secondNode
print(my_list)
>>> 1 -> 2 -> None
```

### Linked Lists Methods

To help us use our linked lists even more efficiently, we would implement some methods to:

- Traverse a linked list.
- Insert a new node at the beginning.
- Insert a new node at the end.

### Traverse a linked list

Traversing a linked list means iterating through the list, and we add the iter function to allow us to replicate the same behavior from regular lists (arrays)

```
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
```

The code above goes through the list if it does not equal to `None`

and yields every node before re-assigning the node to the `next node`

if it exists.

### Insert node at the beginning

```
def add_at_beginning(self, node):
node.next = self.head
self.head = node
```

In the above code, you're setting the next value to the present head value before re-assigning head to the new node

### Insert node at the end

```
def add_at_end(self, node):
if self.head is None:
self.head = node
return
for current in self:
pass
current.next = node
```

While inserting at the end is similar to inserting at the beginning, first, you want to traverse the whole list until you reach the end. Next, you want to set `current`

as the last node on the list. Finally, you want to add the new node as the next value of that `current`

.

#### Our final code containing our methods should look like this

```
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __repr__(self):
return self.data
class LinkedList:
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for elem in nodes:
node.next = Node(data=elem)
node = node.next
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
# Traverse a Linked List
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
# Insert a new node at the beginning
def add_at_beginning(self, node):
node.next = self.head
self.head = node
# Insert a new node at the end
def add_at_end(self, node):
if self.head is None:
self.head = node
return
for current_node in self:
pass
current_node.next = node
```

To wrap up a final example, have a look at how it works:

```
my_list = LinkedList()
firstNode = Node("1")
secondNode = Node("2")
my_list .head = firstNode
firstNode.next = secondNode
my_list.add_at_beginning(Node("3"))
my_list.add_at_end(Node("4"))
print(my_list)
>>> 3 -> 1 -> 2 -> 4 -> None
```

## Conclusion

In this article, you learned quite a few things, The most important are:

- What linked lists are
- What the other types of linked lists are
- Time and Space Complexities of a linked list
- How to implement your own linked list and node classes, plus relevant methods

I hope you enjoyed reading it as much as I enjoyed writing it :)