How to iterate through a doubly linked list Python

Python Linked List: Create a doubly linked list, append some items and iterate through the list

Last update on January 04 2021 14:03:01 (UTC/GMT +8 hours)

Table of Contents Show

Python Linked List: Create a doubly linked list, append some items and iterate through the list
Doubly Linked List (Python Code with Example)
Defining a LinkedList
Linked Lists vs Arrays
Types of Linked Lists
Singly Linked List
Circular Singly Linked List
Doubly Linked List
Circular Doubly Linked List
Creation of Singly Linked List
The iterator function
Insertion in Singly Linked List
Insertion Algorithm
Linked Lists in Python: An Introduction
Make a loop at k-th position in a linked list

Doubly Linked List (Python Code with Example)

Ctrl+Z, can you even survive a day without these keys? Well, Apparently not, undo and redo features are one of the used functionalities in computer engineering. But have you ever thought about how is it even possible? I happen to have an answer this time! Undo and Redo functionality is one of the most important applications of a doubly linked list. So what exactly is a doubly linked list? Before that let’s have a quick glance at Linked List:

Defining a LinkedList

You already have a basic idea of what a LinkedList is, and how it works, but I’ll reiterate for clarity:

According to this GeeksForGeeks article…

a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list

With this in mind, let’s talk about how to actually iterate through one.

Linked Lists vs Arrays

Linked List	Array
Linked lists have a dynamic size, i.e., they can be changed at runtime.	The size of an array can not be altered at runtime.
Memory is allocated at runtime.	Memory is allocated at the time of compilation.
The linked list uses more memory as each node holds a reference to the next one as well.	For the same number of elements, arrays use less memory.
Accessing elements is more time consuming	Accessing elements is less time consuming
Operations such as insertion/deletion are faster.	Operations such as insertion/deletion are slower.

Types of Linked Lists

There are 4 types of linked lists that can be created in python.

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

Singly Linked List

In a singly linked list, each node holds a value and a reference/link to the next node. It has no link pointing to the previous node. This is the simplest form of a linked list.

Circular Singly Linked List

The circular singly linked list is similar to a singly linked list. The only difference is that the last node holds a reference to the first node of the linked list.

When we reach the last node of the circular singly linked list, we have an option of going back to the first node. This is not possible in the case of a singly linked list.

Doubly Linked List

In a doubly-linked list, each node of the list has two references, one of the previous node and the other of the next node. Thus, each node holds two addresses along with the data value. Since each node has two references, a doubly-linked list allows us to traverse in both directions.

Circular Doubly Linked List

Circular doubly linked lists are similar to doubly linked lists. The only difference is that their first and last nodes are interconnected as well. The head node holds a reference to the tail node and vice versa.

Hence, in a circular doubly linked list we can perform circular traversal by jumping from the first node to the last node or from the last node to the first node.

Creation of Singly Linked List

We can create a singly linked list in python by following the mentioned steps.

Step 1: First, we create empty head and tail references and initialize both of them with null.
Step 2: Create a class “node”. The objects of this class hold one variable to store the values of the nodes and another variable to store the reference addresses.
Step 3: Create a blank node and assign it a value. Set the reference part of this node to null.
Step 4: Since we have only one element in the linked list so far, we will link both the head and tail to this node by putting in its reference address.

#Creating the Node class class Node: def __init__(self, value = None): self.value = value self.next = None #Create a class to initialize head and tail references class SinglyLinkedList: def __init__(self): self.head = None self.tail = None singlyll = SinglyLinkedList() #Initializing object of singly linked list temp_node1 = Node(10) temp_node2 = Node(20) singlyll.head = temp_node1 singlyll.head.next = temp_node2 singlyll.tail = temp_node2

The iterator function

Since the custom-created linked list is not iterable, we have to add an “__iter__” function so as to traverse through the list.

#Iterator Function def __iter__(self): node = self.head while node: yield node node = node.next

The time complexity for initializing a singly linked list is O(1). The space complexity is O(1) as no additional memory is required to initialize the linked list.

Insertion in Singly Linked List

A node can be inserted in a singly linked list in any one of the following three ways.

At the beginning of the linked list
In between the linked list
At the end of the linked list

Insertion Algorithm

Algorithm to insert a node at the beginning

