Hey, it’s been a long time since I wrote part one. In this sequel, we are going to write some methods that have been useful for linked lists, so, let’s deep dive into it.
Prepend #
The prepend method is like the name indicates, add a node to the first item of the linked list. This is very useful for changing the value of the head. As well as for implementing stacks and queues.
The logic of the prepend method is as follows:
-
Create a new node.
-
Check if the linked list is empty. If it is, the new node becomes the head and the tail of the linked list.
-
Set the next reference of the new node to the current head of the linked list.
-
Change the reference to the head of the linked list to refer to the new node.
And that’s all, simple right? So the code is:
class LinkedList:
# previous code
def prepend(self, value) -> bool:
"""
Append to the the beginning of the ll a new node
"""
new_node = Node(value=value)
if self.length == 0:
self.head = new_node
self.tail = new_node
self.length = 1
else:
#Refers the new node to the LL
new_node.next = self.head
#Set the head to the new node
self.head = new_node
self.length += 1
return True
Pop firs #
This method allows us to remove the first node in a linked list and return the node. To make this possible, we have to follow the next steps:
- Check if the linked list is empty. If it is, return None.
- If it is not empty, reference the head (the node) to a temp variable.
- Reference the head to the next node that the head is currently referencing.
- The node that is referenced by the temp variable is set to None
- Return the temp value
It’s a method very simple, the code is:
class LinkedList:
# previous code
def pop_firs(self) -> any:
"""
Delete from the ll the first element and return it
Return
None: If the lenght of the ll is 0
Any: The value of the node
"""
if self.length == 0:
return None
else:
temp = self.head
self.head = self.head.next
temp.next = None
self.length -= 1
if self.length == 0:
self.tail = None
return temp.value
Get #
This method returns the reference of a node based on an index of the linked list passed to the method. This code is very simple. Check these steps and judge for yourself:
- First, check if the index that is passed to the method is valid.
- If it’s not, return None.
- If it’s valid, iterate through the linked list until the index of the node.
- Return the reference to the node.
The code is:
class LinkedList:
# previous code
def get(self, index) -> any:
"""
Return the node according to the index pass to the function
Return:
None: If the index its out of range or is less than 0
Any: The value of the node
"""
if index < 0 or index > self.length:
return None
else:
temp = self.head
# The underscore is use to
for _ in range(index):
temp = temp.next
return temp
Set value #
To implement this method, we change the value of a node based on the index passed as an argument to the method. We use the get method described in the previous point. The pseudo code is as follows:
- Use the get method to obtain the node in the linked list, 😅.
- If the get method returns None, do not make any changes
- If the get method returns a reference, change the attribute value of the node to the new one passed as an argument to the method
The code is:
class LinkedList:
# previous code
def set_value(self, index, value) -> bool:
"""
Change the value of a node according to the index pass to the function.
Return
True: If the change was succesful
False: If the index it's out of range or less than 0
"""
temp = self.get(index=index)
if temp:
temp.value = value
return True
return False
Insert #
This method is a little bit more complicated than the 3 others described in the previous points. The insert method consists of adding a new node at the index that is passed in as the argument to the function. For this method, we used some knowledge learned in the previous methods, specifically the logic of the get method and used variables to save the references.
The logic of the insert method is as follows:
- Check if the index passed as the argument is valid
- If it’s not valid, return false.
- If it’s valid:
- If the index passed as an argument to the function is equal to 0, we can use insert 🤌.
- If the index passed as an argument to the function is equal to the length of the linked list, we use the append method 🤌.
- Otherwise, we have to do some extra code:
- First, create a new node.
- Use the get method to obtain the reference to the node previous to the position of the index where we want to insert.
- Reference the new node to the next references of the previous node.
- Reference the previous node to the new node.
And that’s all, the code is ready!
class LinkedList:
# previous code
def insert(self, index, value) -> bool:
"""
Insert a new node in the ll according to the index pass to the function
Return
True: If the insert was successful
False: If the index it's out of range or is less than zero
"""
if index < 0 or index > self.length:
return False
if index == 0:
self.prepend(value=value)
return True
elif index == self.length:
self.append(value=value)
return True
else:
new_node = Node(value=value)
temp = self.get(index= index - 1)
new_node.next = temp.next
temp.next = new_node
self.length += 1
return True
The song of the post #
El cuarto de Tula, le cogió candela
Se quedó dormida y no apagó la vela
Candela, muchacho
Se volvió loco, Barbarito
¡Hay que ingresarlo!
— El cuarto de Tula - Buena Vista Social Club