DS: Singly Linked List in Python
Tags: python, datastructures, algorithms, linkedlist
Published: 2020-06-26 07:42:11

| | |
-|-|-|-|
1 |[__Singly Linked List__](https://dev.to/irfanbaigse/ds-singly-linked-list-in-python-2j7l-temp-slug-4202313)|
2 | __Doubly Linked List__ |
3 | __Circular Linked List__ |

# What is a linked list?

Linked list a data structure used to store and access a collection of data in a formatted way.

They are various types of linked list

* Singly Linked List
* Doubly Linked List
* Circular Linked List
* ...

We will discuss each one in a different post.

# Singly Linked List

This list consists of a number of nodes in which each node has a pointer pointing to the next element/item. The last element/item points to null.


![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/eg5vji073pljybxqq9cq.png)


## Basic Operations on any list

* Traversing the list (display or find)
* Add item to head or beginning (append)
* Add item to tail or end (prepend)
* Add item after particular item (insertAfter)
* Delete a given item (delete)

Let us implement singly using python language.

---

Node is the smallest item in the list which holds data and pointer

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/z6rcy38d6sx64qs966yt.png)

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

---

##### Linked list class

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

`self.head` stores the starting point of the list.

### Traversing the list 

We have to get the starting point from `self.head` then loop over each element until we reach null.

```python
    def display(self):
        currentNode = self.head
        while currentNode:
            print(currentNode.data)
            currentNode = currentNode.next
```

### Add item to head or beginning

let's add the first item to the list. 

```python
def append(self, data):
        newNode = Node(data)
        self.head = newNode
        return;

llist = LinkedList()
llist.append("A")
llist.display() # A
```
The above `append` method holds good for the first time you add an element to the list, what if you want to add another item to the list?

### Add item to tail or end

Modifying the `append` method to suit our new requirement will look like this

```python
    def append(self, data):
        newNode = Node(data);
        if self.head is None:
            self.head = newNode
            return;
        lastNode = self.head
        while lastNode.next:
            lastNode = lastNode.next
        lastNode.next = newNode;

llist = LinkedList()
llist.append("A")
llist.append("B")
llist.display() # A B
```

we have to first check if the head is already set or not? In our case, we have already added the item "A". It will move forward to the next block of code which is traversing the list to find the last item `item.next` until we reach the end of the list.

Add the new node to the `lastNode.next` and the flow ends there.

### Add item after a particular item

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/fnmd076530vht09czsg6.png)

As you can see from the above diagram. In order to insert an element in the middle, we have to do certain operations in a step by step manner.

* Check if a given node is not empty
* Create a new node
* New node to copy the next pointer from the previous node
* Update the previous node next pointer to point our new node

Below program will help you do it.

```python
def insertAfter(self, previousNode, data):
        if not previousNode:
            print('send prev node')
            return

        newNode = Node(data)
        newNode.next = previousNode.next
        previousNode.next = newNode

llist = LinkedList()
llist.append("A")
llist.append("B")
llist.insertAfter(llist.head.next,"C")
llist.display() # A C B
```

## Removing an item from the list

I will leave this section for you to complete and you can answer in the comment section.

The complete file can be found [here](https://gist.github.com/irfanbaigse/6b43ec551cef69afd5ef91dc703280ef)

This explains basic operation on the linked list. As you could see the list can increase on runtime and ease of access.

In the next post, we will discuss the doubly linked list and its advantages over the singly linked list.

Thank you for passing by ;)
If you have any comments or questions please use the comments section below.