<jupyter_start><jupyter_text>Data Structures - Linked ListsA linked list is a sequence of individual data elements called Nodes, which are connected via links. Each data element contains a connection to another data element in the form of a pointer. Visually we can think of a node like the following:A collection of nodes is called a list, and can be visualized as the following:The first node is a particular node that we call the head, or in other words, it is the first chain in the link of nodes. Advantages1. Linked Lists are dynamic, meaning it can grow and shrink at runtime by allocating and deallocating memory. Meaning there is no requirement to give the initial size of the list.2. Insertion and deletion operations are more natural than with arrays. We don't have to shift nodes like array insertion. In Insertion operation in a linked list, we have to update the next link of the node.3. It doesn't waste memory, meaning that it only takes the memory needed to store all nodes. On the other side, arrays can take up more memory than needed. For example, if we declare an array to store six values but only put four values in it, we are wasting the remaining two place holders in memory. To be clear, this does not mean a linked list uses less memory; it just means it uses the memory efficiently. Why Use Linked ListsOften linked lists will be compared to arrays, but different features allow linked lists to stand out from normal arrays. Disadvantages1. Accessing a node is time-consuming. When looking for a value in a linked list, you have to start from the beginning of the chain and check one element at a time for the value you're looking for. If the linked list is n elements long, this can take **up to n time**.2. It takes up more memory than an array. This is because it contains a pointer to the next node, with an array we don't have the pointer because it is stored in memory sequentially. Performance| Data Structure | Average Insert | Average Delete | Average Search | Worst Insert | Worst Delete | Worst Search ||----------------|----------------|----------------|----------------|--------------|--------------|--------------|| Linked List    | O(1)           | O(1)           | O(n)           | O(1)         | O(1)         | O(n)         |<jupyter_code># the basis of a linked list is the node object. A linked list can be made up of multiple nodes.
# we need our node to do a couple of things, return the data inside it, get the node next to it if there is one and 
# set the node next to it

class Node(object):

    # every node starts off with a piece of data, and we define the node next to it.
    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node

        
    # this will return the data in the current node we are on.
    def get_data(self):
        return self.data
    

    # this grabs the next node.
    def get_next(self):
        return self.next_node
    

    # this sets the next node.
    def set_next(self, new_next):
        self.next_node = new_next


        
