Node method i am struggling with (linked lists)

Language Help Python
1

So im currently learning linked lists in data structure module.

This is where i am now, i learned how to make links to nodes how to make a linked list how to retrieve values from a node, how to swap nodes and so on. But now im trying to learn a method to find the nth to last node of a linked list and i am really struggling with it.

def nth_last_node(linked_list, n):
current = None
tail_seeker = linked_list.head_node
count = 1
while tail_seeker:
tail_seeker = tail_seeker.get_next_node()
count += 1
if count >= n + 1:
if current is None:
current = linked_list.head_node
else:
current = current.get_next_node()
return current

Here is the solution of the exercise and one of the ways to do the method itself (given by codecademy)

below is what i can take from it:

TS = tail seeker variable
C = current variable
I = Node

I I I I I

TS I I I I COUNT =1 NO TICK YET N = 2

C TS I I I COUNT = 2 FIRST TICK 2 < 2 + 1

I C TS I I COUNT = 3 SECOND TICK 3 = 2 + 1 FUNCTION STOP

THE CURRENT VARIABLE IS AT THE 4 TO LAST NODE, BUT THE PARAMETER “N” WAS PASSED AS VALUE = 2

IT WOULD WORK IF THE LINKED LIST ACTS REVERSED WICH IS WHERE IM BECOMING CONFUSED SINCE I THINK IT DOES.

IF WE MAKE A LINKED LIST LIKE SO:

FOR I IN RANGE(0,10):
LINKED_LIST.INSERT_BEGGINING(I)

THEN IT WOULD START INSERTING NODES LIKE SO :

1

2 1

3 2 1

4 3 2 1 (SINCE WE ARE ADDING THE NODES AT THE BEGINNING)

WE ARE ASSUMING THE PARAMETER “N” TO BE PASSED AS 2 (linked_list.nth_last_node(self, 2)

10 9 8 7 6 5 4 3 2 1

TS 9 8 7 6 5 4 3 2 1 FUNCTION INITIALIZATION COUNT = 1

C TS 8 7 6 5 4 3 2 1 FIRST TICK COUNT = 2

10 C TS 7 6 5 4 3 2 1 SECOND TICK COUNT = 3 3 = n + 1 FUNCTION STOPED

AND NOW THE CURRENT VARIABLE HOLDS THE SECOND NODE STILL

I WOULD NEED SOME HELP UNDERSTANDING THIS CONCEPT PLEASE C:, BECAUSE AS IM SEEING IT, THE CURRENT VARIABLE IS AT THE 8TH TO LAST NODE OF THE LIST.

2

I don’t really care for the OOP linked list thing: it kind of over complicates. Let’s go old school simple:

# build a node
def cons(value, next = None):
    return (value, next)

# build a linked list
head = None
for i in range(5):
    head = cons(i, head)

print(head)

Result:

(4, (3, (2, (1, (0, None)))))

We’ve kind of cheated and used python’s tuple to get what we’re after. However, I think it does a good job of showing what’s going on.

As we have tuples, we can dig down using that:

print("first value", head[0])
print("second value", head[1][0])
print("third value", head[1][1][0])

Result:

first value 4
second value 3
third value 2

For an nth, given what we have, we should be able to do:

def nth_node(xs, n):
    while xs != None and n>1:
        xs = xs[1]
        n -= 1
    return xs

print("third node", nth_node(head, 3))

Result:

third node (2, (1, (0, None)))

Hopefully, this way of looking at it make the concept of the structure a little more clear.

You should be able to roll this idea back into a node with methods. Though, again, don’t get bogged down in those methods.

e.g.

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

    def nth(self, n):
        h = self
        while h != None and n>1:
            h = h.next
            n -= 1
        if h != None:
            return h.value
head = None
for i in range(5):
    head = Node(i, head)

print("third value", head.nth(3))
2 Likes
3

Thanks a lot! I will try and look at this from your perspective (probably more understandable), you kind of broke it down into easier pieces for me thanks again :smiley: