I am just starting up to learn the more advanced data structures of programming (node, linked list, etc), and I can't seem to understand/grasp the logic of it completely. I could see and understand how it's supposed to work (how it could traverse and such), but when I try to understand each line of code, I can't seem to understand it clearly.
class node:
def __init__(self,data = None):
self.data = data
self.next = None
class linked_list:
def __init__(self):
self.head = node()
def append(self,data):
new_node = node(data)
cur = self.head #self.head is like the arrow/pointer that's going to pierce/traverse through the llist
while cur.next != None:
cur = cur.next
cur.next = new_node
def length(self):
cur = self.head
total_length = 0
while cur.next != None:
total_length += 1
cur = cur.next
return total_length
def display(self):
elems = []
cur_node = self.head
while cur_node.next != None:
cur_node = cur_node.next
elems.append(cur_node.data)
print (elems)
my_list = linked_list()
my_list.append(1)
my_list.append(2)
my_list.append(3)
print(f'The length of the linked list is {my_list.length()}')
my_list.display()
This is a short linked list system I have made and it is based on a course I've followed on Youtube. I understand how it's supposed to traverse through the node by finding the point where the .next or pointer in a node is None as in The end of the node.
But, as such, I'm still confused on a certain thing:
Why do we need class linked_list: and its self.head = node()? Why can't I just do my_list = node()
On each of the functions, there are similar blocks of code:
while cur.next != None:
cur = cur.next
I understand that the function of this code is to move to the next node by changing the current "head" to the next node.
Now the cur is on the .next, but how is this able to change the .next values sequentially through the node after that?
Consider what happens if you want to have two variables that refer to the same linked list. If you don't have the linked_list class, the variables will have to contain references to the first node in the list. So you do something like:
list_1 = node(1)
list_1.next = node(2)
list_2 = list_1
Now suppose you want to remove the first element of the list, so you do:
list_1 = list_1.next
But list_2 still refers to the first node in the original list.
Adding the linked_list container class allows you to treat lists as items distinct from the nodes that they use to implement them.
There's also an more conceptual reason: "list" is a higher level of abstraction. You could decide to change the representation from linked nodes to a linear array, and the callers would not need to change. Object-oriented programming facilitates this kind of information hiding -- users of a class just need to know what it does for them, not how it does it.