# //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
Comments