Linked List in Python [Notes]

Trying to understand Linked List from an undergrads perspective…

So what is a Linked List?
• A linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer.

#linked list by constructor.

empty = []  
def   is_link(s):      
     return s == empty or (len(s) == 2 and is_link(s[1]))  
 def   link(first, rest):          
     assert is_link(rest), "rest must be a linked list."      
     return [first, rest] 

#Representation in Python using 2-elements list  

def   first(s):          
     assert is_link(s), "first only applies to linked lists."      
     assert s != empty, "empty linked list has no first element."     
     return s[0]  
def   rest(s):     
    assert is_link(s), "rest only applies to linked lists."      
    assert s != empty, "empty linked list has no rest."      
    return s[1] 

def   len_link(s):      
    length = 0                         
    while s != empty:                               
       s, length = rest(s), length + 1              
    return length

generally, in a while loop, you need an index and at the end of the while block, we need to update the index.

It won’t count the empty nodes.

a = [123, []]
len_link(a)
=> 1

def getitem_link(s, i):    #s = [1, [2,[3,[]]]], i = 2  
    while i > 0:          # 2 > 0 -> 1 > 0 -> 0 !> 0
        s,  i = rest(s),  i - 1    #s = [2,[3,[]]], i = 1 -> s=…