# 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. 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. ![ll_node.jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1631660678835/wMly27lxq.jpeg) A linked list therefore is a collection of nodes, with the last node pointing to `None` ![ll_fulllist.jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1631661130804/R_HNEHB9C.jpeg) ## 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. ![ll_doubly.jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1631661821627/506epzxdh.jpeg) - 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 ![ll_circular.jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1631662489705/X_m1w1cbD.jpeg) # 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](https://docs.python.org/3/reference/datamodel.html#object.__repr__) 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](https://docs.python.org/3/reference/datamodel.html#object.__iter__) 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](https://docs.python.org/3/reference/simple_stmts.html#yield) 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 :) [Learn more about me](https://abdulqudus.com)