Step 1: Create a node and assign a value to it.
Step 2: Assign the “next” reference of the node as head.
Step 3: Set the created node as the new head.
Step 4: Terminate.

Method to insert a node at the beginning

#Insertion at the beginning in a Singly Linked List class Node: def __init__(self, value = None): self.value = value self.next = None class SinglyLinkedList: def __init__(self): self.head = None self.tail = None #Function to add node in the beginning def atBeg(self, value): new_node = Node(value) new_node.next = self.head self.head = new_node #Initially, we have a linked list (1,3,5,7,9) called "sll". sll.atBeg(0) print([node.value for node in sll]) #Output [0, 1, 3, 5, 7, 9]

Algorithm to insert a node in between the linked list

Step 1: Create a node and assign a value to it.
Step 2: If the previous node doesn’t exist, return an error message and move to step 5.
Step 3: Assign the “next” reference of the previous node to the “next” reference of the new node.
Step 4: Set the “next” reference of the previous node to the newly added node.
Step 5: Terminate.

Method to insert a node in between the linked list

#Insertion in between a Singly Linked List #Function to add node in the middle def inMid(self,mid_node, value): if mid_node is None: print("Mentioned node doesn't exist") return new_node = Node(value) new_node.next = mid_node.next mid_node.next = new_node #Initially, we have a linked list (1,3,5,7,9) called "sll" and "mid" node points to the value 3. sll.inMid(mid, 11) print([node.value for node in sll]) #Output [1, 3, 11, 5, 7, 9]

Algorithm to insert a node at the end of the linked list

Step 1: Create a node and assign a value to it.
Step 2: If the list is empty, assign new node to head and tail. Move to step 5.
Step 3: Search for the last node. Once found, set its “next” reference pointing to the new node.
Step 4: Assign the new node as the tail.
Step 5: Terminate.

Method to insert a node at the end of the linked list

#Insertion at the end in a Singly Linked List #Function to add node in the end def atEnd(self, value): new_node = Node(value) if self.head is None: self.head = new_node self.tail = new_node return last_node = self.head while(last_node.next): last_node = last_node.next last_node.next=new_node self.tail = new_node #Initially, we have a linked list (1,3,5,7,9) called "sll". sll.atEnd(0) print([node.value for node in sll]) #Output [1, 3, 5, 7, 9, 0]

Time and Space Complexity

In python, instead of iterating over the linked list and reaching the required position, we can directly jump to any point. Therefore, the time complexity of insertion in a singly linked list is O(1).

But, for insertion at the end, the time complexity is O(N) as we need to traverse to the last element. The space complexity is O(1) because it takes a constant space to add a new node.

Linked Lists in Python: An Introduction

by Pedro Pregueiro intermediate python

Mark as Completed

Tweet Share Email

Table of Contents

Remove ads

Watch Now This tutorial has a related video course created by the Real Python team. Watch it together with the written tutorial to deepen your understanding: Working With Linked Lists in Python

Linked lists are like a lesser-known cousin of lists. They’re not as popular or as cool, and you might not even remember them from your algorithms class. But in the right context, they can really shine.

In this article, you’ll learn:

What linked lists are and when you should use them
How to use collections.deque for all of your linked list needs
How to implement your own linked lists
What the other types of linked lists are and what they can be used for

If you’re looking to brush up on your coding skills for a job interview, or if you want to learn more about Python data structures besides the usual dictionaries and lists, then you’ve come to the right place!

You can follow along with the examples in this tutorial by downloading the source code available at the link below:

Get the Source Code: Click here to get the source code you’ll use to learn about linked lists in this tutorial.

Make a loop at k-th position in a linked list

Given a linked list and a position k. Make a loop at k-th position
Examples:

Input : Given linked list

Output : Modified linked list

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Algorithm
1) Traverse the first linked list till k-th point
2) Make backup of the k-th node
3) Traverse the linked linked list till end
4) Attach the last node with k-th node

C++

// CPP program for making loop at k-th index
// of given linked list
#include <bits/stdc++.h>

using namespace std;
/* Link list node */

struct Node {

int data;

struct Node* next;
};
/* Function to make loop at k-th elements of
linked list */

