# //almost identical to doubly linked list but # //every node has another pointer to previous node # //Advantages: able to access list at end instead of going from start # //Disadvantages: takes up more memory class Node: def __init__(self, value, next=None, previous=None): self.value = value self.next = next self.previous = previous class DoublyLinkedList: def __init__(self, head=None, tail=None, length=0): self.head = head self.tail = tail self.length = length #add to end of list def append(self, value): new_node = Node(value) #if there is no head (list is empty), set head and tail to be new_node if self.head == None: self.head = new_node self.tail = new_node #otheriwse, set next property on tail to be new node and set tail to be newly created node else: self.tail.next = new_node new_node.previous = self.tail self.tail = new_node #increment length and return self.length += 1 return self #removes last element of list def pop(self): if self.head == None: return None #current will eventually be the last elemeent and will be removed current = self.head #variable right before end new_tail = current #while loop to traverse to end while current.next: new_tail = current current = current.next #sets new tail self.tail = new_tail #cuts off old tail and current previous property self.tail.next = None current.previous = None #decrement list self.length -= 1 #to account when list will be destroyed if self.length == 0: self.head = None self.tail = None return current #removes elememnt at head. Note in python, shift doesn't exist, it would be .pop(0) or you can use remove which is defined later def shift(self): if self.head == None: return None #current_head will be removed and returned current_head = self.head self.head = current_head.next #severs new self.head previous property self.head.previous = None self.length -= 1 #to account when list will be destroyed if self.length == 0: self.tail = None #severs current_head. Note previous is already set to None current_head.next = None return current_head #adds to start of list and replaces head. I included shift/unshift because this is what makes linked list special in terms of reducing big O def unshift(self, value): new_node = Node(value) #edge case to account if list is originally empty if self.head == None: self.head = new_node self.tail = self.head else: temp = self.head self.head = new_node self.head.next = temp temp.previous = self.head self.length += 1 #travels to node at index and returns node def traverse(self, index): if index < 0 or index >= self.length: raise IndexError('index out of range') counter = 0 current = self.head #since this is doubly linked list, you can also approach from tail and go backwards while counter != index: current = current.next counter += 1 return current #travels to node at index and returns node's value def get(self, index): #to accomodate normal python function, where if you give index = -1 in a get(), it will return last index and so on if index < 0: index = self.length + index node = self.traverse(index) return node.value #replaces value at index def set(self, index, value): found_node = self.traverse(index) if found_node: found_node.value = value return True else: return False #insert value at index and adds 1 to length, returns boolean if successful def insert(self, index, value): if index < 0 or index > self.length: raise IndexError('index out of range') if index == self.length: #not not is similar to !! in javascript and it's so it returns a boolean if successful return not not self.append(value) if index == 0: return not not self.unshift(value) else: new_node = Node(value) previous_node = self.traverse(index - 1) after_node = previous_node.next #creating relations before new_node previous_node.next = new_node new_node.previous = previous_node #creating relations after new_node new_node.next = after_node after_node.previous = new_node #increment length self.length += 1 return self def remove(self, index): if index < 0 or index > self.length: return indexError('index out of range') if index == self.length - 1: return self.pop() if index == 0: return self.shift() else: #need to get previous node and after node to create relationships previous_node = self.traverse(index - 1) #removed_node will be removed and returned removed_node = previous_node.next after_node = removed_node.next #unlink removed_node previous_node.next = removed_node.next after_node.previous = previous_node #sever removed_node next removed_node.next = None removed_node.previous = None self.length -= 1 return removed_node #common interview question def reverse(self): #switching head and tail current = self.head self.head = self.tail self.tail = current next, previous = None, None #to show for loop is possible in LL. Could use while loop as well for i in range(0, self.length): #think of this as creating the block next = current.next current.next = previous #initially None current.previous = next #think of this as connecting head/previous to the block previous = current current = next return self # # // [100. 201, 250, 350, 999] # # // first part # # // NODE NEXT # # // 100 -> null # # // second part (for loop and beyond) # # // PREV NODE NEXT # # // line 154( prev = current; ) specifically: # # // 201 -> 100 -> null # # // line 155 (current = next;): # # // PREV NODE NEXT # # // 250 -> 201 -> 100 #useful to visualize reverse() or any other function works def print_linkedlist_to_list(self): result = [] current = self.head while current: result.append(current.value) current = current.next print(result) # l = DoublyLinkedList() # l.append(1) # l.append(2) # l.pop() # l.shift() # l.unshift(3) # l.append(4) # l.traverse(0) # l.get(-2) # l.set(2, 7) # l.insert(0, 99) # l.remove(2) # l.print_linkedlist_to_list() # l.reverse() # l.print_linkedlist_to_list() # y = l.length # print(y) # // Insertion: # // O(1) # // Removal: recall in SL it depends # // O(1) # // Searching: # // O(N) but optimized bc you can start from head or tail (but more memory) # // Access: # // Same as searching
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter