Well done!
      You have completed Introduction to Data Structures!
      
    
You have completed Introduction to Data Structures!
      Instruction
      
            
    Linked Lists Operations
Python
Singly Linked List
class Node:
    """
    An object for storing a single node in a linked list
    Attributes:
        data: Data stored in node
        next_node: Reference to next node in linked list
    """
    def __init__(self, data, next_node = None):
        self.data = data
        self.next_node = next_node
    def __repr__(self):
        return "<Node data: %s>" % self.data
class SinglyLinkedList:
    """
    Linear data structure that stores values in nodes. The list maintains a reference to the first node, also called head. Each node points to the next node in the list
    Attributes:
        head: The head node of the list
    """
    def __init__(self):
        self.head = None
        # Maintaining a count attribute allows for len() to be implemented in
        # constant time
        self.__count = 0
    def is_empty(self):
        """
        Determines if the linked list is empty
        Takes O(1) time
        """
        return self.head is None
    def __len__(self):
        """
        Returns the length of the linked list
        Takesn O(1) time
        """
        return self.__count
    def add(self, data):
        """
        Adds new Node containing data to head of the list
        Also called prepend
        Takes O(1) time
        """
        new_head = Node(data, next_node=self.head)
        self.head = new_head
        self.__count += 1
    def search(self, key):
        """
        Search for the first node containing data that matches the key
        Returns the node or `None` if not found
        Takes O(n) time
        """
        current = self.head
        while current:
            if current.data == key:
                return current
            else:
                current = current.next_node
        return None
    def insert(self, data, index):
        """
        Inserts a new Node containing data at index position
        Insertion takes O(1) time but finding node at insertion point takes
        O(n) time.
        Takes overall O(n) time.
        """
        if index >= self.__count:
            raise IndexError('index out of range')
        if index == 0:
            self.add(data)
            return
        if index > 0:
            new = Node(data)
            position = index
            current = self.head
            while position > 1:
                current = current.next_node
                position -= 1
            prev_node = current
            next_node = current.next_node
            prev_node.next_node = new
            new.next_node = next_node
        self.__count += 1
    def node_at_index(self, index):
        """
        Returns the Node at specified index
        Takes O(n) time
        """
        if index >= self.__count:
            raise IndexError('index out of range')
        if index == 0:
            return self.head
        current = self.head
        position = 0
        while position < index:
            current = current.next_node
            position += 1
        return current
    def remove(self, key):
        """
        Removes Node containing data that matches the key
        Returns the node or `None` if key doesn't exist
        Takes O(n) time
        """
        current = self.head
        previous = None
        found = False
        while current and not found:
            if current.data == key and current is self.head:
                found = True
                self.head = current.next_node
                self.__count -= 1
                return current
            elif current.data == key:
                found = True
                previous.next_node = current.next_node
                self.__count -= 1
                return current
            else:
                previous = current
                current = current.next_node
        return None
    def remove_at_index(self, index):
        """
        Removes Node at specified index
        Takes O(n) time
        """
        if index >= self.__count:
            raise IndexError('index out of range')
        current = self.head
        if index == 0:
            self.head = current.next_node
            self.__count -= 1
            return current
        position = index
        while position > 1:
            current = current.next_node
            position -= 1
        prev_node = current
        current = current.next_node
        next_node = current.next_node
        prev_node.next_node = next_node
        self.__count -= 1
        return current
    def __iter__(self):
        current = self.head
        while current:
            yield current
            current = current.next_node
    def __repr__(self):
        """
        Return a string representation of the list.
        Takes O(n) time.
        """
        nodes = []
        current = self.head
        while current:
            if current is self.head:
                nodes.append("[Head: %s]" % current.data)
            elif current.next is None:
                nodes.append("[Tail: %s]" % current.data)
            else:
                nodes.append("[%s]" % current.data)
            current = current.next_node
        return  '-> '.join(nodes)
Doubly Linked List
class Node:
    def __init__(self, data, prev_node=None, next_node=None):
        self.data = data
        self.prev_node = prev_node
        self.next_node = next_node
    def __repr__(self):
        return "<Node data: %s>" % self.data
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.__count = 0
    def is_empty(self):
        return self.head is None
    def __len__(self):
        return self.__count
    def add(self, data):
        """
        Adds new Node containing data to head of the list
        Also called prepend
        Takes O(1) time
        """
        new_head = Node(data, prev_node=None, next_node=self.head)
        if not self.is_empty():
            self.head.prev_node = new_head
        self.head = new_head
        self.__count += 1
    def search(self, key):
        """
        Search for the first node containing data that matches the key
        Returns the node or `None` if not found
        Takes O(n) time
        """
        current = self.head
        while current:
            if current.data == key:
                return current
            else:
                current = current.next_node
        return None
    def node_at_index(self, index):
        """
        Returns the Node at specified index
        Takes O(n) time
        """
        if index >= self.__count:
            raise IndexError('index out of range')
        if index == 0:
            return self.head
        current = self.head
        position = 0
        while position < index:
            current = current.next_node
            position += 1
        return current
    def insert(self, data, index):
        """
        Inserts a new Node containing data at index position
        Insertion takes O(1) time but finding node at insertion point takes
        O(n) time.
        Takes overall O(n) time.
        """
        if index >= self.__count:
            raise IndexError('index out of range')
        if index == 0:
            self.add(data)
            return
        if index > 0:
            current_node = self.node_at_index(index)
            prev_node = current_node.prev_node
            new_node = Node(data, prev_node=prev_node, next_node=current_node)
            current_node.prev_node = new_node
            prev_node.next_node = new_node
        self.__count += 1
    def remove(self, key):
        """
        Removes Node containing data that matches the key
        Returns the node or `None` if key doesn't exist
        Takes O(n) time
        """
        current = self.head
        found = False
        while current and not found:
            if current.data == key and current is self.head:
                found = True
                self.head = current.next_node
                self.head.prev_node = None
                self.__count -= 1
                return current
            elif current.data == key:
                found = True
                prev_node = current.prev_node
                next_node = current.next_node
                prev_node.next_node = next_node
                next_node.prev_node = prev_node
                self.__count -= 1
                return current
            else:
                current = current.next_node
    def remove_at_index(self, index):
        """
        Removes Node at specified index
        Takes O(n) time
        """
        if index >= self.__count:
            raise IndexError('index out of range')
        current = self.head
        if index == 0:
            self.head = current.next_node
            self.head.prev_node = None
            self.__count -= 1
            return current
        current = self.node_at_index(index)
        prev_node = current.prev_node
        next_node = current.next_node
        prev_node.next_node = next_node
        next_node.prev_node = prev_node
        self.__count -= 1
        return current
    def __iter__(self):
        current = self.head
        while current:
            yield current
            current = current.next_node
    def __repr__(self):
        """
        Return a string representation of the list.
        Takes O(n) time.
        """
        nodes = []
        current = self.head
        while current:
            if current is self.head:
                nodes.append("[Head: %s]" % current.data)
            elif current.next_node is None:
                nodes.append("[Tail: %s]" % current.data)
            else:
                nodes.append("[%s]" % current.data)
            current = current.next_node
        return  '-> '.join(nodes)