void makeloop(struct Node** head_ref, int k)
{

// traverse the linked list until loop

// point not found

struct Node* temp = *head_ref;

int count = 1;

while (count < k) {

temp = temp->next;

count++;

}

// backup the joint point

struct Node* joint_point = temp;

// traverse remaining nodes

while (temp->next != NULL)

temp = temp->next;

// joint the last node to k-th element

temp->next = joint_point;
}
/* Function to push a node */

void push(struct Node** head_ref, int new_data)
{

struct Node* new_node =

(struct Node*)malloc(sizeof(struct Node));

new_node->data = new_data;

new_node->next = (*head_ref);

(*head_ref) = new_node;
}
/* Function to print linked list */

void printList(struct Node* head, int total_nodes)
{

struct Node* curr = head;

int count = 0;

while (count < total_nodes) {

count++;

cout << curr->data << " ";

curr = curr->next;

}
}

int countNodes(Node *ptr)
{

int count = 0;

while (ptr != NULL)

{

ptr = ptr->next;

count++;

}

return count;
}
/* Driver program to test above function*/

int main()
{

// Create a linked list 1->2->3->4->5->6->7

struct Node* head = NULL;

push(&head, 7);

push(&head, 6);

push(&head, 5);

push(&head, 4);

push(&head, 3);

push(&head, 2);

push(&head, 1);

// k should be less than the

// numbers of nodes

int k = 4;

int total_nodes = countNodes(head);

cout << "\nGiven list\n";

printList(head, total_nodes);

makeloop(&head, k);

cout << "\nModified list\n";

printList(head, total_nodes);

return 0;
}

Java

// Java program for making loop at k-th index 
// of given linked list 

class GFG
{

// Link list node /

static class Node
{ 

int data;

Node next;
} 
// Function to make loop at k-th elements of 
//linked list /

static Node makeloop( Node head_ref, int k)
{ 

// traverse the linked list until loop

// point not found

Node temp = head_ref;

int count = 1;

while (count < k)

{

temp = temp.next;

count++;

}

// backup the joint point

Node joint_point = temp;

// traverse remaining nodes

while (temp.next != null)

temp = temp.next;

// joint the last node to k-th element

temp.next = joint_point;

return head_ref;
} 
// Function to push a node /

static Node push( Node head_ref, int new_data)
{ 

Node new_node = new Node();

new_node.data = new_data;

new_node.next = (head_ref);

(head_ref) = new_node;

return head_ref;
} 
// Function to print linked list /

static void printList( Node head, int total_nodes)
{ 

Node curr = head;

int count = 0;

while (count < total_nodes)

{

count++;

System.out.print(curr.data + " ");

curr = curr.next;

}
} 

static int countNodes(Node ptr)
{ 

int count = 0;

while (ptr != null)

{

ptr = ptr.next;

count++;

}

return count;
} 
// Driver code

public static void main(String args[])
{ 

// Create a linked list 1.2.3.4.5.6.7

Node head = null;

head = push(head, 7);

head = push(head, 6);

head = push(head, 5);

head = push(head, 4);

head = push(head, 3);

head = push(head, 2);

head = push(head, 1);

// k should be less than the

// numbers of nodes

int k = 4;

int total_nodes = countNodes(head);

System.out.print("\nGiven list\n");

printList(head, total_nodes);

head = makeloop(head, k);

System.out.print( "\nModified list\n");

printList(head, total_nodes);
}
} 
// This code is contributed by Arnab Kundu

Python3

# Python3 program for making loop at k-th index
# of given linked list

import math
# Link list node 

class Node:

def __init__(self, data):

self.data = data

self.next = None
# Function to make loop at k-th elements of
#linked list 

def makeloop(head_ref, k):

# traverse the linked list until loop

# point not found

temp = head_ref

count = 1

while (count < k):

temp = temp.next

count = count + 1

# backup the joint point

joint_point = temp

# traverse remaining nodes

while (temp.next != None):

temp = temp.next

# joint the last node to k-th element

temp.next = joint_point

return head_ref
# Function to push a node 

def push(head_ref, new_data):

new_node = Node(new_data)

new_node.data = new_data

new_node.next = head_ref

head_ref = new_node

return head_ref
# Function to print linked list 

def printList( head,total_nodes):

curr = head

count = 0

while (count < total_nodes):

count = count + 1

print(curr.data, end = " ")

