Linked List is a linear data structure which consists of group of nodes in a sequence where each node holds its own data and the address of the next node thus forming a chain like structure. They can be used to construct trees, stacks or graphs.

Linked lists may be preferred over normal lists because:

- They allow Stacks and queues to be easily implemented executed
- They are a dynamic in nature thus only allocating memory when required
- They reduces the access time

However, they also require extra memory to store pointers, are difficult to traverse in reverse and it is not possible to access any element randomly thus for simple data it makes more sense to use simple lists.

There are three types of linked lists:

- Singly Linked List
- Doubly Linked List
- Circular Linked List

# 1. Singly Linked

Are the easiest kind of linked list to implement. A node only requires to have its data and the address of the next node

# 2. Doubly Linked

Each node here has its data and two addresses. One address points to the next node in the link while one address points to the previous node.

# 3. Circular Linked

Are similar to singly linked lists where each node holds its own data and the address of the next node except the last node that holds the address to the first node in the link thus forming a complete loop.

## Linked list operations

# Insert

Data can be inserted at the beginning of a linked list, after a node or at the end of the list.

- At the beginning

It is simple and only requires you to create a new node with the data you want to insert . The next variable of the new node is then pointed to the current head of the list. The head of the list is then changed to point to the newly created node.

```
def insert_at_beginning(self, new_data):
#create new node
new_node = Node(new_data)
#point next of the new node to current head
new_node.next = self.head
#point head to the new_node
self.head=new_node
```

- After a node

Requires two inputs: the previous node and the new data. First we check if the previous node exists and raise an exception if it doesn't exist. Then we create a new node with the new data and point its next to the next of the previous node. Last we point the next of the previous node to the new data

```
def insert_after(self,prev_node, new_data):
#check if node exists
if prev_node is Node:
raise Exception('Previous node does not exist')
#create new node
new_node = Node(new_data)
#point next of the new node to prev_node next
new_node.next = prev_node.next
#point next of prev_node to the new_node
prev_node.next=new_node
```

- Insert at the end

This operation takes more steps than the previous two. This is because you have to traverse the entire list till you find a node that has no pointer to the next node (i.e last node in the list), then insert your new node there. First you create a new node then check if the list is empty. If it is empty make the new node the head node of the list. Otherwise traverse the list till you find the last node then point the next of the last node to the new node.

```
# insert at the end of the list
def insert_at_end(self, new_data):
# create new node
new_node = Node(new_data)
# check if list is empty
if self.head is None:
self.head = new_node
return
# traverse list and add to last item on list
last = self.head
while last.next:
last = last.next
# append to end of list
last.next = new_node
```

In the next article we look at the delete and delete method and how to print the entire list. The full code for this article can be found here