0. Setup `Node`, `LinkedList` & `DoublyLinkedList` Class

from typing import Any

class NodeLL():
    def __init__(self,data: Any|None=None):
        self.data:          Any|None = data
        self.next_node:     NodeLL|None = None

class NodeDLL():
    def __init__(self,data: Any|None=None):
        self.data:          Any|None = data
        self.prev_node:     NodeDLL|None = None
        self.prev_node:     NodeDLL|None = None

class LinkedList():
    def __init__(self, first_node: NodeLL|None=None):
        self.first_node:    NodeLL|None = first_node
        
class DoublyLinkedList():
    def __init__(self, first_node: NodeDLL|None=None,last_node: NodeDLL|None=None):
        self.first_node:    NodeDLL|None = first_node
        self.last_node:     NodeDLL|None = last_node

# classic nodes setup
node0_ll=NodeLL("time")
node1_ll=NodeLL("of")
node2_ll=NodeLL("your")
node3_ll=NodeLL("life")
node0_ll.next_node=node1_ll
node1_ll.next_node=node2_ll
node2_ll.next_node=node3_ll

# doubly nodes setup
node0_dll=NodeDLL("TIME")
node1_dll=NodeDLL("OF")
node2_dll=NodeDLL("YOUR")
node3_dll=NodeDLL("LIFE")

node0_dll.next_node=node1_dll
node1_dll.next_node=node2_dll
node2_dll.next_node=node3_dll

node1_dll.prev_node=node0_dll
node2_dll.prev_node=node1_dll
node3_dll.prev_node=node2_dll

1. Add method: `print_all` to Classic `LinkedList` Class

def print_all_ll(linked_list: LinkedList)-> None:
    current_node = linked_list.first_node

    # case 1: empty list: print empty list
    if not current_node:
        print("Empty LinkedList!")
        return None

    # case 2: len(ll)==1: print ll[0] # captured in case 3
    # if not current_node.next_node:
    #     print(current_node.data)
    #     return None

    # case 3: n items 
    while current_node:
        print(current_node.data)        # print node.data
        current_node = current_node.next_node # go next node
    return None
print_all_ll(LinkedList()) # empty list
print()
print_all_ll(LinkedList(NodeLL("single lonely node"))) # empty list
print()
print_all_ll(LinkedList(node0_ll))

print()

Empty LinkedList!

single lonely node

time
of
your
life

2a. Add method: `print_all_reverse` to `ClassicLinkedList` Class


def print_rev_all_ll(linked_list: LinkedList)-> None:
    current_node = linked_list.first_node
    node_list = []
    # case 1: empty list: print empty list
    if not current_node:
        print("Empty LinkedList!")
        return None
    
    # case n: n items 
    while current_node:
        # print(current_node.data)        # print node.data
        node_list.append(current_node.data)
        current_node = current_node.next_node # go next node
    
    [print(node_list[i]) for i in range(len(node_list)-1,-1,-1)]
    
    return None

# LL - REVERSE
print_rev_all_ll(LinkedList()) # empty list
print()
print_rev_all_ll(LinkedList(NodeLL("single lonely node"))) # empty list
print()
print_rev_all_ll(LinkedList(node0_ll))
print()

# eta: 9 mins
# Comments: used [1.soln], create [node_list] and append each [node.data] then [reverse print]

Empty LinkedList!

single lonely node

life
your
of
time

2b. Add method: `print_all_reverse` to `DoublyLinkedList` Class

def print_rev_all_dll(dbly_linked_list: DoublyLinkedList)-> None:
    current_node = dbly_linked_list.last_node

    # case 1: empty list: print empty list
    if not current_node:
        print("Empty LinkedList!")
        return None

    # case 3: n items 
    while current_node:
        print(current_node.data)        # "last"
        current_node = current_node.prev_node # go prev node
    return None
# DLL REVERSE
print_rev_all_dll(DoublyLinkedList()) # empty list
print()
print_rev_all_dll(DoublyLinkedList( # SINGLE NODE - DLL 
    first_node=NodeDLL("single lonely node"),   # node is first_node
    last_node=NodeDLL("single lonely node")))    # and last_node

print()
print_rev_all_dll(DoublyLinkedList(
    first_node=node0_dll, last_node=node3_dll))
print()

# eta: 15 min 
# comments: 
# - found & fixed bug prev_node assignments, 
# - [2] update assn  current_node -> prev_node and 
# - [12] while loop to update to current_node to prev_node

Empty LinkedList!

single lonely node

LIFE
YOUR
OF
TIME

3a. Add method: `return_last_item` to Classic `LinkedList` Class

Number of Elements: Unknown


def return_last_item_ll(linked_list: LinkedList)-> None:
    current_node = linked_list.first_node
    # node_list = []
    # case 1: empty list: print empty list
    if not current_node:
        print("Empty LinkedList!")
        return None
    
    # case n: n items 
    while current_node.next_node:
        # print(current_node.data)        # print node.data
        # node_list.append(current_node.data)
        current_node = current_node.next_node # go next node
    
    # [print(node_list[i]) for i in range(len(node_list)-1,-1,-1)]
    print(current_node.data)
    # return current_node.data

# LL - last item
return_last_item_ll(LinkedList()) # empty list
print()
return_last_item_ll(LinkedList(NodeLL("single lonely node"))) # empty list
print()
return_last_item_ll(LinkedList(node0_ll))
print()

# eta: 3 mins
# Comments: used [1.soln] [11] while current_next.next_node exist then not last and go next 
# [11/14] if c_node.next_node is falsy, its last node, leave while-loop.

Empty LinkedList!

single lonely node

life

3b. Add recursive method: `return_last_item` to Classic `LinkedList` Class

# recursive attempt - 1
def return_last_item_ll_recursivefn(linked_list: LinkedList)-> None:
    current_node = linked_list.first_node
    if not current_node:
        print("Empty LinkedList!")
        return None
    
    if current_node.next_node:
        current_node = current_node.next_node
        current_linked_list = LinkedList(current_node) # start from next node
        return return_last_item_ll_recursivefn(current_linked_list)
    else:
        print(current_node.data)
        return current_node.data

# 'time','of','your','life'
return_last_item_ll_recursivefn(LinkedList()) # empty list
print()
return_last_item_ll_recursivefn(LinkedList(NodeLL("single lonely node")))
print()
return_last_item_ll_recursivefn(LinkedList(node0_ll))
print()

# eta: 20 mins
# comments: had to remind myself how recursive functions work
# [10] then thought of creating a new list each time current_node updates
# bad but worked

Empty LinkedList!

single lonely node

life

3c. Add recursive method: `return_last_item` with `Nodes`

# recursive attempt - 2
def return_last_item_nodes_recursivefn(current_node: NodeLL)-> None:
    # current_node = linked_list.first_node
    if not current_node.data:
        print("Empty Node!")
        return None
    
    if current_node.next_node:
        current_node = current_node.next_node
        # current_linked_list = LinkedList(current_node) # start from next node
        return return_last_item_nodes_recursivefn(current_node)
    else:
        print(current_node.data)
        return current_node.data

# 'time','of','your','life'
return_last_item_nodes_recursivefn(NodeLL()) # empty list
print()
return_last_item_nodes_recursivefn((NodeLL("single lonely node")))
print()
return_last_item_nodes_recursivefn(node0_ll)
print()

# eta: 2mins
# comments: adapt first attempt and remove the creation of lists.

Empty Node!

single lonely node

life

[ignore] 3d. Re-wrote to help me attempt 3b and 3c

def max_val(arr):
    if len(arr)==1:
        return arr[0]
    
    if arr[0]>max_val(arr[1:]):
        return arr[0]
    else:    
        return max_val(arr[1:])
    
arr=[1,7,3,5,9,4,8,3]    
max_val(arr)

4. Add method: `reverse_linkedlist`

original list: A -> B -> C
reversed list: C -> B -> A.

