I'm trying to create a function that takes in a head of a linked list and a value, create a node with that value, set node.next to head, and then update the the new node to be the head. I got it to work but I feel like I'm doing this very inefficiently by returning values, so I was wondering if there is a more elegant way to do this.
Here's the code I'm using:
#!/usr/bin/env python3
"""
This module is a linked list implementation.
"""
class Node:
"""
Node structure to be used in our linked list.
"""
def __init__(self, value):
self.value = value
self.next = None
def linked_insert(head, value):
"""
Insert new node to the tail of the linked list.
Time Complexity: O(n)
"""
current = head
while current.next is not None:
current = current.next
current.next = Node(value)
def linked_insert2(head, value):
"""
Insert new node to the head of the linked list, making sure to update head.
Time Complexity: O(1)
"""
to_insert = Node(value)
to_insert.next = head
head = to_insert
return head
def linked_extract(head):
"""
Extract the last element in the linked list
"""
current = head
while current.next.next is not None:
current = current.next
tail = current.next
current.next = None
return tail
def linked_display(head):
"""
Print all node values in the linked list
"""
current = head
while current is not None:
print(current.value)
current = current.next
# Test Program
head = Node(5)
# linked_insert(head, 1)
# linked_insert(head, 2)
# linked_insert(head, 3)
#
# print(linked_extract(head).value)
head = linked_insert2(head, 1)
head = linked_insert2(head, 2)
head = linked_insert2(head, 3)
linked_display(head)
Is there a way to do this without having to return the value of head and setting head = returned value in the test program?
The function in question is linked_insert2(). The whole program is meant to be a linked list implementation in python.
Implementation using linked list class:
#!/usr/bin/env python3
"""
This module is a linked list implementation.
"""
class Node:
"""
Node class to be used in our linked list.
"""
def __init__(self, value):
self.value = value
self.next = None
class Linkedlist:
"""
Linked list implementation that supports functions including inserting
at head, inserting at tail, extracting elements, and displaying all
elements in the ist
"""
def __init__(self, head):
self.head = Node(head)
def insert(self, value):
"""
Insert new node to the tail of the linked list.
Time Complexity: O(n)
"""
current = self.head
while current.next is not None:
current = current.next
current.next = Node(value)
def insert2(self, value):
"""
Insert new node to the head of the linked list, making sure to update head.
Time Complexity: O(1)
"""
to_insert = Node(value)
to_insert.next = self.head
self.head = to_insert
def extract(self):
"""
Extract the last element in the linked list
"""
current = self.head
while current.next.next is not None:
current = current.next
tail = current.next
current.next = None
return tail
def display(self):
"""
Print all node values in the linked list
"""
current = self.head
while current is not None:
print(current.value)
current = current.next
# Test Program
head = Linkedlist(5)
# linked_insert(head, 1)
# linked_insert(head, 2)
# linked_insert(head, 3)
head.insert2(1)
head.insert2(2)
head.insert2(3)
head.display()
