I have never been good at linked lists and even more broader - pointer logic. In this post I want to show a practical example of a linked list implementation in python and how to use it.

The main advantage of a linked list is that it does not need to be stored in a continuous block in memory and can live in a random place. The disadvantage is we can’t just access a node - the list has to be traversed.

#### The Python Implementation#

This Singly linked list implementation was taken from hackerrank:

``````class SinglyLinkedListNode:
def __init__(self, node_data):
self.data = node_data
self.next = None

def __init__(self):
self.tail = None

def insert_node(self, node_data):

else:
self.tail.next = node

self.tail = node
``````

To use it:

``````my_linked_list = SinglyLinkedList()
``````

#### Moving it Around#

Instead of passing the linked list around. Sometimes it is preferable to just send a single node (really? when is that preferable and why? - recursion?)

That is all the current function needs to know as the node has the reference to the `next` and the function can iterate from the current node till the tail of the linked list.

To print a linked list you can use a while loop or recursion.

The recursion example:

``````def print_linked_list(head):
'''
'''
``````

what happens is you print the current nodes data attribute then if the current node has a next node - run the function to print the linked list with that node.

The while example:

``````def print_linked_list_while(head):
'''
Print a single linked list in a while loop
'''
``````

The timing were inconclusive:

• `while` loop: 10000 times - 0.702690217, 50000 times - 8.423126091
• `recursion`: 10000 times - 0.388262048, 50000 times - 7.361549832

#### Inserting a node at the Tail#

My successful attempt (but probably not optimal):

``````def insertNodeAtTail(head, data):
return node
# Get the the end
# Set the next node as the new tail node
return initial_node
``````

### Inserting a node at the head#

``````def insertNodeAtHead(llist, data):
node.next = llist
return node
``````

### Inserting a node within a linkedlist#

Whenever dealing with positions not at the start or the end - a temporary node is needed to do changes and switches

``````def insertNodeAtPosition(llist, data, position):
if llist is None:
return new_node
else:
# index position form 0
position = position - 1
while (position > 0 and llist.next is not None):
llist = llist.next
position -= 1
temp = llist.next
llist.next = new_node
new_node.next = temp
``````

### Deleting a Node#

When deleting a node a reference will always be needed to the prior node as the prior nodes `next` attribute will (the case of the first and last node are handled with if statements)

``````def deleteNode(llist, position):
if position == 0:
return llist.next
prior_node = llist

position -= 1
while (position > 0):
prior_node = prior_node.next
position -= 1

current_node = prior_node.next
if current_node.next is not None:
next_node = current_node.next
else:
next_node = None

prior_node.next = next_node
``````

Since the linked list can only be processed in a single direction - we could read the entire list until `node.next == None` then print it and set the prior nodes next to `None`

I went with using a list:

``````def reversePrint(llist):
items = []
while (llist):
items.append(llist.data)
llist=llist.next
for item in items[::-1]:
print(item)
``````

Reversing a linked list - at the core is changing the next to point to the prior node - instead of the next one - for all nodes along the chain. We can process it one way - swapping the next references all the way until the end returning the head. Whenever making changes in teh middle - we require a temporary node and have references to 3 nodes at a time

``````def reverse(llist):
prior_node = None
current_node = llist
next_node = llist.next

while(current_node):
temp = current_node.next
current_node.next = prior_node
prior_node = current_node
current_node = temp

# at this point the prior_node is the head of the list
return prior_node
``````

``````def compare_lists(llist1, llist2):
while(llist1.data == llist2.data):
llist1 = llist1.next
llist2 = llist2.next
if not llist1 and not llist2:
return 1
elif not llist1 or not llist2:
return 0
return 0
``````

### Delete Even numbers in a linked list#

``````def delete_even_nodes(head):
'''
Remove nodes that are even
'''
while (head.data % 2 == 0):

while (current_node):
next_node= current_node.next
if current_node.data % 2 == 0:
# skip it
prior_node.next = next_node
else:
# otherwise ensure current node is maintained
prior_node = current_node
current_node = next_node