def reverse_ll(linked_list: LinkedList):
    current_node = linked_list.first_node
    previous_node = None
    
    if not current_node:
        print("Empty Linked List!")
        
    while current_node:
        # A->B->C->
        # 1. <-A POINT A TO PREVIOUS NODE
        # 1.  BUT CANT DO THAT YET, BECAUSE WONT HAVE ACCESS
        #     TO NEXT NODE FOR ITERATION
        # 1A. SO SAVE [NEXT_NODE], 
        # 1B. then CURR.NEXT IS [PREV]  <-A 
        # 2.  update [PREV]
        # 3.  update [CURR]  
        next_node=current_node.next_node        # 1A.   B=A.NEXT
        previous_node = current_node.next_node  # 1B.   A.NEXT=PREV
        current_node = previous_node            # 2.    PREV = A   
        current_node = next_node                # 3.    CURR = CURR.NEXT
        
    return linked_list

# 'time','of','your','life'
reverse_ll(LinkedList()) # empty list
print()

ll = LinkedList(NodeLL("single lonely node"))
reverse_ll(ll)
print_rev_all_ll(ll)

print()
ll = LinkedList(node0_ll)
reverse_ll(ll)
print_rev_all_ll(ll)
print()

#eta: 25m
#comments: definitely helped writign it down step by step 
# rather than trying to do it all in my head, see the comments

Empty Linked List!

single lonely node

life
your
of
time

5. Delete Current Node Puzzle

List-Type:

LinkedList Class

Scenario:

You have access to a node from somewhere in the middle of a classic linked list but not to the linked list itself;
You have a variable that points to an instance of Node, but you don’t have access to the LinkedList instance.
Write code that will effectively delete this node from the list.
The entire remaining list should remain complete, with only this node removed.

def delete_node_ll(current_node: NodeLL)->None:
    # A -> B -> C -> D
    # Delete current_node: [B]
    # A ->   -> C -> D
    # A -> C -> D
        
    # C.data into B.data
    # D.data into C.data
    # None into D.data
    if not current_node.data:
        print("Empty Node!")
        return None
    
    while current_node.next_node: # STOPS AT CN=D, LAST ENTERS CN=C
        current_node.data = current_node.next_node.data #B, C,
        # print(f"NEW_CURRENT_DATA: {current_node.data}")
        current_node=current_node.next_node
    current_node.data = None 
    # print(f"NEW_CURRENT_DATA: {current_node.data}")
    return None

# classic nodes setup
node0_ll=NodeLL("A")
node1_ll=NodeLL("B")
node2_ll=NodeLL("C")
node3_ll=NodeLL("D")
node0_ll.next_node=node1_ll
node1_ll.next_node=node2_ll
node2_ll.next_node=node3_ll
ll = LinkedList(node0_ll)
print(f"Before Deleting 'B'")
print_all_ll(ll)
delete_node_ll(node1_ll)
print()
print(f"After Deleting 'B'")
print_all_ll(ll)
# print()
# print()
# ll = LinkedList(node0_ll)
# reverse_ll(ll)
# print_rev_all_ll(ll)
# print()

Before Deleting 'B'
A
B
C
D

After Deleting 'B'
A
C
D
None

0. Setup Node, LinkedList & DoublyLinkedList Class

1. Add method: print_all to Classic LinkedList Class

2a. Add method: print_all_reverse to ClassicLinkedList Class

2b. Add method: print_all_reverse to DoublyLinkedList Class

3a. Add method: return_last_item to Classic LinkedList Class

3b. Add recursive method: return_last_item to Classic LinkedList Class

3c. Add recursive method: return_last_item with Nodes

[ignore] 3d. Re-wrote to help me attempt 3b and 3c

4. Add method: reverse_linkedlist

5. Delete Current Node Puzzle

0. Setup `Node`, `LinkedList` & `DoublyLinkedList` Class

1. Add method: `print_all` to Classic `LinkedList` Class

2a. Add method: `print_all_reverse` to `ClassicLinkedList` Class

2b. Add method: `print_all_reverse` to `DoublyLinkedList` Class

3a. Add method: `return_last_item` to Classic `LinkedList` Class

3b. Add recursive method: `return_last_item` to Classic `LinkedList` Class

3c. Add recursive method: `return_last_item` with `Nodes`

4. Add method: `reverse_linkedlist`