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

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

    def append(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            return

        # Navigate to the end of the list
        current = self.head
        while current.next:
            current = current.next

        current.next = new_node

    def displayLL(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.displayLL()

class Node:
    def __init__(self, data):
        self.data = data  # Store the value
        self.next = None  # Initialize the pointer to the next node as None

"+data+"");
									jQuery(".maineditor57459 .code-editor-output").show();
									jQuery("#runBtn57459 i.run-code").hide();
									
								}
							})
					

						}
						
						
		function closeoutput57459() {	
		var code = editor57459.getSession().getValue();
		jQuery(".maineditor57459 .code-editor-output").hide();
		}

    // Attach event listeners to the buttons
    document.getElementById("copyBtn57459").addEventListener("click", copyCodeToClipboard57459);
    document.getElementById("runBtn57459").addEventListener("click", runCode57459);
    document.getElementById("closeoutputBtn57459").addEventListener("click", closeoutput57459);
 
    



Outcome:






In this code, the node class is generated and established using the __init__ method to set a data value and a reference to the subsequent node. Furthermore, two nodes are instantiated and interconnected in this example, forming a basic two-element linked list.







Adding Elements to a Linked List in Python



Adding elements in a linked list involves including a new node at a designated location. There are three varieties of addition in a linked list in Python.



1. Adding a Node at the Front of a Linked List






To add a node at the front of a linked list in Python, follow these procedures:

“““html

Result:

The code illustrates how new nodes are introduced at the start of the linked list. Initially, a new node is created via insertAtBegin(), then it is linked to the current head, and the head is modified to reference the new node. This allows for elements to be added at the beginning of the list, and afterwards, printLL() is utilized to traverse and display the linked list.

2. Inserting at the End of a Linked List

To add a new node at the end of a linked list in Python, follow these instructions:

• First, create a new node from the data you wish to insert.
• Now, verify whether the linked list is empty.
• If the linked list is unoccupied, set the new node as the head of the linked list.
• If the linked list contains nodes, traverse to the last node, identified by the node’s next being None.
• Set the next of the last node to refer to the new node and link it to the end.

Illustration:

``````javascript
"");

editor52609.setValue(decodedContent); // Assign the default text
editor52609.clearSelection();

editor52609.setOptions({
maxLines: Infinity
});

function decodeHTML52609(input) {
var doc = new DOMParser().parseFromString(input, "text/html");
return doc.documentElement.textContent;
}

// Function to copy code to the clipboard
function copyCodeToClipboard52609() {
const code = editor52609.getValue(); // Retrieve code from the editor
navigator.clipboard.writeText(code).then(() => {
jQuery(".maineditor52609 .copymessage").show();
setTimeout(function() {
jQuery(".maineditor52609 .copymessage").hide();
}, 2000);
}).catch(err => {
console.error("Error copying code: ", err);
});
}

