Implementation of Linked Lists in C++ and Python
Tags: dsa, python, linkedlist, cpp
Published: 2024-02-20 23:30:55

Hi everyone, I'm Mahfuz Hossain, a student of Information and Communication Engineering from Bangladesh. In this article, I'm going to talk about Linked Lists in C++ and Python. Mainly I'll show you the implementation part step by step of Linked Lists in this article.  

A linked list is a linear data structure which can store a collection of "nodes" connected together via links i.e. pointers.

**LinkedList representation:**

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



For theoretical part you can visit [here](https://www.w3schools.com/dsa/dsa_theory_linkedlists.php)  


### **Implementation of Linked List in C++**


####Step one: Defining Node Class

```
class Node
{
public:
  int data;
  Node *next;
  
  //constructor
  Node(int data)
  {
    this->data=data;
    this->next=nullptr;
  }
};
```

So, at the first step I created a class _Node_ which has two member _data_ for storing the value of the node and _next_ for storing the address of another node.
After that, I created a _Node_ constructor which initializes the member variables _data_ and _next_ by using _this_ pointer. To know more about the use of _this_ pointer in C++ you can visit [here](https://www.javatpoint.com/cpp-this-pointer).

####Step two: Creating and connecting Nodes

```
//creating the nodes
Node *head;
Node *node1=new Node(3);
Node *node2=new Node(7);

//connecting the nodes

head=node1;  
node1->next=node2;
```
That's it! We have created the linked list! Now let's understand the code.



Here at first we created the _head_ node and after that two node objects by dynamically allocating their memory using _new_ operator and assigned their addresses to _node1_ and _node2_. 
To know more about _new_ operator in C++ visit [here](https://www.javatpoint.com/difference-between-new-and-delete-operator-in-cpp).

![head and two nodes](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pkzzqvu4w9rbrqy0c9w1.png)




And later on, assigned the address of _node2_ to the _next_ member variable of _node1_. It established the link between _node1_ and _node2_. Also made the _node1_ as the _head_ of the linked list.



![connecting head and nodes](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nxw06y6ohb8vrgp7m7yv.png)


####Step three: Printing the linked list 


```
void printList(Node *node)
{
  while(node != NULL)
  {
    cout<<node->data<<" -> ";
    node=node->next;
  }
  cout<<"NULL";
}
```
the printList function takes pointer as an argument. The while loop will print all the nodes until it encounters an empty node. Inside the while loop the _node_=_node_->_next_ will update the node in each iteration and it will make the node traverse through the entire list. 
##### <u>At the start of the while loop:</u>


![at the start of the loop node is at firs Node](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/53scm8uuprnpn8k2tuhr.png)


##### <u>After the first iteration</u>: 


![After first iteration node is at Second Node](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/op94cnj8c9hieyaq91a3.png)


### So the final code will be: 

```
#include <iostream>

using namespace std;

class Node
{
public:
  int data;
  Node *next;
  
  //constructor
  Node(int data)
  {
    this->data=data;
    this->next=nullptr;
  }
};

void printList(Node *node)
{
  while(node != NULL)
  {
    cout<<node->data<<" -> ";
    node=node->next;
  }
  cout<<"NULL";
}

int main()
{
//creating the nodes
 Node *head;
 Node *node1= new Node(3);
 Node *node2= new Node(7);
 Node *node3= new Node(11);

 
 //connecting the nodes
 head=node1;
 node1->next=node2;
 node2->next=node3;
 
printList(head);

//free the memory
delete head;
delete node1;
delete node2;
delete node3;

return 0;

}
```
here at the last part I deallocated the memory using _delete_ operator to avoid memory leaks. To know more about delete operator you can visit [here](https://www.javatpoint.com/difference-between-new-and-delete-operator-in-cpp).

**The output will be:**

```
3 -> 7 -> 11 -> NULL
```



that's all for C++ now it's time for Python




![Python Logo](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sd1d3xdw6oo12yjpmpt7.png)





##**Implementation of Linked List in Python**

Python is broadly known for it's simplicity, here it is no different when it comes to implementing a Linked list in Python.  

####Step one: Creating Node class

```
class Node:
 def __init__(self,data):
   self.data=data
   self.next=None
```
Here __init__ is a constructor of the class which initializes the data attribute with the provided data argument and sets next to None. To know more about constructor in Python visit [here](https://www.geeksforgeeks.org/__init__-in-python/).

####Step two: Creating and connecting nodes

```
node1=Node(3)
node2=Node(7)
node3=Node(11)

//connecting the nodes
node1.next=node2
node2.next=node3
```
Here I created three Node objects and then connected each node to point to the next node in the desired order. 

####Step three: Printing the list

```
def printList(node):
 while node != None:
   print(node.data," -> ",end="")
   node=node.next
 print("None")
```

So here it will traverse through the list and print the value till the last node. After the last will the _node_ will be assigned the value None and the loop will exit.

#####So the final Python code will be: 

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

def printList(node):
 while node != None:
   print(node.data," -> ",end="")
   node=node.next
 print("None")

node1=Node(3)
node2=Node(7)
node3=Node(11)

//connecting the nodes
node1.next=node2
node2.next=node3

```

The output will be: 

```
3 -> 7 -> 11 -> None
```

That's all from me. Hope this blog was helpful to you. If you have any comments or feedback about this article, please share them. Additionally, I would be happy to provide any assistance or answer any questions you may have regarding the content. Thank you.