Data Structure (Types of Linked List)
Tags: algorithms
Published: 2023-03-26 18:15:49

There are different types of linked lists. Basically they are all similar with few details changed so that we can use them regarding our needs. In this section we are gonna learn about,

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

We have already learned singly linked list previously. You can kindly check my previous post if you haven't checked yet. 

Moving on, Circular Linked List is basically the same concept of a Singly Linked List. However, instead of having an end node, we are going to recycle our path to the beginning node.

![Circular01](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jl0tkmfyhpgr0ofvlsay.png)

Instead of keeping our last node's instance variable 'next node' equal to null, we are going to replace it with our beginning node location. 

![Circular02](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/v1zmwkghpiibtdg00dye.png)

Here, we linked our last node with the beginning node. Now, we can call it a circular linked list. Pseudo code is given below for clear understanding.

```
given head

current node = head
while current node.next node is not null {
    current node = current node.next node
}
current node.next node = head
```

How do we find the end node of a circular linked list? We just simply look for head in our current node.

```
while current node.next node is not head {
    get current node.data
    current node = current node.next node
}
get current node.data //getting the data of the last node
```

Moving on to Doubly Linked List. Up till now we learned about one way linked list. Doubly linked list is a two way linked list where I can move forward as well as backwards. 


![DLL01](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vznn09y6dzgnbz7e9jh1.png)

Now, instead of having two instance variable in our node, we are going to have three instance variable. One extra variable for previous location to get backward access.

```
object Node {
    initialising variable (data) {
        data = data
        next node = null
        previous node = null
    }
}
```

Making Link with the nodes. We keep our head's previous node location as null and Move on.


![DLL02](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6g1wfsbdujj7sd2dgsex.png)

Set the previous node value of node two to node one and so on.

![DLL03](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g6s3fv1wv3l8k1w014fs.png)


![DLL04](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/frretceqse43vh7mfoew.png)

Pseudo code is given below for better understanding.

```
given head

current node = head
while current node.next node is not null {
    temporary node = current node
    current node = current node.next node
    current node.previous node = temporary node
}
```
We have successfully created a Doubly linked list. Now anywhere in the middle of our linked list we can have access to our previous nodes. 

You can always make it sufficient in your ways. For example, you can set previous node value when you first time created your linked list and also many other ways.

Now we are left with Doubly Circular linked list. Pretty much same concept of a Circular linked list. Instead of having one way linked, we will now make a cycle with two ways.

![DCLL](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/36h16n2d6kyn9og7nghj.png) 

Here we linked the end node with the starting node and linked the starting node with the end node.

```
given head

current node = head
while current node.next node is not null {
    current node = current node.next node
}
current node.next node = head
head.previous node = current node
```
Congratulations. We have successfully completed different types of linked lists. Later on I will write post about insertion and deletion methods.