class LinkedList(object):
    
    def __init__(self, head = None, end = None):        
        self.head = head
        self.end = end
        
        
    def insert_front(self, data):
        '''
            Insert a node at the beginning of our list
            Time Complexity: O(1) 
        '''
        
        # define a new node
        new_node = Node(data)
        
        # the second node will be the old first one
        new_node.set_next(self.head)
        
        # the new head will be the new node
        self.head = new_node
        
        
    def insert_end(self, data):        
        '''
            Insert a node at the end of our list.
            Time Complexity: Θ(1) when last element is known,
                             Θ(n) when last element is unknown
        '''
        
        # define a new node and the head node
        new_node = Node(data)
        head_node = self.head
        
        # if there isn't a head node then the head node will be the last node
        if head_node is None:
            head_node = new_node
            return
        
        # otherwise, let's find the last node
        last_node = head_node

        # as long as there is a "next" node that means we haven't reached the end
        while last_node.get_next() != None:        
            last_node = last_node.get_next()
        
        # when we have reached the end, set the next node to the new node we created above.
        last_node.set_next(new_node)
        self.end = new_node
        
        
    def insert_middle(self, middle_node, data):
        '''
            Insert a node in the middle of our list
            Time Complexity: search time + Θ(1) 
        '''        
        
        if middle_node is None:
            print("The node you've selected does not exist.")
        
        new_node = Node(data)
        new_node.set_next(middle_node.get_next())
        middle_node.set_next(new_node)
        
        
    def list_size(self):
        '''
            Return the list size
            Time Complexity: O(n) 
        '''
        
        current_node = self.head        
        current_count = 0
        
        while current_node:            
            current_count += 1
            current_node = current_node.get_next()
            
        return current_count
    
    
    def search_list(self, value):
        '''
            Search the list and return all the nodes that contain a given value.
            Time Complexity: O(n) 
        '''
        
        current_node = self.head
        previous_node = None
        result_list = []
        
        # if the head node is none, then we can just exit early.
        if current_node == None:
            return
        
        # if it's not none then start searching for the value.
        # there are two conditions where we stop traversing the node.
        # 1st. The current node is None, which means we've reached the end.
        # 2nd. We found the value so we continue you on to deletion
        while current_node != None:
            
            if current_node.data == value:                
                result_list.append(current_node)
                previous_node = current_node
                current_node = current_node.get_next()   
                
            else:
                previous_node = current_node
                current_node = current_node.get_next()   

        return result_list
    

    def delete_list(self): 
        '''
            Delete the entire list itself.
            Time Complexity: O(n) 
        '''
        
        # initialize the current node 
        current = self.head 
        
        while current: 
            
            # grab the next node
            next_node = current.next_node 
              
            # delete the current node 
            del current.data 
              
            # set current equal to the next node 
            current = next_node 
            
            
    def delete_node(self, value):
        '''
            Delete the first instance of a value.
            Time Complexity: O(1) when at beginning, 
                             O(1) when at end and element is known, 
                             O(n) when at end and element is unknown,
                             search time + Θ(1) when in middle
        '''
        
        current_node = self.head
        found = False
        previous_node = None
        
        # if the head node is none, then we can just exit early.
        if current_node == None:
            return
        
        # if it's not none then start searching for the value.
        # there are two conditions where we stop traversing the node.
        # 1st. The current node is None, which means we've reached the end.
        # 2nd. We found the value so we continue you on to deletion
        while current_node != None and found is False:
            
            if current_node.data == value:
                found == True
                break
                
            else:
                previous_node = current_node
                current_node = current_node.get_next() 

                
        # if it wasn't found let the user know.
        if current_node is None:
            raise ValueError("Data not in list")
            
        # if it was found then delete it.
        if previous_node is None:
            # if the head node contains the value, jump it and set the next node to be the head node.
            self.head = current_node.get_next()
        else:
            # if isn't the head node then take the previous node and set it as the next node.
            previous_node.set_next(current_node.get_next())

        
    def traverse(self):        
        '''
            Traverse the list and print each value.
            Time Complexity: O(n)
        '''
        
        # first define the node
        node = self.head
        
        while node != None:
            
            # print the node and then set the new node equal to the next one.
            # if the next one doesn't equal none (there is no value after it) then it
            # will keep printing
            print(node.get_data())
            node = node.get_next()
         
        
    def remove_duplicates(self):
        '''
            Remove duplicate values from the list.
            Time Complexity: O(n) on average (assuming that hash table access time is O(1) on average).
        '''
        
        # grab the first node and the node after the first
        previousNode = self.head
        currentNode = previousNode.next_node
        
        # build a set to store non-duplicate values
        keys = set([previousNode.data])
        
        while currentNode:
            
            data = currentNode.data
            
            # if it is a duplicate
            if data in keys:
                
                # have the previous node's next pointer by pass the current node and point to the node after it.
                previousNode.next_node = currentNode.next_node
                
                # set up for the next run
                currentNode = currentNode.next_node
                
            else:
                
                # else it was a unique value so add it to the set
                keys.add(data)
                
                # reassign the nodes
                previousNode = currentNode
                currentNode = currentNode.next_node
                
            
    def kth_to_last(self, k):
        '''
            Return kth to the last elements of our list.
            Time Complexity: O(n) 
        '''        
        
        # if k is negative just return nothing
        if k < 0:
            return None
        
        # if k is 0 just print the whole list
        if k == 0:
            self.traverse()
            return
           
        # grab the list length
        list_length = self.list_size()
            
        # in the situaiton where they give us a K larger then the list length, pass back an error.
        if k > list_length:
            print("You chose a K which is longer than the list.")
        
        # start from the beginning
        p1 = self.head
        
        # go from position 1 to the end of the list
        for i in range(1, list_length + 1):
            if i >= k:
                print(p1.data) 
                p1 = p1.next_node
            else:
                p1 = p1.next_node
                
                

    def sum_linked_list(self, linked_list):
        '''
            Sum two individual linked lists.
            Time Complexity: O(m + n) where m and n are number of nodes in first and second lists respectively.
        '''
        
        # define the total
        total = 0
        
        # grab the first node from each list
        p1 = self.head
        p2 = linked_list.head
        
        # sum all the value's from list 1
        while p1:
            if isinstance(p1.data,(int, float)):
                total = total + p1.data
                p1 = p1.get_next()
            else:
                p1 = p1.get_next()
        
        # sum all the value's from list 2
        while p2:
            if isinstance(p2.data,(int, float)):
                total = total + p2.data
                p2 = p2.get_next()
            else:
                p2 = p2.get_next()
        
        return total
# let's first define a linked list
linked_list = LinkedList()
linked_list2 = LinkedList()

linked_list2.insert_front(35)
linked_list2.insert_front(35)
linked_list2.insert_front(37)
linked_list2.insert_front(37)

# insert some nodes
linked_list.insert_front(35)
linked_list.insert_front(35)
linked_list.insert_front(37)
linked_list.insert_front(37)
linked_list.insert_end(90)
linked_list.insert_end('Bob')
linked_list.insert_end(35)

# insert a node inbetween two nodes. First define the node we want to insert the value after
second_node = linked_list.head.get_next()

# insert the value
linked_list.insert_middle(second_node, 50)

# traverse our list, to print out the values
linked_list.traverse()

# grab the last data point
linked_list.end.data

# determine the size of the linked list
linked_list.list_size()

# delete a value from the linked list
print('-'*50)
linked_list.delete_node(90)

# traverse our list, to print out the values
linked_list.traverse()

# search the list for a value
linked_list.search_list(20)

# remove duplicates
linked_list.remove_duplicates()

# traverse the list without duplicates
print('-'*50)
linked_list.traverse()

# clear the list
linked_list.delete_list()

# print out the head, should return an error now.
linked_list.head.data

print('-'*50)
linked_list.kth_to_last(3)

linked_list.sum_linked_list(linked_list2)<jupyter_output>37
37
50
35
35
90
Bob
35
--------------------------------------------------
37
37
50
35
35
Bob
35
--------------------------------------------------
37
50
35
Bob
35
{'fraction_non_alphanumeric': 0.07153534059363656, 'fraction_numerical': 0.008968609865470852, 'mean_word_length': 1.5936865423666235, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '372415', 'license': 'MIT', 'n_tokens_mistral': 3726, 'n_tokens_neox': 3567, 'n_words': 1522, 'path': 'data structures/Linked List.ipynb', 'repo_name': 'nsethtyler/sigma_coding_youtube', 'size': '14049'}