Linked Lists¶

class Node:
    def __init__(self, cargo=None, next=None):
        self.cargo = cargo
        self.next = next
        
    def __str__(self):
        return str(self.cargo)

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

node1.next = node2
node2.next = node3

def print_list(node):
    while node is not None:
        print(node, end=" ")
        node = node.next
    print()

def print_backward(alist):
    if alist is None:
        return
    head = alist
    tail = alist.next
    print_backward(tail)
    print(head, end=" ")

# function that removes the second node in the list and returns reference to the removed node
def remove_second(alist):
    if alist is None: return
    first = alist
    second = alist.next
    # Make the first node point to the third
    first.next = second.next
    # Separate the second node from the rest of the list
    second.next = None
    return second

removed = remove_second(node1)

def print_backward_nicely(alist):
    print("[", end=" ")
    print_backward(alist)
    print("]")

class LinkedList(object):
    def __init__(self):
        self.length = 0
        self.head = None
        self.tail = None
        
    def append(self, data):
        node = Node(data)
        if not self.head: # empty linked list
            # make the first and last point to the new node
            self.head = node
            self.tail = node
        else:
            self.tail.next = node # make the current tail's next node point to the new node
            self.tail = node # node is the last node
        self.length += 1
        
    def __str__(self):
        """
        traverse linked list and return all the cargos/data
        """
        llist = list()
        current = self.head
        while current:
            llist.append(current.cargo)
            current = current.next
        return str(llist)
    
    def print(self):
        current = self.head
        while current is not None:
            print(current, end=" ")
            current = current.next
        print()
        
    def print_reverse(self):
        current = self.head
        if not current:
            return
        print_backward(current.next)
        print(current, end=" ")
            
    def find(self, data):
        # find and return the node with given data
        current = self.head
        found = False
        while (current and not found):
            if current.cargo == data:
                found = True
            else:
                current = current.next
        return current
        
            
    def remove(self, data):
        """
        We need to consider several cases:
        Case 1: the list is empty - do nothing
        Case 2: The first node is the node with the given cargo/data, we need to adjust head and may be tail
        Case 3: The node with the given info is somewhere in the list. 
            i. find the node and delete
            ii. If the node to be deleted is the tail,
                we must adjust tail.
        Case 4: The list doesn't contain a node with the given info - do nothing
        """
        # case 1
        if not self.head:
            return # done
        # case 2
        if self.head.cargo == data:
            self.head = self.head.next # 2nd node becomes the head
            # if list becomes empty; update tail as well
            if not self.head:
                self.tail = None
            self.length -= 1
        else:
            # search the list for the node with given data
            found = False
            trailCurrent = self.head # first node
            current = self.head.next # second node
            while(current and not found):
                if current.cargo == data:
                    found = True
                else:
                    trailCurrent = current
                    current = current.next
            if found: #case 3
                trailCurrent.next = current.next
                if self.tail is current:
                    self.tail = trailCurrent
                self.length -= 1
            else: # case 4
                return
        
    def clear(self):
        self.length = 0
        self.head = None
        self.tail = None
        
    def __len__(self):
        return self.length

node = alist.find('cat')

node.cargo = 'Cat'

alist.remove('dog')