Implementation of Linked Lists in C++ and Python

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:

For theoretical part you can visit here

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.

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.

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.

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.

At the start of the while loop:

After the first iteration:

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.

The output will be:

3 -> 7 -> 11 -> NULL

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

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.

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.

Comments

[Paul J. Lucas]

You should have an actual slist class that contains the pointer to the head and a second pointer to the tail of the list to make appending an O(1) operation. Additionally, the class should be a template so you can have any type, not just int.

[Md Mahfuz Hossain]

You are right. Basically I've just shown the simple implementation and printing part of the linked list for the beginners. It needs to be modified for insertion, deletion operations.