# Doubly Linked List Data Structure Initialization and Methods Python

Sun Jul 31 2022 18:22:49 GMT+0000 (Coordinated Universal Time)

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

def __init__(self, head=None, tail=None, length=0):
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.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
#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.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
#severs new self.head previous property
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

#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:
else:
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
#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
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
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
result = []
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.reverse()

# 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 ```
content_copyCOPY

Udemy