In computer science, you can store a list of items in two ways, either at contiguous memory locations or at random memory locations.

If you store items at contiguous memory locations, we can access all the items if we know the memory location of the first item. For example, arrays or lists use contiguous memory locations to store a list of items.

A **linked list** is a linear data structure in which the items get stored at random memory locations. Each memory location of a linked list is called a **node**. These nodes are linked together using pointers.

Since the items are at random locations, we need to store the address of the next item in the current node. Hence, each node contains two fields; a data value to store the data of the current node and a pointer that stores the address of the next node.

The last node of the linked list contains a pointer that points to NULL. The **head **is a pointer that keeps a reference to the first element of a linked list.

Here is a pictorial representation of a linked list. This linked list has three nodes with values A, B, and C.

Linked list achieves optimized utilization of space since the nodes can reside anywhere in the memory. Also, you don’t need to define the size of a linked list in advance as it allocates the memory dynamically. These are some advantages of using linked lists over arrays.

If you haven’t understood the working of linked lists clearly, check out the following video.

## Linked List Implementation using Python

Let’s implement linked lists using the Python programming language. We can create a class called *Node*, and whenever we want to add a node to the linked list, we can create an object of this class. This class will have two attributes: *data *and *next*.

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

Now, let’s create a class called *LinkedList*. We can create an object of this class to create a linked list. This class will have one attribute called *head*, which can be used as a pointer.

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

### Inserting nodes

Let’s create a linked list and insert some nodes into it using Python. You can do insert nodes at the beginning of the linked list, end of the linked list, or after a specific node. We will see the Python code for inserting nodes in all three ways.

#### Inserting at the beginning of a linked list

```
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insertAtBeginning(self,new_value):
new_node = Node(new_value)
new_node.next = self.head
self.head = new_node
print("New node inserted with data",new_value)
lList = LinkedList()
lList.insertAtBeginning(5)
lList.insertAtBeginning(7)
```

#### Inserting at the end of a linked list

```
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insertAtEnd(self,new_value):
new_node = Node(new_value)
if self.head is None:
self.head = new_node
print("New node inserted with data",new_value)
return
last_node = self.head
while(last_node.next):
last_node = last_node.next
last_node.next = new_node
print("New node inserted with data",new_value)
lList = LinkedList()
lList.insertAtEnd(2)
lList.insertAtEnd(4)
```

#### Inserting after a specific node

I have inserted a node using the *insertAtBeginning* method so that the previous node can’t be empty.

```
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insertAtBeginning(self,new_value):
new_node = Node(new_value)
new_node.next = self.head
self.head = new_node
print("New node inserted with data",new_value)
def insertAfter(self,prev_node,new_value):
if prev_node == None:
print("Previous node is empty")
new_node = Node(new_value)
new_node.next = prev_node.next
prev_node.next = new_node
print("New node inserted with data",new_value)
lList = LinkedList()
lList.insertAtBeginning(5)
lList.insertAfter(lList.head,8)
lList.insertAfter(lList.head,3)
```

### Traversing the linked list

In traversing, we visit each node of the linked list to perform some operation on it, for example, printing the data present in each node. Let’s see how we can print all the data values in the linked list.

```
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insertAtBeginning(self,new_value):
new_node = Node(new_value)
new_node.next = self.head
self.head = new_node
print("New node inserted with data",new_value)
def printLinkedList(self):
temp = self.head
while(temp):
print(temp.data)
temp = temp.next
lList = LinkedList()
lList.insertAtBeginning(5)
lList.insertAtBeginning(1)
lList.insertAtBeginning(9)
lList.printLinkedList()
```

### Deleting a node from the linked list

Let’s see how we can delete a node from a linked list. This can be done in many ways. But we are not going to try all those different ways.

Here, we will simply create a method that accepts a value and delete the node that contains that value.

```
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insertAtBeginning(self,new_value):
new_node = Node(new_value)
new_node.next = self.head
self.head = new_node
print("New node inserted with data",new_value)
def printLinkedList(self):
temp = self.head
while(temp):
print(temp.data)
temp = temp.next
def deleteNode(self,key):
temp = self.head
if(temp==None):
print("Can't perform deletion")
return
while(temp != None):
if(temp.data == key):
break
prev = temp
temp = temp.next
prev.next = temp.next
temp = None
print("1 node deleted with data",key)
lList = LinkedList()
lList.insertAtBeginning(5)
lList.insertAtBeginning(1)
lList.insertAtBeginning(9)
lList.deleteNode(1)
lList.printLinkedList()
```

### Reversing a linked list

Let’s see the Python code to reverse a linked list.

```
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insertAtBeginning(self,new_value):
new_node = Node(new_value)
new_node.next = self.head
self.head = new_node
print("New node inserted with data",new_value)
def printLinkedList(self):
temp = self.head
while(temp):
print(temp.data)
temp = temp.next
def reverseLinkedList(self):
prev = None
curr = self.head
while(curr is not None):
next = curr.next
curr.next = prev
prev = curr
curr = next
self.head = prev
print("LinkedList reversed")
lList = LinkedList()
lList.insertAtBeginning(5)
lList.insertAtBeginning(1)
lList.insertAtBeginning(9)
lList.printLinkedList()
lList.reverseLinkedList()
lList.printLinkedList()
```

### Delete a linked list

Now let’s try to write a method that deletes the entire linked list when it gets called.

```
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insertAtBeginning(self,new_value):
new_node = Node(new_value)
new_node.next = self.head
self.head = new_node
print("New node inserted with data",new_value)
def deleteLinkedList(self):
curr = self.head
while curr:
temp = curr.next
del curr.data
curr = temp
print("LinkedList deleted")
lList = LinkedList()
lList.insertAtBeginning(5)
lList.insertAtBeginning(1)
lList.insertAtBeginning(9)
lList.deleteLinkedList()
```

I hope this article was helpful to you. Check out my articles on queue and stack data structures in Python.