DSA 35: LinkedList - Insert & Delete [Part 3]

1. Setup Linkedlist and Node Objects

Previously introduced.

class Node():
    def __init__(self, data):
        self.data=data
        self.next_node=None

class LinkedList():
    def __init__(self, first_node:Node|None=None):
        self.first_node: Node|None = first_node

node0=Node("Hey")
node1=Node("I")
node2=Node("Just")
node3=Node("Met")
node0.next_node=node1
node1.next_node=node2
node2.next_node=node3

2. Read from LinkedList

Previously introduced

2.1 Read(0) or Top

def read_top_ll(linked_list: LinkedList, index: int):
    current_node = linked_list.first_node 
    return current_node.data

ll = LinkedList(node0)
read_top_ll(ll,0)

'Hey'

2.2 Read Index of LinkedList

2.3 Add Base-Case: Read(0)

def read_ll_forloop(linked_list: LinkedList, index: int):
    current_node = linked_list.first_node 
    
    if index==0:
        return current_node.data
    
    for i in range(index+1):
        print(i)
        if i==index:
            return current_node.data
        current_node=current_node.next_node
    return None

ll = LinkedList(node0)
read_ll_forloop(ll,0)

'Hey'

2.4 Read(1)

def read_ll_whileloop(linked_list: LinkedList, index: int):
    current_node = linked_list.first_node 
    
    if index==0:
        return current_node.data
    i=0    
    while current_node: # for i in range(index+1):
        if i==index:
            return current_node.data
        current_node=current_node.next_node
        i+=1
    return None

ll = LinkedList(node0)
read_ll_whileloop(ll,1)

'I'

2.5 Read All - LinkedList to Python List

def read_all_ll_whileloop(linked_list: LinkedList):
    current_node = linked_list.first_node 
    ll_list = []
    while current_node: # for i in range(index+1):
        ll_list.append(current_node.data)
        current_node=current_node.next_node
        
    return ll_list

ll = LinkedList(node0)
read_all_ll_whileloop(ll)

['Hey', 'I', 'Just', 'Met']

3. Insert from LinkedList

3.1 Insert(0) or Top

def insert_front_ll_forloop(linked_list: LinkedList, index: int,
                            new_node: Node):
    
    current_node = linked_list.first_node 
    if index==0:
        new_node.next_node = current_node
        linked_list.first_node=new_node
    
    # for i in range(index+1):
    #     print(i)
    #     if i==index:
    #         return current_node.data
    #     current_node=current_node.next_node
    # return None


ll = LinkedList(node0)
insert_front_ll_forloop(ll,0,Node("mate"))
print(read_all_ll_whileloop(ll))

['mate', 'Hey', 'I', 'Just', 'Met']

3.2 Create New LinkedList for Each Test

def reset_ll():
    node0=Node("Hey")
    node1=Node("I")
    node2=Node("Just")
    node3=Node("Met")
    node0.next_node=node1
    node1.next_node=node2
    node2.next_node=node3
    ll = LinkedList(node0)
    return ll

3.3 Insert(Index)

3.3.1 Insert(Index): for-loop version

def insert_ll_forloop(linked_list: LinkedList, index: int,
                            new_node: Node):
    
    current_node = linked_list.first_node 
    if index==0:
        new_node.next_node = current_node
        linked_list.first_node=new_node
    
    for i in range(index+1):
        if i==index-1:
            new_node.next_node = current_node.next_node
            current_node.next_node = new_node
            # return current_node.data
        current_node=current_node.next_node
    return None