curr = curr.next

def countNodes(ptr):

count = 0

while (ptr != None):

ptr = ptr.next

count = count + 1

return count
# Driver Code

if __name__=='__main__':

# Create a linked list 1.2.3.4.5.6.7

head = None

head = push(head, 7)

head = push(head, 6)

head = push(head, 5)

head = push(head, 4)

head = push(head, 3)

head = push(head, 2)

head = push(head, 1)

# k should be less than the

# numbers of nodes

k = 4

total_nodes = countNodes(head)

print("Given list")

printList(head, total_nodes)

makeloop(head, k)

print("\nModified list")

printList(head, total_nodes)

# This code is contributed by Srathore

// C# program for making loop at k-th index 
// of given linked list 

using System;

class GFG
{

// Link list node /

public class Node
{ 

public int data;

public Node next;
} 
// Function to make loop at k-th elements of 
//linked list /

static Node makeloop( Node head_ref, int k)
{ 

// traverse the linked list until loop

// point not found

Node temp = head_ref;

int count = 1;

while (count < k)

{

temp = temp.next;

count++;

}

// backup the joint point

Node joint_point = temp;

// traverse remaining nodes

while (temp.next != null)

temp = temp.next;

// joint the last node to k-th element

temp.next = joint_point;

return head_ref;
} 
// Function to push a node /

static Node push( Node head_ref, int new_data)
{ 

Node new_node = new Node();

new_node.data = new_data;

new_node.next = (head_ref);

(head_ref) = new_node;

return head_ref;
} 
// Function to print linked list /

static void printList( Node head, int total_nodes)
{ 

Node curr = head;

int count = 0;

while (count < total_nodes)

{

count++;

Console.Write(curr.data + " ");

curr = curr.next;

}
} 

static int countNodes(Node ptr)
{ 

int count = 0;

while (ptr != null)

{

ptr = ptr.next;

count++;

}

return count;
} 
// Driver code

public static void Main(String []args)
{ 

// Create a linked list 1.2.3.4.5.6.7

Node head = null;

head = push(head, 7);

head = push(head, 6);

head = push(head, 5);

head = push(head, 4);

head = push(head, 3);

head = push(head, 2);

head = push(head, 1);

// k should be less than the

// numbers of nodes

int k = 4;

int total_nodes = countNodes(head);

Console.Write("\nGiven list\n");

printList(head, total_nodes);

head = makeloop(head, k);

Console.Write( "\nModified list\n");

printList(head, total_nodes);
}
}
// This code contributed by Rajput-Ji

Javascript

<script>
// javascript program for making loop at k-th index 
// of given linked list 
// Link list node /
class Node {

constructor(val) {

this.data = val;

this.next = null;

}
}

// Function to make loop at k-th elements of

// linked list /

function makeloop(head_ref , k) {

// traverse the linked list until loop

// point not found

var temp = head_ref;

var count = 1;

while (count < k) {

temp = temp.next;

count++;

}

// backup the joint point

var joint_point = temp;

// traverse remaining nodes

while (temp.next != null)

temp = temp.next;

// joint the last node to k-th element

temp.next = joint_point;

return head_ref;

}

// Function to push a node /

function push(head_ref , new_data) {

var new_node = new Node();

new_node.data = new_data;

new_node.next = (head_ref);

(head_ref) = new_node;

return head_ref;

}

// Function to print linked list /

function printList(head , total_nodes) {

var curr = head;

var count = 0;

while (count < total_nodes) {

count++;

document.write(curr.data + " ");

curr = curr.next;

}

}

function countNodes(ptr) {

var count = 0;

while (ptr != null) {

ptr = ptr.next;

count++;

}

return count;

}

// Driver code

// Create a linked list 1.2.3.4.5.6.7

var head = null;

head = push(head, 7);

head = push(head, 6);

head = push(head, 5);

head = push(head, 4);

head = push(head, 3);

head = push(head, 2);

head = push(head, 1);

// k should be less than the

// numbers of nodes

var k = 4;

var total_nodes = countNodes(head);

document.write("<br/>Given list<br/>");

printList(head, total_nodes);

head = makeloop(head, k);

document.write("<br/>Modified list<br/>");

printList(head, total_nodes);
// This code contributed by umadevi9616
</script>