Linked Lists - Class and Node Operations

Linked Lists - Class and Node Operations

1. Doubly Linked Lists

   • Node Operations
     • __init__
     • __repr__
     • get_data
     • get_previous
     • set_previous
     • get_next
     • set_next
     • set_data
   • Class Operations
     • __init__
     • __repr__
     • is_empty
       • O(1)
     • size
       • O(N)
     • search
       • O(N)
     • add_front
       • Create a temp node
       • set the next pointer of the new node to the the node referred by self.head
       • set the previous pointer of the new node to the self.head only if the linked list is not empty
       • point the self.head to the new node created
       • O(1)
     • remove
       • check if the self.head is pointing to None. If None return a message that the list is empty
       • set the current to self.head and set found to false
       • until found is set to true check the data from the current node with passed value. if found then set the found to true else check the current nodes next node by using the get_next method.
       • if it returns None that means we have reached to the end of the list and we haven't found the value we are looking for to remove else continue to set the current to current nodes next node using the get_next method
       • check if we are removing the first node using the value of current nodes previous value. As first node will have previous set to None. if that's the case then set self.head to the current nodes next_node. In a way the node is not removed from the memory but it's no more accessed and will be eventually taken out using the garbage collector.
       • If the node we are trying to remove is not the first node then set the current nodes previous nodes next pointer to the current nodes next node. that way the node to be removed is no more a part of the linked list but we are not done yet as we need to also set the current nodes next nodes previous pointer to current nodes previous node 
       • O(N)

2. Singly Linked Lists

   • If the linked list is empty i.e. linked list head is pointing to None then provide some helpful message to the user
   • Node Operations
     • When creating a new node, set the next to none
     • get_data
     • set_data
     • get_next
     • set_next
     • __init__
       • Set the Next to None and data to the value passed while initializing the node.
     • __repr__
   • Class Operations
     • __init__
       • Point the head to none
     • __repr__
     • is_empty
       • If head is pointing to None then it should return true
       • O(1)
     • add_front
       • Create a temporary node
       • Set the Next value to the current head value if its the very first node which is getting added to the list it may be None. Don't worry about that.
       • Replace the current head value to new node
       • O(1)
     • size
       • Count all the nodes until the current node is pointing to None
       • Edge Case : Return 0 if the current code is already pointing to None.
       • O(N)
     • search
       • Edge Cases : -- Is self.head is None If yes then return None  or print the message Use the temporary variable to hold the value of the current node
       • While the current is not None if current data matches to the data passed then return true
       • If the current data doesn't match, move to the next node using the get_next method
       • return false by default i
       • O(N)
     • remove
       • Edge Case #1 : If you are trying to remove the node from the empty linked list, return the message to the user
       • Edge Case #2 : Target data not found
       • Edge Case #3 : Head we are removing the first node
       • O(N)