ll = reset_ll()
insert_ll_forloop(ll,0,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
insert_ll_forloop(ll,1,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
insert_ll_forloop(ll,2,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
insert_ll_forloop(ll,3,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
insert_ll_forloop(ll,4,Node("YOU")) 
print(read_all_ll_whileloop(ll))

ll = reset_ll()
print("OUT-OF-INDEX ERROR EXPECTED NEXT RUN")
insert_ll_forloop(ll,5,Node("YOU"))  # OUT OF INDEX ERROR EXPECTED 
print(read_all_ll_whileloop(ll))

#hey i just met

['YOU', 'Hey', 'I', 'Just', 'Met']
['Hey', 'YOU', 'I', 'Just', 'Met']
['Hey', 'I', 'YOU', 'Just', 'Met']
['Hey', 'I', 'Just', 'YOU', 'Met']
['Hey', 'I', 'Just', 'Met', 'YOU']
OUT-OF-INDEX ERROR EXPECTED NEXT RUN

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[41], line 39
     37 ll = reset_ll()
     38 print("OUT-OF-INDEX ERROR EXPECTED NEXT RUN")
---> 39 insert_ll_forloop(ll,5,Node("YOU"))  # OUT OF INDEX ERROR EXPECTED 
     40 print(read_all_ll_whileloop(ll))
     42 #hey i just met

Cell In[41], line 11, in insert_ll_forloop(linked_list, index, new_node)
      9 for i in range(index+1):
     10     if i==index-1:
---> 11         new_node.next_node = current_node.next_node
     12         current_node.next_node = new_node
     13         # return current_node.data

AttributeError: 'NoneType' object has no attribute 'next_node'

3.3.2 Insert(Index): while-loop version 1 (No Out-of-Index Error)

def insert_ll_WHILELOOP_v1(linked_list: LinkedList, index: int,
                            new_node: Node):
    
    current_node = linked_list.first_node 
    if index==0:
        new_node.next_node = current_node
        linked_list.first_node=new_node
    i=0
    while current_node:
        if i==index-1:
            new_node.next_node = current_node.next_node
            current_node.next_node = new_node
        current_node=current_node.next_node
        i+=1
    return None

ll = reset_ll()
print(read_all_ll_whileloop(ll))
insert_ll_WHILELOOP_v1(ll,0,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
insert_ll_WHILELOOP_v1(ll,1,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
insert_ll_WHILELOOP_v1(ll,2,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
insert_ll_WHILELOOP_v1(ll,3,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
insert_ll_WHILELOOP_v1(ll,4,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
print("NO ERROR EXPECTED NEXT RUN DESPITE OUT OF INDEX - NEED TO UPDATE FN")
insert_ll_WHILELOOP_v1(ll,5,Node("YOU"))  # ERROR EXPECTED BUT NO ERROR DUE TO while current_node
print(read_all_ll_whileloop(ll))

['Hey', 'I', 'Just', 'Met']
['YOU', 'Hey', 'I', 'Just', 'Met']
['Hey', 'YOU', 'I', 'Just', 'Met']
['Hey', 'I', 'YOU', 'Just', 'Met']
['Hey', 'I', 'Just', 'YOU', 'Met']
['Hey', 'I', 'Just', 'Met', 'YOU']
NO ERROR EXPECTED NEXT RUN DESPITE OUT OF INDEX - NEED TO UPDATE FN
['Hey', 'I', 'Just', 'Met']

3.3.3 Insert(Index): while-loop version 2 (Includes Out-of-Index Error)

def insert_ll_WHILELOOP(linked_list: LinkedList, index: int,
                            new_node: Node):
    
    current_node = linked_list.first_node 
    if index==0:
        new_node.next_node = current_node
        linked_list.first_node=new_node
        return None
    i=0
    while i<index-1:
        current_node=current_node.next_node
        i+=1
    # print(current_node.data)    
    new_node.next_node = current_node.next_node
    current_node.next_node = new_node
    return None
#i=1, index=1
#exit while at (index-1) 0 -> 'Hey'
# ['Hey', 'I', 'Just', 'Met']

# ll = reset_ll()
# print(read_all_ll_whileloop(ll))
# insert_ll_WHILELOOP(ll,0,Node("YOU"))
# print(read_all_ll_whileloop(ll))

ll = reset_ll()
insert_ll_WHILELOOP(ll,1,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
insert_ll_WHILELOOP(ll,2,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
insert_ll_WHILELOOP(ll,3,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
insert_ll_WHILELOOP(ll,4,Node("YOU"))
print(read_all_ll_whileloop(ll))

ll = reset_ll()
print("OUT-OF-INDEX ERROR EXPECTED NEXT RUN")
insert_ll_WHILELOOP(ll,5,Node("YOU")) # OUT OF INDEX ERROR EXPECTED 
print(read_all_ll_whileloop(ll))

['Hey', 'YOU', 'I', 'Just', 'Met']
['Hey', 'I', 'YOU', 'Just', 'Met']
['Hey', 'I', 'Just', 'YOU', 'Met']
['Hey', 'I', 'Just', 'Met', 'YOU']
OUT-OF-INDEX ERROR EXPECTED NEXT RUN

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[45], line 44
     42 ll = reset_ll()
     43 print("OUT-OF-INDEX ERROR EXPECTED NEXT RUN")
---> 44 insert_ll_WHILELOOP(ll,5,Node("YOU")) # OUT OF INDEX ERROR EXPECTED 
     45 print(read_all_ll_whileloop(ll))

Cell In[45], line 14, in insert_ll_WHILELOOP(linked_list, index, new_node)
     12     i+=1
     13 # print(current_node.data)    
---> 14 new_node.next_node = current_node.next_node
     15 current_node.next_node = new_node
     16 return None

AttributeError: 'NoneType' object has no attribute 'next_node'

4. Delete from LinkedList

4.1 Delete(0) or Top

# [Hey', 'I', 'Just', 'Met']
# del 0 ->  'I', 'Just', 'Met'

def delete_top_ll(linked_list: LinkedList, index=0):
    current_node = linked_list.first_node
    if index==0:
        linked_list.first_node=current_node.next_node

ll = reset_ll()
print(read_all_ll_whileloop(ll))
delete_top_ll(ll,index=0)
print(read_all_ll_whileloop(ll))

['Hey', 'I', 'Just', 'Met']
['I', 'Just', 'Met']

4.2 Delete(Index)

4.2.1 Delete(Index): for-loop version

def delete_node_ll_FORLOOP(linked_list: LinkedList, index=0):
    current_node = linked_list.first_node
    if index==0:
        linked_list.first_node=current_node.next_node

    for i in range(index):
        if i==index-1:
            next_node = current_node.next_node
            current_node.next_node = next_node.next_node
        current_node=current_node.next_node

# ['Hey', 'I', 'Just', 'Met']
# ['Hey'     , 'Just', 'Met']

ll = reset_ll()
print(read_all_ll_whileloop(ll))
delete_node_ll_FORLOOP(ll,index=0)
print(read_all_ll_whileloop(ll))

print()
ll = reset_ll()
print(read_all_ll_whileloop(ll))
delete_node_ll_FORLOOP(ll,index=1)
print(read_all_ll_whileloop(ll))

print()
ll = reset_ll()
print(read_all_ll_whileloop(ll))
delete_node_ll_FORLOOP(ll,index=2)
print(read_all_ll_whileloop(ll))

print()
ll = reset_ll()
print(read_all_ll_whileloop(ll))
delete_node_ll_FORLOOP(ll,index=3)
print(read_all_ll_whileloop(ll))

print()
ll = reset_ll()
print(read_all_ll_whileloop(ll))
print("OUT-OF-INDEX ERROR EXPECTED NEXT RUN")
delete_node_ll_FORLOOP(ll,index=4) # OUT OF INDEX ERROR EXPECTED 
print(read_all_ll_whileloop(ll))

['Hey', 'I', 'Just', 'Met']
['I', 'Just', 'Met']

['Hey', 'I', 'Just', 'Met']
['Hey', 'Just', 'Met']

['Hey', 'I', 'Just', 'Met']
['Hey', 'I', 'Met']

['Hey', 'I', 'Just', 'Met']
['Hey', 'I', 'Just']

['Hey', 'I', 'Just', 'Met']
OUT-OF-INDEX ERROR EXPECTED NEXT RUN

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[46], line 42
     40 print(read_all_ll_whileloop(ll))
     41 print("OUT-OF-INDEX ERROR EXPECTED NEXT RUN")
---> 42 delete_node_ll_FORLOOP(ll,index=4) # OUT OF INDEX ERROR EXPECTED 
     43 print(read_all_ll_whileloop(ll))

Cell In[46], line 9, in delete_node_ll_FORLOOP(linked_list, index)
      7 if i==index-1:
      8     next_node = current_node.next_node
----> 9     current_node.next_node = next_node.next_node
     10 current_node=current_node.next_node

AttributeError: 'NoneType' object has no attribute 'next_node'

4.2.2 Delete(Index): while-loop version

def delete_node_ll_WHILELOOP(linked_list: LinkedList, index=0):
    current_node = linked_list.first_node
    if index==0:
        linked_list.first_node=current_node.next_node
    i=0
    while current_node: # for i in range(index):
        if i==index-1:
            # next_node = current_node.next_node.next_node
            # current_node.next_node = next_node.next_node
            current_node.next_node = current_node.next_node.next_node
            # current_node.next_node = next_node.next_node
        current_node=current_node.next_node
        i+=1
ll = reset_ll()
print(read_all_ll_whileloop(ll))
delete_node_ll_WHILELOOP(ll,index=0)
print(read_all_ll_whileloop(ll))
print()

ll = reset_ll()
print(read_all_ll_whileloop(ll))
delete_node_ll_WHILELOOP(ll,index=1)
print(read_all_ll_whileloop(ll))
print()

ll = reset_ll()
print(read_all_ll_whileloop(ll))
delete_node_ll_WHILELOOP(ll,index=2)
print(read_all_ll_whileloop(ll))
print()

ll = reset_ll()
print(read_all_ll_whileloop(ll))
delete_node_ll_WHILELOOP(ll,index=3)
print(read_all_ll_whileloop(ll))
print()

ll = reset_ll()
print(read_all_ll_whileloop(ll))
print("OUT-OF-INDEX ERROR EXPECTED NEXT RUN")
delete_node_ll_WHILELOOP(ll,index=4) # OUT OF INDEX ERROR EXPECTED 
print(read_all_ll_whileloop(ll))

['Hey', 'I', 'Just', 'Met']
['I', 'Just', 'Met']

['Hey', 'I', 'Just', 'Met']
['Hey', 'Just', 'Met']

['Hey', 'I', 'Just', 'Met']
['Hey', 'I', 'Met']

['Hey', 'I', 'Just', 'Met']
['Hey', 'I', 'Just']

['Hey', 'I', 'Just', 'Met']
OUT-OF-INDEX ERROR EXPECTED NEXT RUN

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[47], line 41
     39 print(read_all_ll_whileloop(ll))
     40 print("OUT-OF-INDEX ERROR EXPECTED NEXT RUN")
---> 41 delete_node_ll_WHILELOOP(ll,index=4) # OUT OF INDEX ERROR EXPECTED 
     42 print(read_all_ll_whileloop(ll))

Cell In[47], line 10, in delete_node_ll_WHILELOOP(linked_list, index)
      6 while current_node: # for i in range(index):
      7     if i==index-1:
      8         # next_node = current_node.next_node.next_node
      9         # current_node.next_node = next_node.next_node
---> 10         current_node.next_node = current_node.next_node.next_node
     11         # current_node.next_node = next_node.next_node
     12     current_node=current_node.next_node

AttributeError: 'NoneType' object has no attribute 'next_node'