#   # Implementing a Linked List in Python: Easy as 1,2,3.

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.

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` 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).

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.

``````class LinkedList:
def __init__(self, nodes=None):
if nodes is not None:
node = Node(data=nodes.pop(0))
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

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

def __repr__(self):
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")
secondNode = Node("2")
firstNode.next = secondNode
print(my_list)

>>> 1 -> 2 -> None
``````

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

• Insert a new node at the beginning.
• Insert a new node at the end.

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

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

def __init__(self, nodes=None):
if nodes is not None:
node = Node(data=nodes.pop(0))
for elem in nodes:
node.next = Node(data=elem)
node = node.next

def __repr__(self):
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)

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

# Insert a new node at the beginning

# Insert a new node at the end
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")
firstNode.next = secondNode
print(my_list)

>>>  3 -> 1 -> 2 -> 4 -> None
``````

## Conclusion

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