Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article at *OpenGenus*, let's understand how to implement a **Linked List** in Python using OOP concepts. First, let's start with a quick recap on linked lists.

## What is a Linked List?

A Linked List is a *data structure* where each element holds 2 pieces of information: it's *value* and the *reference to the next element*. A reference is like a pointer or a clue that tells where to find something.

Imagine that there are many boxes. Each box has something inside it. These boxes are connected to each other with arrows such that each box knows where the next box is. *A Linked List is similar to this arrangement of boxes*. In a linked list, each box, called a node, contains a value and the location of the next box or node.

To find an item in a linked list, we start at the first box (node), look inside the box. Then we follow the arrow to the next box (node) and repeat this till we find the item we're looking for.

Here **Head** points to the first node of the Linked List.

Linked Lists are different from Arrays in the sense that they **dont require fixed space**. We can add and delete elements easily. Also, in arrays, elements are stored in a contiguous way whereas in linked lists it is not the case.

Now, let's understand how to implement a linked list in Python using OOP concepts.

## Node Class

We will first create a class for nodes to represent each node in the linked list. Each node will have 2 properties, it's value and the reference of the next node.

**__init__**initializes a new node with the given value.**next**is originally set as*None*which implies that the node doesn't point to any other node initially.**get_value(self)**returns the value stored in the node, allowing access to the value from outside the class.**get_next(self)**retrieves the reference to the next node in the linked list.**set_next(self, next_node)**sets the reference to the next node. It links the current node to the specified next node.

```
class Node:
def __init__(self, val):
self.val = val
self.next = None
def get_value(self):
return self.val
def get_next(self):
return self.next
def set_next(self, next_node):
self.next = next_node
```

## LinkedList Class

Next, we will create a class for Linked List itself. In the class we will add basic methods for insert, delete, print and search.

**__init__** initializes Linked List with **head**, which points to the first node of the linked list. It is set as *None* because initially, the linked list is empty.

```
class LinkedList:
def __init__(self):
self.head = None
```

We can now add some basic methods to modify the linked list.

### Add at the beginning

In this method, we create a new node with the given value and then set the next attribute of this new node to the current head node. Finally, we update head to point to this new node.

```
def add_at_beginning(self, val):
new_node = Node(val)
new_node.next = self.head
self.head = new_node
```

### Add at the end

In this method, we create a new node with the given value and then set the next attribute of the last node to the new node.

```
def add_at_end(self, val):
new_node = Node(val)
if not self.head:
self.head = new_node
else:
curr_node = self.head
while curr_node.next:
curr_node = curr_node.next
curr_node.next = new_node
```

### Delete method

In this method, we delete the node with the given value. First, we check if the linked list is empty. Then we check if the node to be deleted is the head of the linked list. Finally, we iterate over the list to find the value which if found is deleted.

```
def delete(self, val):
if not self.head:
return
if self.head.get_value() == val:
self.head = self.head.get_next()
return
curr_node = self.head
prev_node = None
while curr_node and curr_node.get_value() != val:
prev_node = curr_node
curr_node = curr_node.get_next()
if curr_node:
prev_node.set_next(curr_node.get_next())
```

### Printing elements of the linked list

In this method, we print the elements of the linked list one by one by iterating over it.

```
def print(self):
curr_node = self.head
while curr_node:
print(curr_node.val,end = " --> ")
curr_node = curr_node.next
print("None")
print("\n")
```

### Searching a value

In this method, we will implement a basic search operation for a given value. We will go through the list till we find the value and return **True**. Otherwise we will return **False** if not found.

```
def search(self, val):
curr_node = self.head
while curr_node:
if curr_node.get_value() == val:
return True
curr_node = curr_node.get_next()
return False
```

### Putting it all together

Now that we have all the methods, we will bring them together and complete our Class definitions for nodes and linked lists.

```
class Node:
def __init__(self, val):
self.val = val
self.next = None
def get_value(self):
return self.val
def get_next(self):
return self.next
def set_next(self, next_node):
self.next = next_node
class LinkedList:
def __init__(self):
self.head = None
def add_at_beginning(self, val):
new_node = Node(val)
new_node.next = self.head
self.head = new_node
def add_at_end(self, val):
new_node = Node(val)
if not self.head:
self.head = new_node
else:
curr_node = self.head
while curr_node.next:
curr_node = curr_node.next
curr_node.next = new_node
def delete(self, val):
if not self.head:
return
if self.head.get_value() == val:
self.head = self.head.get_next()
return
curr_node = self.head
prev_node = None
while curr_node and curr_node.get_value() != val:
prev_node = curr_node
curr_node = curr_node.get_next()
if curr_node:
prev_node.set_next(curr_node.get_next())
def print(self):
curr_node = self.head
while curr_node:
print(curr_node.val,end = " --> ")
curr_node = curr_node.next
print("None")
print("\n")
def search(self, val):
curr_node = self.head
while curr_node:
if curr_node.get_value() == val:
return True
curr_node = curr_node.get_next()
return False
```

Now that we have our complete code, let's see one example to see how to create a linked list and perform basic operations on it in Python

## Example

```
list = LinkedList()
list.add_at_beginning(3)
list.add_at_beginning(2)
list.add_at_beginning(1)
list.print()
list.add_at_end(4)
list.print()
list.delete(3)
list.print()
print(list.search(3))
print(list.search(4))
```

The following will be the output

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

To conclude, in this *OpenGenus* article we implemented a linked list in Python using OOP concepts. We defined a **Node** class to represent each node in the linked list and then we defined a **LinkedList** class to manage the linked list, providing methods to add, delete, search and print elements. You can create your own methods and perform various operations on the linked list using these various methods.