# Singly Linked List Data Structure Initialization and Methods Python

Sun Jul 31 2022 04:32:49 GMT+0000 (UTC)

```class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next

self.tail = tail
self.length = length

def append(self, value):
new_node = Node(value)
#if there is no head (list is empty), set head and tail to be 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
self.tail = self.tail.next
#increment length and return
self.length += 1
return self

#removes last element of list
def pop(self):
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
self.tail.next = 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):
return None
self.length -= 1
#to account when list will be destroyed
if self.length == 0:
self.tail = 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
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
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)
temp = previous_node.next
#set next property of previous node to be new_node
previous_node.next = new_node
#set new_node next to be old next of previous
#you can also write this as previous_node.next.next = temp
new_node.next = temp
self.length += 1
return True

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 to create relationships
previous_node = self.traverse(index - 1)
#removed_node will be removed and returned
removed_node = previous_node.next
previous_node.next = removed_node.next
#sever removed_node next
removed_node.next = None
self.length -= 1
return removed_node

#common interview question
def reverse(self):
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
#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() works
result = []
while current:
result.append(current.value)
current = current.next
print(result)

l.push(1)
l.push(2)
l.pop()
l.shift()
l.unshift(3)
l.push(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)

# //Big O:
# //Insertion: O(1)
# //Removal: depends O(1) if start or O(N) at end
# //Above 2 are main advantages vs. arrays esp at start
# //Searching: O(N)
# //Access: O(N)

# //Recall with array implenetation, insertion and removal is not constant ```
content_copyCOPY

Udemy