function runCode52609() {
var code = editor52609.getSession().getValue();

jQuery("#runBtn52609 i.run-code").show();
jQuery(".output-tab").click();

jQuery.ajax({
url: "https://intellipaat.com/blog/wp-admin/admin-ajax.php",
type: "post",
data: {
language: "python",
code: code,
cmd_line_args: "",
variablenames: "",
action:"compilerajax"
},
success: function(response) {
var myArray = response.split("~");
var data = myArray[1];

jQuery(".output52609").html("

" + data + "");
            jQuery(".maineditor52609 .code-editor-output").show();
            jQuery("#runBtn52609 i.run-code").hide();
        }
    });
}

function closeoutput52609() {    
    var code = editor52609.getSession().getValue();
    jQuery(".maineditor52609 .code-editor-output").hide();
}

// Attach event listeners to the buttons
document.getElementById("copyBtn52609").addEventListener("click", copyCodeToClipboard52609);
document.getElementById("runBtn52609").addEventListener("click", runCode52609);
document.getElementById("closeoutputBtn52609").addEventListener("click", closeoutput52609);


Output:



    



This code illustrates how new nodes are added to the end of the list. In this instance, the insertAtEnd() function verifies whether the list is empty and proceeds to add the new node. The printLL() function subsequently prints all node values from head to tail.

3. Inserting at a Specific Index in a Linked List



    



To add a new node at a particular index in a linked list in Python, perform the following steps.

• Create a new node using the data you intend to insert.
• If the index equals 0, invoke the method to insert at the beginning.
• Then traverse the list just prior to the specified index.
• If the index exceeds the list’s length, indicate an error or continue without adding the node.
• Assign the new node’s next reference to the current node’s next.
• The previous node’s next should be updated to point to the new node.

Example:

Result:

The code illustrates how new nodes are added at given indices in a linked list. 10 is included at index 0 (start), 20 is added at index 1 (end), 15 is inserted at index 1 (between 10 and 20), followed by printing the list using printLL().

Modifying a Node in a Linked List using Python

Modifying a node in a linked list refers to altering the value of a node at a specific position or upon meeting a particular condition.

Below are several steps to follow for modifying a linked list using Python.

• Begin from the head of the linked list.
• Next, traverse the list while monitoring the current node and index.
• If you reach the desired index, update the data field with the new value.
• If the desired node is not found, display an error message.
  

Illustration:

Result:

The script illustrates how the node of a linked list can be modified using the updateAtIndex function, which navigates the list to reach the given index. Upon arriving at the designated index, the data within that node gets updated, and the refreshed list will display the newly assigned value.

Removing a Node in a Linked List

Removing a node from a linked list involves eliminating a node that corresponds to a specific value or position and then reconnecting the remaining nodes to preserve the list's structure.

1. Deleting the First Node from a Linked List

Eliminating the initial node, or head of a linked list is straightforward; all that is required is to delete the head and redirect the head to the head.next.

To remove the first node from a linked list in Python, follow these instructions:

• Initially, verify if the linked list is empty.
• If the head is not null, set the head to reference the head.next node to discard (delete) the first node.
• Once the previous head is no longer referenced by any node, it will be removed from the list.

Illustration:

Result:

The following code illustrates how to eliminate the initial node of a linked list by verifying whether the list is devoid of elements, through the use of the removeFirstNode() function. If the list isn't empty, the head is reassigned to point to the subsequent node, effectively removing the original first node (10) from reference and leading to its deletion.

2. Removing the Last Node from a Linked List

To extract the last node from a linked list, it is necessary to navigate to the penultimate node and eliminate it by setting its next pointer to None.

To remove the final node from a linked list using Python, adhere to the steps outlined below:

• Initially, verify if the linked list is empty.
• If the linked list consists of only one node, modify the head to None.
• In cases where multiple nodes are present, traverse to the second last node (the one where node.next.next is None).
• Finally, delete the last node of the linked list and establish second_last.next to None.

Example:

Output:

This code illustrates how to delete the last node from a linked list using the removeLastNode() method, which navigates to the second-last node and sets its next pointer to None, followed by the deletion of the last node from the list.

3. Deleting a Node from a Linked List at a Specified Position

A node within a linked list can be eliminated at a specified position by traversing the list and adjusting the pointers to bypass the designated node.

To delete a node from a linked list in Python at a specified position, execute the following steps:

• Verify if the list is empty (head is None).
• If the position is 0, set the head to head.next.
• Otherwise, navigate to the position-1 node (the node prior to the designated position).
• In case the position exceeds bounds, display an error notification.
• Finally, modify the next pointer of the preceding node to bypass the node at the specified position.

Example:

var isMobile = window.innerWidth ");

editor65208.setValue(decodedContent); // Set the initial text editor65208.clearSelection();

editor65208.setOptions({ maxLines: Infinity });

function decodeHTML65208(input) { var doc = new DOMParser().parseFromString(input, "text/html"); return doc.documentElement.textContent; }

// Function to copy code to clipboard function copyCodeToClipboard65208() { const code = editor65208.getValue(); // Get code from the editor navigator.clipboard.writeText(code).then(() => { jQuery(".maineditor65208 .copymessage").show(); setTimeout(function() { jQuery(".maineditor65208 .copymessage").hide(); }, 2000); }).catch(err => { console.error("Error copying code: ", err); }); }

function runCode65208() { var code = editor65208.getSession().getValue(); jQuery("#runBtn65208 i.run-code").show(); jQuery(".output-tab").click();

jQuery.ajax({ url: "https://intellipaat.com/blog/wp-admin/admin-ajax.php", type: "post",

data: { language: "python", code: code, cmd_line_args: "", variablenames: "", action:"compilerajax" }, success: function(response) { var myArray = response.split("~"); var data = myArray[1];

jQuery(".output65208").html("

" + data + "

"); jQuery(".maineditor65208 .code-editor-output").show(); jQuery("#runBtn65208 i.run-code").hide(); } }); }

function closeOutput65208() { jQuery(".maineditor65208 .code-editor-output").hide(); }

// Attach event listeners to the buttons document.getElementById("copyBtn65208").addEventListener("click", copyCodeToClipboard65208); document.getElementById("runBtn65208").addEventListener("click", runCode65208); document.getElementById("closeoutputBtn65208").addEventListener("click", closeOutput65208);

Result:

The aforementioned code illustrates how a node from a linked list is removed using the deleteAtPosition() method, which deletes the node at a specified index by navigating to the preceding node and adjusting the pointers accordingly.

Categories of Linked Lists in Python

Linked lists can be classified into 4 distinct types, depending on how nodes are interconnected and accessed. Below is a brief overview of the types with examples in Python.

1. Singly Linked List

A singly linked list is a variety of linked list in Python where each node directs to the subsequent node in the series.

• It is a linked list that can solely be traversed in one direction, from the head to the end.
• In a singly linked list, each node contains two components: the data and the next, with the next of the last node pointing to None.
• Any node can be quickly inserted and deleted from the start of the list.
• A singly linked list is straightforward, user-friendly, and consumes less memory.

Sample:

``````javascript
isMobile = window.innerWidth "");

editor16181.setValue(decodedContent); // Set the default text
editor16181.clearSelection();

editor16181.setOptions({
maxLines: Infinity
});

function decodeHTML16181(input) {
var doc = new DOMParser().parseFromString(input, "text/html");
return doc.documentElement.textContent;
}

// Function to copy code to clipboard
function copyCodeToClipboard16181() {
const code = editor16181.getValue(); // Retrieve code from the editor
navigator.clipboard.writeText(code).then(() => {
// alert("Code copied to clipboard!");
jQuery(".maineditor16181 .copymessage").show();
setTimeout(function() {
jQuery(".maineditor16181 .copymessage").hide();
}, 2000);
}).catch(err => {
console.error("Error copying code: ", err);
});
}

function runCode16181() {
var code = editor16181.getSession().getValue();

jQuery("#runBtn16181 i.run-code").show();
jQuery(".output-tab").click();

jQuery.ajax({
url: "https://intellipaat.com/blog/wp-admin/admin-ajax.php",
type: "post",
data: {
language: "python",
code: code,
cmd_line_args: "",
variablenames: "",
action:"compilerajax"
},
success: function(response) {
var myArray = response.split("~");
var data = myArray[1];

jQuery(".output16181").html("

"+data+"");
            jQuery(".maineditor16181 .code-editor-output").show();
            jQuery("#runBtn16181 i.run-code").hide();
        }
    });
}

function closeoutput16181() {
    var code = editor16181.getSession().getValue();
    jQuery(".maineditor16181 .code-editor-output").hide();
}

// Attach event listeners to the buttons
document.getElementById("copyBtn16181").addEventListener("click", copyCodeToClipboard16181);
document.getElementById("runBtn16181").addEventListener("click", runCode16181);
document.getElementById("closeoutputBtn16181").addEventListener("click", closeoutput16181);



Output:




This code illustrates how a linked list is constructed, wherein each node links to the subsequent node. Nodes are appended to the end of the linked list using insertAtEnd(), while printList() is utilized for traversing the list and showcasing the node values.

2. Doubly Linked List




A doubly linked list represents a form of linked list in Python where each node is associated with links to both the subsequent node and the preceding one in the chain.

• It allows traversal in both directions, forward and backward, meaning from the head to the tail and from the tail back to the head.
• In a doubly linked list, every node comprises three components: data for storing the value, next for pointing to the next node, and prev for referring to the preceding node.
• It facilitates efficient insertions and deletions from either end while consuming additional memory due to the extra prev pointer.

Example:

Result:

The code illustrates how a doubly linked list is constructed, with each node connecting to both its succeeding and preceding nodes. New nodes are appended to the end using insertAtEnd(), while printForward() displays the list from start to finish.

3. Circular Linked List

A circular linked list is a different variant of a singly linked list in Python characterized by the last node linking back to the first, thus creating an endless loop.

• In a circular linked list, each node points to the following node, and the last node's pointer leads back to the head.
• Traversal of the circular linked list occurs in a cycle endlessly and can only be halted deliberately.
• This structure is optimal for managing circular data, such as implementing round-robin scheduling.

Illustration:

Result:

This code illustrates how a circular linked list is constructed, where the final node links back to the head, creating a loop. Nodes are appended at the list's end, and the printList() function is utilized to display the list until it returns to the head.

4. Circular Doubly Linked List

A circular doubly linked list is a specific kind of doubly linked list in Python, where the last node refers back to the first node, and the first node points to the last node.

• Similar to a traditional doubly linked list, it allows traversal in both directions, and due to its circular nature, we can navigate through the linked list continuously.
• In a circular doubly linked list, every node comprises three components: data, where the value is stored; next, which signifies the pointer to the subsequent node; and prev, which indicates the pointer to the previous node.
• The next pointer of the final node directs to the head, while the prev pointer of the head references the last node.

Sample:

Result:

This code demonstrates how the circular doubly linked list is formed, where every node is interconnected in both forward and backward paths, with the last node looping back to the head.

Navigating a Linked List in Python

Navigating a linked list refers to the activity of reaching each of the nodes in the linked list from the head to the end and retrieving the data.

To traverse a linked list ``````html

In Python, simply execute these steps:

• Begin with the head node.
• Utilize a while loop to navigate from one node to the next, following the next pointer within the linked list.
• Keep moving to a node until the current one is None, indicating you have reached the conclusion of the linked list.
• Inside the loop, at every iteration, perform the actions you wish to carry out (e.g., print the data).

Example:

Output:

The code demonstrates how to traverse a linked list by iterating through each node, utilizing the next link until reaching the end of the list, at which point the traversed nodes are printed to the console.

Calculating the Length of a Linked List in Python

The length of a linked list is assessed by the number of nodes starting at the head node (the first node) to the concluding node in the linked list.

To ascertain the length of a linked list in Python, follow these steps:

• Commence at the head node.
• Progress through every node, adding to a counter during each visit (initially set to 0).
• After completing the traversal (when node is None), return the counter as the length of the linked list.

Example:

var isMobile = window.innerWidth
``````html
");

editor9060.setValue(decodedContent); // Assign the initial text
editor9060.clearSelection();

editor9060.setOptions({
maxLines: Infinity
});

function decodeHTML9060(input) {
var doc = new DOMParser().parseFromString(input, "text/html");
return doc.documentElement.textContent;
}

// Function to copy code to clipboard
function copyCodeToClipboard9060() {
const code = editor9060.getValue(); // Retrieve code from the editor
navigator.clipboard.writeText(code).then(() => {
// alert("Code copied to clipboard!");

jQuery(".maineditor9060 .copymessage").show();
setTimeout(function() {
jQuery(".maineditor9060 .copymessage").hide();
}, 2000);
}).catch(err => {
console.error("Error copying code: ", err);
});
}

function runCode9060() {

var code = editor9060.getSession().getValue();

jQuery("#runBtn9060 i.run-code").show();
jQuery(".output-tab").click();

jQuery.ajax({
url: "https://intellipaat.com/blog/wp-admin/admin-ajax.php",
type: "post",

data: {
language: "python",
code: code,
cmd_line_args: "",
variablenames: "",
action:"compilerajax"
},
success: function(response) {
var myArray = response.split("~");
var data = myArray[1];

jQuery(".output9060").html("

"+data+"");

									jQuery(".maineditor9060 .code-editor-output").show();

									jQuery("#runBtn9060 i.run-code").hide();
								}

							})
						}
		function closeoutput9060() {

		var code = editor9060.getSession().getValue();

		jQuery(".maineditor9060 .code-editor-output").hide();

		}
    // Attach event listeners to the buttons

    document.getElementById("copyBtn9060").addEventListener("click", copyCodeToClipboard9060);

    document.getElementById("runBtn9060").addEventListener("click", runCode9060);

    document.getElementById("closeoutputBtn9060").addEventListener("click", closeoutput9060);
    
Output:



This code illustrates how to compute the length of a linked list by invoking the getLength() method, which starts at the head of the list and traverses from there, tallying the nodes until the list concludes, ultimately yielding a total node count of 3 for the linked list.

Time Complexity of Linked List Operations in Python




Operation
Time Complexity
Explanation




Insertion at Beginning
O(1)
Only the head pointer needs adjustment.


Insertion at End
O(n)
Requires retracing to the list's end.


Insertion at Index
O(n)
Must reach the specified index.


Deletion at Beginning
O(1)
Head shifts to the next node.


Deletion at End
O(n)
Requires reaching the penultimate node.


Deletion at Index
O(n)
Must access that position for deletion.


Search Element
O(n)
Needs to assess each node until a match is found.


Access by Index
O(n)
Direct indexing like in arrays is not available.


Traverse the List
O(n)
Every node must be visited only once.




Note:

• The variable n signifies the number of nodes within the linked list.
• In the case of a doubly linked list, it may be feasible to enhance the insertion and removal at the end to O(1).
• A circular linked list has no terminus, as you can perpetually traverse all nodes unless you manually halt it.

Benefits of Linked List in Python

• Dynamic Size: The linked list’s size can be modified while in operation, and it doesn’t require a predefined size.
• Effective Insertion & Deletion: Nodes can be added or removed more efficiently compared to an array, as elements within the same index do not need to be shifted.
• No Memory Waste: A linked list consumes memory only if it contains nodes; if there are no nodes, it does not occupy memory (thus preventing waste).
• Versatility: A linked list is adaptable and straightforward to implement.
• Simpler Reordering: Data can be rearranged without duplicating or shifting other information.

Drawbacks of Linked List in Python

• Memory Overhead: Each node within a linked list requires additional memory for the pointer, besides the data it holds.
• No Random Access: Linked lists do...
  ``````html
• No Random Access: Accessing an element necessitates traversing through each node sequentially, commencing from the head up to the tail.
• Extended Look-up Time: In the worst-case scenario, locating an element may require O(n) time, resulting in a prolonged look-up duration.
• Increased Complexity: Managing insertions and deletions in linked lists can become quite intricate with sizable data sets.
• Cache Efficiency: Compared to arrays, linked lists perform poorly in CPU cache usage. They do not occupy contiguous memory spaces.

Linked List vs Array in Python

Attribute	Linked List	Array
Fundamental Definition	A collection of nodes, each containing data and a pointer to the following node	A sequence of memory addresses storing elements of a uniform type
Memory Management	Dynamic allocation (nodes can exist anywhere in memory)	Static allocation (a contiguous segment)
Insertion/Deletion	O(1) at the start/end (with proper pointers), O(n) for arbitrary access	O(n) at the start/middle (requires shifting), O(1) at the end
Arbitrary Access	O(n) – Requires traversal from the head node	O(1) – Immediate access via index
Memory Consumption	Higher (includes extra pointers)	Lower (only includes data)
Python Realization	Custom class implementation or utilizing collections.deque	Built-in list data type
Cache Efficiency	Poor (nodes dispersed throughout memory)	Superior (contiguous memory)
Size Adaptability	Expands/shrinks effortlessly during execution	Fixed size (though Python lists are dynamic arrays)
Common Functions	insert_at_head(), delete_node(), traverse()	append(), pop(), indexing
Optimal Application	Frequent insertions/deletions, unpredictable size	Random access, fixed size data, mathematical tasks

Uses of Linked Lists in Python

• Linked lists are utilized for the implementation of queues and stacks, allowing constant-time insertion and deletion from either end.
• Linked lists facilitate dynamic memory management, accommodating continual insertions and deletions without the need for memory reallocation.
• Linked lists are well-suited for graph representations, employing adjacency lists, particularly for sparse graph structures.
• Ideal for handling real-time data streams, linked lists can be used for computations involving sliding windows or buffering.
• Links in text editors or similar software for undo & redo functionalities can effectively utilize doubly linked lists.
• In polynomial computations, polynomial terms can be added and administered more effectively with linked lists, enhancing flexibility.
• Media players or systems that navigate through playlists may implement circular or doubly linked lists, promoting easier and more efficient forward and backward navigation.

Conclusion

Python linked lists adeptly manage data dynamically, offering greater flexibility than arrays for certain operations such as element addition and removal. The Python programming language presents numerous advantages, particularly its flexibility, simplicity, and ease of linked list creation, alongside a few limitations. Despite Python's powerful built-in lists and capabilities, grasping linked lists is crucial for beginners to develop robust coding skills and understand data structures effectively.

Linked Lists in Python – FAQs

The post Linked Lists in Python appeared first on Intellipaat Blog.

```