that saves back half speed
#algos-and-data-structs
fiery cosmos
dapper sapphire
something like merge sort?
fiery cosmos
more simple
dapper sapphire
How we keep on splitting at each half and look at right and left.
dapper sapphire
Oh ok interesting.
fiery cosmos
having a for loop starting at the end of the list and decrementing until it hits the middle of the list
using tail to traverse towards the middle
but im not sure how to implement in python tbh
dapper sapphire
Yup I see exactly what you mean
compare their memory addresses that would be the middle
That was helpful. Appreciate the help you guys!
lean dome
Looks like it's singly linked - so popping tail would still be O(n). Even if you store a tail attribute, you need to find the new tail after popping the old tail - and if the list is singly linked and you can't go backwards, you need to start from the start of the list to find the node before the tail.
if it's doubly linked, you can pop tail in O(n), though - go to the tail, check what its prev is, set self.tail = self.tail.prev, and then set self.tail.next = None
dapper sapphire
Oh actually yeah I would have to create a doubly linked list
I was like wait how do I go back from the tail, because thead node only points to next, there's no previous
errant skiff
Does anyone know of a good data structure course online taught in python?
torn scarab
modest ruin
thanks @torn scarab
queen portal
there is a book called DataStructures and algorithms in Python by Michael T. Goodrich, Roberto Tamasssia and Michael H. Goldwasser
its a very good book, if you decide to learn from written sources
warm solstice
there is a book called DataStructures and algorithms in Python by Michael T. Goo...
Just started it, going 1hr per day, because of school.
I will be doing 1 Question per day, then after exams, I'll do three.
queen portal
yeah collage is limiting most of our free time
fiery cosmos
def insertionSort(listaPar):
for i in range(1, len(listaPar)):
key = listaPar[i]
j = i - 1
while j >= 0 and key < listaPar[j]:
# parcurgem elementele din vectorul "sortat" si punem pe pozitia corespunzatoare
listaPar[j + 1] = listaPar[j]
j -= 1
# daca nu se (mai) intampla ce am zis mai sus, atunci listaPar va fi elementul key
listaPar[j + 1] = key
print(listaPar)
# bucketSort
def bucketSort():
numarGaleti = round(math.sqrt(len(lista)))
valMaxima = max(lista)
vectorGaleti = []
for galeata in range(numarGaleti):
vectorGaleti.append([])
for elem in lista:
indexG = math.ceil(elem*numarGaleti/valMaxima)
vectorGaleti[indexG - 1].append(elem)
for i in range(numarGaleti):
vectorGaleti[i] = insertionSort(vectorGaleti[i])
k = 0
for i in range(numarGaleti):
for j in range(len(vectorGaleti[i])):
lista[k] = vectorGaleti[i][j]
k += 1
return lista
customList = bucketSort()
print(customList)
I tried to do a BucketSort
for j in range(len(vectorGaleti[i])):
TypeError: object of type 'NoneType' has no len()
but i m getting this error and idk why
it looks good to me, and I can t find the issue
oh, i m fuckin dumb
nvm, i was printing instead of returning
drifting trellis
Any idea on how to code recursively insertion sort
I don't find
My main problem is to insert a value in a sublist
oblique panther
@old rover did you finish the three methods?
old rover
def addTofront(self, new_data):
"""Self is the instance the method is acting"""
#this inserts a node at the beginning to become the head
newNode = Node(new_data)
#creates a new Node with data stored in it
newNode.next = self.head
#The second line makes it so that the node after the brand new node is the old first node.
self.head = newNode
#make the new node the head
I have this for prepending
oblique panther
```python
def addTofront(self, new_data):
"""Self is the instance the method...
the doubly linked list that comes with Python collections.deque calls that appendleft, so you should probably call it that, too.
old rover
what's collections.deque?
oblique panther
Also remember to use snake_case and new_node instead of thisKindOfThing
oblique panther
what's collections.deque?
a sequence data structure that comes with Python that has O(1) operations for either end of the sequence.
old rover
you not rocking w camel case?
oblique panther
Did you listen to lemon's music video?
old rover
the first 30 seconds yeah
oblique panther
🎵 Camel case is not for python. Never ever. Never everrrrrrrrrrr. 🎵
oblique panther
!docs collections.deque.appendleft
halcyon plankBOT
oblique panther
they just call it "appendleft" with no underscores or capitalization
there's also pop and popleft
old rover
is that a built in method?
oblique panther
it's a method of collections.deque
old rover
can you use this collections.deque method on a linked list?
like does it require an import statement?
oblique panther
!e
from collections import deque
from string import ascii_lowercase
d = deque(ascii_lowercase)
a = d.popleft() # pops the first letter off, a, and gives it to us
print(a)
z = d.pop() # pops the last letter off and gives it to us
print(z)
print(d)
@oblique panther :white_check_mark: Your eval job has completed with return code 0.
001 | a
002 | z
003 | deque(['b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y'])
if they want you to show how they work, no
but they are basically doubly linked lists
old rover
interesting
did you know
that there's ways you can practice creating linked lists on geeks 4 geeks?
oblique panther
```python
def addTofront(self, new_data):
"""Self is the instance the method...
this looks right to me if the list is singly linked (which is what I think you should aim for for now)
old rover
yep it's singly linked
oblique panther
that there's ways you can practice creating linked lists on geeks 4 geeks?
hopefully the practice isn't as bad as their python code.
old rover
I find it interesting that they gave you class Node but didn't give you class LinkedList
oblique panther
why are those stand-alone functions?
and why are they talking about NULL?
and it's camel cased.
Just close that tab.
old rover
class Node:
"""Node class"""
def __init__(self,data):
self.data = data
self.next = None #there's no next node
#linked list class
class LinkedList:
#function to initalize the linked list object
def __init__(self):
self.head = None
""" This says that there is no head"""
def appendLeft(self, new_data):
"""Self is the instance the method is acting"""
#this inserts a node at the beginning to become the head
new_node = Node(new_data)
#creates a new Node with data stored in it
new_node.next = self.head
#The second line makes it so that the node after the brand new node is the old first node.
self.head = new_node
#make the new node the head
I'm confused
wouldn't you say appendLeft is a stand alone function?
oblique panther
```python
class Node:
"""Node class"""
def __init__(self,data):
self.dat...
remember that the l in left should be lower-case.
appendleft is a method and is not a stand-alone function
old rover
ok
oblique panther
a method is a function that belongs to a class and acts upon a specific instance of that class. (there are also class methods and static methods, but we need not go into those or acknowledge that they exist)
old rover
you have any websites I can practice linked lists with?
other than leetcode
hackerrank?
oblique panther
I'm not sure. But you have appendleft, what about just append?
old rover
like insert it behind any random node?
oblique panther
for insert you have to provide an index where you want it to go, or raise IndexError if you're trying to go over the edge.
old rover
linked lists have indexes???
oblique panther
yes, ordered data structures usually do
do you remember the distinction between an index and an element?
old rover
an index is where an element is found?
oblique panther
yes
nova holly
def singleNumber(nums):
last = None
for num in sorted(nums):
if not last:
last = num
else:
if num == last:
last = None
return last
print(singleNumber([4, 3, 1, 1, 4, 3, 2]))
what si the space complexity of the function ?
is it O(1) or O(n) because of the sorted() ?
onyx root
is it O(1) or O(n) because of the `sorted()` ?
It's O(n): sorted returns a list of the numbers
nova holly
oh ok thx
old rover
I haven't even learned a single sorting algorithm yet
woe is me
once I make it past the hell that is linked list then I'll encounter selection sort
def insert(self, prev_node, new_data):
#check if the last node existed
if prev_node == None:
print("The previous node must be in the linked list")
return
#creates a new Node
new_node = Node(new_data)
#idk dude
new_node.next = prev_node.next
prev_node.next = new_node
what are these last two lines
the last line actually makes sense
but what is that one before it
the next node after the previous node is assigned to the node after the new node?
what does that even mean???
grizzled schooner
think about it. if you're inserting into a linked list like this
1 -> 2 -> 3 -> 4
``` and you want to insert after `2`, you'll want the new node to be in between `2` and `3`. so it'll be
1 -> 2 -> new_node -> 3 -> 4
``` as you can see, the node after the inserted node is 3, which was previously the one which was after the previous node (2)
sorry, I'm kind of bad at explaining things, does that make sense?
old rover
I understand that explanation but I don't understand how they wrote it in code
I get that next line tho
they're trying to insert the node between???
grizzled schooner
yep
in my example, prev_node.next is 3, right? you want to insert the new node before that one, so you set new_node.next equal to it
old rover
CLRS doesn't even have psuedocode to insert a node after a given node
they just assume you can figure it out yourself
so far my understanding of the line is just that it's between the two nodes
# This function is defined in Linked List class
# Appends a new node at the end. This method is
# defined inside LinkedList class shown above */
def append(self, new_data):
# 1. Create a new node
# 2. Put in the data
# 3. Set next as None
new_node = Node(new_data)
# 4. If the Linked List is empty, then make the
# new node as head
if self.head is None:
self.head = new_node
return
# 5. Else traverse till the last node
last = self.head
while (last.next):
last = last.next
# 6. Change the next of last node
last.next = new_node
ok I'm curious
when they if self.head is None
how is that possible? don't linked lists always have a head?
or do they mean that the linked list hasn't been created yet
am confused
agile sundial
if the linked list is empty
old rover
if there is no linked list?
lean dome
The head is the first node in the list. There's no head if the list contains no nodes.
old rover
so it's an empty linked list
lean dome
Right.
old rover
learning linked lists is an adjustment period bc there's no append or prepend built in function
you write them yourself
there is a module for it but they won't let you use it during interviews
lean dome
There's no "built in" function for any data structure until someone writes it.
old rover
why did my CS professor say append is a built in function
bc it is
why don't they just update the language so you have a built in function to append to linked lists
that would be interesting
agile sundial
append is builtin to python's standard lists
old rover
standard lists but not linked lists
agile sundial
yes
old rover
eh it's not too bad
I am starting to get it
it just takes time for me to learn things for the first time
lean dome
I think you're getting things a bit confused. Whoever creates a type also creates functions to manipulate it.
In the case of list, the Python authors created the type, and also created the append method for it.
In the case of a linked list, you're creating the type, and also creating the append method for it.
if you were to create your own dynamic array without using list, you wouldn't be able to reuse list.append - you'd need to build your own append method.
the only thing that's special about list is that it's included in Python, so the language comes with both the data structure and its methods.
old rover
well I've done everything with insertion on a linked list
adding a node behind the head
adding a node after a given node
and adding a node at the end
time to do deletion of nodes
lean dome
have you added a node in front of the head, to make a new first node in the list?
changing b -> c to a -> b -> c, that is
oblique panther
```python
# This function is defined in Linked List class
# Appends a new node ...
did you write this? it looks like code from g4g
old rover
I didn't write it
I tried spending an hour writing it but I got nowhere
and either way I can still apply the stuff I learned in the leetcode questions
I have joined the dark side
oblique panther
Anyway, we can worry about how pythonic the code is later. godlygeek gave you some good feedback.
def append(self, new_data):
new_node = Node(new_data)
if self.head is None:
self.head = new_node
return
last = self.head
while last.next is not None:
last = last.next
last.next = new_node
This is how I would write that
however, what is new_node.next?
old rover
that is what confuses me
it's the node that comes after the new node?
the line that comes after makes sense
lean dome
When you insert a new node at the front of a singly linked list, you set new_node.next = self.head, and then self.head = new_node.
When you insert anywhere else, you set new_node.next = prior_node.next, and then prior_node.next = new_node
When you append a new node to an empty singly linked list, you set new_node.next = None and then self.head = new_node.
When you append a new node to a non-empty list, you set new_node.next = None, then you find the last node and set last.next = new_node.
when you're appending a node, the new node's .next is always going to be None - if you're appending a node, it's becoming the last node in the list, and the last node in the list never has a next thing after it.
old rover
yeah I’m not gonna remember that until I start doing leetcode problems
lean dome
That's all at the conceptual level - you'll have trouble doing the leetcode problems without understanding the concepts.
the next of a node is what comes after it. When you're appending a node, nothing comes after it, so next is None.
old rover
yeah I get that part
new_node.next = self.head
so this line right here is saying self.head becomes None?
self.head = new_node
and that line turns the new node into the head?
new_node.next = prev_node.next
@old rover remember that self.head and the links between nodes are the only way you can find your way around the linked list, so every time you change the list, you need to ask yourself what links need to be updated for the list to continue working.
if self.head is None:
# place A
self.head = new_node
# place B
return
what is this one? the next of the previous node is equal to None?
oblique panther
where does new_node.next = self.head go? place A or B?
old rover
place B
so I need to remember what .prev, .next, and .head are
they're pretty self explanatory
most of the times when you use .head you're referring to self which is the linked list
lean dome
place B
nope. if you put it there, you've made a circle. self.head is new_node, and new_node.next is new_node
old rover
oh
F
so that code says if there's no head
then make the node that comes after the new node the head?
if there's no head there's no linked list
lean dome
there is, it's just empty (no nodes)
old rover
but a head is a node...
lean dome
then make the node that comes after the new node the head?
yeah. You could instead write that as new_node.next = None, in which case the order wouldn't matter - but if you leave it as new_node.next = self.head, then you need to run it before you change self.head to not be None anymore.
old rover
The head is the first node in the list. There's no head if the list contains no ...
I'm referring to this
lean dome
but a head is a node...
right - head is the first node in the chain of linked nodes. When head is None, it means that there are no nodes in the chain of linked nodes - meaning that the list is empty.
old rover
so there is no linked list
lean dome
if there's only one entry in the list, then head points to that entry, and that entry's next is None
lean dome
so there is no linked list
there is a linked list in the sense that there's still an instance of the LinkedList class. There are no instances of the Node class.
old rover
@lean dome what did you use to learn linked lists?
oblique panther
<@451976922361102357> what did you use to learn linked lists?
have you tried a youtube video?
I think it might help you to see an animation of nodes being added or removed.
old rover
@oblique panther yeah I’ve tried a couple
There was this account Neso academy
I’ll check it out later
there’s also this guy named Abdul bari and he does videos on data structures/algos but he doesn’t do singly linked lists
lean dome
<@451976922361102357> what did you use to learn linked lists?
A textbook - I'm not sure which, but it seems like textbooks aren't your preference.
spring jasper
Wiki is pretty good too
austere sparrow
What's the advantage of a multidict over just a dict of lists?
dapper sapphire
by multi-dict, do you mean nested-dict?
austere sparrow
No, I mean multidict
Both aiohttp and starlette use it for headers and query parameters
Is it faster because it only allows strings as keys?
dapper sapphire
Ok just reading about it briefly, it seems that you can map one key to multiple values.
austere sparrow
Right, like with a dict of lists
dapper sapphire
which we could still achieve with dicts of list, but the same key would be in different indexes of the list that contain multiple values.
austere sparrow
Not sure what you mean.
Ah, I see
because a multidict has to preserve order, I can't just have a dict of lists.
Gotcha, thanks
spring jasper
Why does order matter for multidicts
Does order matter for headers or query params? I wouldnt think so
dapper sapphire
because the value that's mapped at the first key gets returned, so when you do
d = multidict.MultiDict([('a', 1), ('b', 2), ('a', 3)])
print(d["a")
it will return 1, but not 3
In terms of advanced concepts, sorting algorithms makes use of the array.
Which advanced concepts make use of the linked lists?
spring jasper
You can sort a more than just arrays
dapper sapphire
Like what?
agile sundial
you can sort a linked list
dapper sapphire
But conventionally when sorting is mentioned, is to sort an array or a linked list?
agile sundial
conventionally, an array, but that's because no one really uses linked lists
old rover
and lists are dynamic arrays in python?
agile sundial
they are
dapper sapphire
Actually convention is not the same thing as coding interviews. So I take back what I said lol. Would coding interviews ask you to sort a linked list?
And would they ask you implement a specific type of sorting algorithm on linked list?
spring jasper
Maybe, sorting algorithms shouldnt care about the type of array or implementation
fiery cosmos
Hi ! I am new and had a question. LeetCode uses class Solution(): . For example I was able to write code to find the lowest common ancestor of a binary tree and pass the test. But I dont know how to pass an actual input to this.
What is this weird class Solution():
agile sundial
Maybe, sorting algorithms shouldnt care about the type of array or implementatio...
yeah, but since linked lists can't have O(1) access, you'll have to tweak the implementation.
fiery cosmos
You dont pass input, they handle it for you
Understood but I wanted to pass my own input in an IDE
spring jasper
yeah, but since linked lists can't have O(1) access, you'll have to tweak the im...
But the concept of a mergesort is the same for arrays, list, linkedlists, etc
honest hill
hey can someon ehelp me make a discord bot? the anguge is python
agile sundial
But the concept of a mergesort is the same for arrays, list, linkedlists, etc
yeah for sure
dapper sapphire
What other advanced concepts rely on linked list? I mean in terms of trees and graphs...
spring jasper
Understood but I wanted to pass my own input in an IDE
I dont think you can and thats why i dont like leetcode
fiery cosmos
I dont think you can and thats why i dont like leetcode
Ahhh ok
spring jasper
Theres not a lot of stuff you can do with lists is there, sorting, reversing, traversing
Reversing a linked list is a classic leetcode question
fiery cosmos
Can I paste a few lines (7-8) of code here to get an opinion?
mighty cedar
having bit issue with traversing in a matrix diagonally from bottom right corner.
#this is initial matrix
m = [[0 , 0, 0], [0, 0, 0], [0, 0, 0], ]
#this is an array.
a=[1,2,3,4,5,6,7,8,9]
I want the output to be
new_m = [ [9 , 8,6], [7, 5, 3], [4, 2, 1] ]
looks like below
9 8 6
7 5 3
4 2 1
dapper sapphire
having bit issue with traversing in a matrix diagonally from bottom right corner...
traverse backwards
you will have to traverse backwards both for x and y.
fiery cosmos
class Solution():
def print_aapl():
print('$aapl')
apple = Solution()
apple.print_aapl()
does this code make sense? I wanted to experiment with a class that has no initializer
mighty cedar
m=0
for x in range(3,-1,-1):
for y in range(3,-1,-1):
a[x][y]=ass_arr[m]
m+=1
this was what i was using
want this
9 8 6
7 5 3
4 2 1
getting this
9 8 7
6 5 4
3 2 1
ik why i am getting this.
just not able to understand how to reach the desired output
dapper sapphire
m=0
for x in range(3,-1,-1):
for y in range(3,-1,-1):
a[x][y]=ass_ar...
This is your input?:
m = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
input is a 1d array m=[1,2,3,4,5,6,7,8,9]
want to make a new 2d array
new_m
9 8 6
7 5 3
4 2 1
spring jasper
Thats C
old rover
oh
I'm just looking at it to see a visual implementation
maybe some animation will help
spring jasper
@mighty cedar do you know how to get the diagonals of a matrix?
mighty cedar
not really, trying to understand it getting bit confused.
spring jasper
Ok the concept is simple but i cant give an implementation right now, im eating
Build this matrix
Then find the anti diagonals, i marked them
You reverse them, eg the middle anti diagonal becomes 3 5 7 instead of 7 5 3
Put them together you get
1 2 4 3 5 7 6 8 9
Reverse this to
9 8 6 7 5 3 4 2 1
And then print as a 3x3 matrix
Aight imma go enjoy my curry
old rover
curry yum
mighty cedar
i am literally lost, can you come on call so I can screenshare as soon as you get free?
the idea i get it, its the implementation thats causing me issue.
old rover
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __repr__(self):
return self.data
class LinkedList:
def __init__(self):
self.head = None
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
the website: https://realpython.com/linked-lists-python/
Do I really need this repr function?
I've never seen anything really like it
onyx root
that's an odd way to do that.
old rover
it looks like that creates a linked list
onyx root
it looks like that creates a linked list
what in that looks like creating a linked list?
old rover
what in that looks like creating a linked list?
the repr function?
onyx root
yes, what in the repr function?
old rover
well it says node is equal to self.head
meaning node becomes the head of the linked list
onyx root
yes, node refers to the head of the list at first.
old rover
they then assign a variable called nodes equal to an empty list
while the node exists
add the data to that empty list
onyx root
yes, but a Python list is not a linked list.
old rover
oh
ok
yeah I was sus bc they were using append
there's no built in method for a linked list to append stuff you have to write it yourself
so then what is the point of the function???
onyx root
do you know what __repr__ is for?
old rover
nope
"helpful representation of the objects"
to visualize it?
visualize the list as if it's a singly linked list?
onyx root
__repr__ has a particular meaning and use in Python.
what are you reading to learn Python?
old rover
I'm right though it's just a printable representation of the object
and to answer your question I read automate the boring stuff
onyx root
i wonder if they cover __repr__ there?
yes, __repr__ produces a printable representation.
old rover
ah ok
so I don't really need it then
I know what a linked list looks like
5---> 6 ----> 3
that is a singly linked list
I don't know how to do a doubly linked list here but there would be an arrow pointing from the 6 back to the 5
old rover
oh yeah
undone mauve
a doubly linked list would be
None <-> 5 <-> 6 <-> 3 <-> None
old rover
got it
onyx root
you could decide on any representation you wanted. I would use <LinkedList [1, 2, 3, 4]> and skip the fancy punctuation.
undone mauve
??
the point of the representation is to model how it is structured, particularly for purposes of education or demonstration
which, i would argue your representation does not do
anywho
onyx root
the point of the representation is to model how it is structured, particularly f...
well, the point is to let developers know what is in the object. "LinkedList" says what it is.
undone mauve
not in this context
because in this context
it is someone learning how linked lists work
🙃
agile sundial
well, in the context of this context, it's someone learning what repr does
onyx root
it is someone learning how linked lists work
as I said, you can choose. there's not one "right way".
old rover
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
could you also write while node != None?
what is yield???
dapper sapphire
That repr thing is almost pretty good.
old rover
almost?
dapper sapphire
Yeah,
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
This wont work if you have anything other than a string
So if you append a number it wont work.
deft garden
Could someone help me reviewing a short code in Python?
dapper sapphire
But still pretty good.
deft garden
Could someone help me reviewing a short code in Python?
Please?
Via PM
Won't take more than 10 min
onyx root
@deft garden why not ask here?
deft garden
I didn't want to clutter the chat
But I can paste it
def secondlargest(array):
def split(array, keep_comparisons=True):
if len(array)!=1:
#Split the array in 2 halves, if its size is greater than 1
half= len(array)//2
#Try to split both halves further, applying recursion
L,R= split(array[:half], keep_comparisons), split(array[half:], keep_comparisons)
return compare(L, R, keep_comparisons) #Compare the halves
else:
#If the array cannot be halved further, go back. !!!!
return (array[0], []) if keep_comparisons==True else array
def compare(array1, array2, keep_comparisons):
if array1[0] >= array2[0]:
if keep_comparisons==True:
array1[1].append(array2[0])
return array1
else:
if keep_comparisons==True:
array2[1].append(array1[0])
return array2
losers_vectors= split(array)[1]
return split(losers_vectors, keep_comparisons=False)[0]
import numpy as np
a= np.random.random((200,))
print(secondlargest(a))
It finds the second largest number in an array
deft garden
Not about understanding, but gathering suggestions for improvement
old rover
I am confusion
class Node:
"""Node class"""
def __init__(self,data):
self.data = data
self.next = None #there's no next node
#linked list class
class LinkedList:
#function to initalize the linked list object
def __init__(self):
self.head = None
""" This says that there is no head"""
def ___iter__(self):
node = self.head
while node is not None:
yield node
node= node.next
llist = LinkedList(["a", "b", "c","d","e"])
llist
Traceback (most recent call last):
File "main.py", line 20, in <module>
llist = LinkedList(["a", "b", "c","d","e"])
TypeError: init() takes 1 positional argument but 2 were given
where does it see 2 arguments?
it's just a list
class Node:
"""Node class"""
def __init__(self,data):
self.data = data
self.next = None #there's no next node
def __repr__(self):
return self.data
#linked list class
class LinkedList:
#function to initalize the linked list object
def __init__(self):
self.head = None
""" This says that there is no head"""
def ___iter__(self):
node = self.head
while node is not None:
yield node
node= node.next
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
llist = LinkedList(["a", "b", "c", "d", "e"])
llist
here's the code w the repr functions added in
oh I didn't know you had to change the init function to match what they said
class Node:
"""Node class"""
def __init__(self,data):
self.data = data
self.next = None #there's no next node
def __repr__(self):
return self.data
#linked list class
class LinkedList:
#function to initalize the linked list object
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for elem in nodes:
node.next = Node(data=elem)
node = node.next
""" This says that there is no head"""
def ___iter__(self):
node = self.head
while node is not None:
yield node
node= node.next
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
llist = LinkedList(["a", "b", "c", "d", "e"])
llist
well now it's just blank
I tried print(lllist) but it just shows an address in memory
deft garden
```py
def secondlargest(array):
def split(array, keep_comparisons=True):
...
Hello?
austere sparrow
If you don't learn how to trash other people's code, you will not learn how to trash your own 🙂
which is very important
old rover
If you don't learn how to trash other people's code, you will not learn how to t...
but I have a mortal enemy to duel with to the death: linked lists
spring jasper
Traceback (most recent call last):
File "main.py", line 20, in <module>
ll...
self here is an argument
Your llist __init__ takes self only but you pass it self and the list
Thats why you get the error
Also yield turns a function into generator
You'd have to read up on generators to fully understand it
spring jasper
Realpython has a nice article on generators
old rover
def __init__(self, nodes=None):
self.head = None
#no head on the linked list
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for elem in nodes:
node.next = Node(data=elem)
node = node.next
what do they mean by if node is not None?
spring jasper
Thats checking if the node exists
When you check for None its better to do is None or is not None
Instead of != None
spring jasper
node = Node(...) judt creates a node by popping one from the nodes list
It doesnt add it anywhere yet
That happens in the next line
old rover
where it makes the node the head
old rover
I don't know tbh it seems like realpython and G4G have weird code
old rover
mutation means changing data structures? right?
inmutable means you can't change it? like frozen sets?
spring jasper
Yep
Here the nodes list is mutated with the pop method
It looks weird and is error prone so dont do that in the future, just create new objects
I think our very own nedbat has a lecture on it
spring jasper
No, about names in python
Yea anyway, getting off track
Did you fix the init error?
old rover
for elem in nodes:
node.next = Node(data=elem)
node = node.next
what does that segment of code even do?
how do you iterate through something that is none?
old rover
all it says in real python is that function creates linked lists w some data
spring jasper
all it says in real python is that function creates linked lists w some data
It does that
Your None check is in the if 2 lines up
old rover
I don't know how to fix the init___ problem
spring jasper
Add a parameter to the function
old rover
ok I added aList
but it says non-default argument follows default argument
does that mean it's an unused parameter?
spring jasper
Show us
old rover
spring jasper
Keyword args always come after positional args
old rover
I fixed it
it still prints the memory address
<main.LinkedList object at 0x7fdc4fa27a90>
spring jasper
Also, if you added the nodes param you dont need aList
Thats because you dont have a repr dunder
Like you do in Node
old rover
class LinkedList:
#function to initalize the linked list object
def __init__(self, aList, nodes=None):
self.head = None
#no head on the linked list
if nodes is not None:
#checking if the node exists
node = Node(data=nodes.pop(0))
#creates a node
self.head = node
#node becomes head
for elem in nodes:
node.next = Node(data=elem)
node = node.next
def ___iter__(self):
node = self.head
while node is not None:
yield node
node= node.next
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
but I do it's right there
spring jasper
Watch your indentation
old rover
class Node:
"""Node class"""
def __init__(self,data):
self.data = data
self.next = None #there's no next node
def __repr__(self):
return self.data
#linked list class
class LinkedList:
#function to initalize the linked list object
def __init__(self, aList, nodes=None):
self.head = None
#no head on the linked list
if nodes is not None:
#checking if the node exists
node = Node(data=nodes.pop(0))
#creates a node
self.head = node
#node becomes head
for elem in nodes:
node.next = Node(data=elem)
node = node.next
def ___iter__(self):
node = self.head
while node is not None:
yield node
node= node.next
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
llist = LinkedList(["a", "b", "c", "d", "e"])
print(llist)
fixed the indentation but still prints nothing
old rover
a -> None -> b -> None -> c -> None -> d -> None -> e -> None
that is interesting
>>> llist = LinkedList(["a", "b", "c", "d", "e"])
>>> llist
a -> b -> c -> d -> e -> None
you've got an extra _ in your iter
spring jasper
Congrats you made a linked list
agile sundial
🎉
spring jasper
Also nodes.append("None")
Idk why thats there
In the loop i mean
Should be outside
old rover
now it works
old rover
ok
scarlet maple
old rover
def add_first(self, node):
node.next = self.head
self.head = node
inserting at the front of a linked list on the real python website
def push(self, new_data):
# 1 & 2: Allocate the Node &
# Put in the data
new_node = Node(new_data)
# 3. Make next of new Node as head
new_node.next = self.head
# 4. Move the head to point to new Node
self.head = new_node
inserting in front of a linked list on G4G
which one is better? I think it's the first one
agile sundial
i mean
they do exactly the same thing
*with the exception that the bottom expects a value, and the top expects a nnode
old rover
so you don't need that Node(new_data) line?
agile sundial
the top function expects the user to pass it a Node
old rover
oh I see
agile sundial
the bottom function expects just a value, and so it has to create a Node before using it
old rover
ok
agile sundial
apart from different names, they do pretty much the exact same thing
old rover
nice
elfin sundial
hey guys, would hexadecimal be easier for a application? say if you are working with map based data such as lattitude and longitude, do you reckon that if i convert that integer into a hex, would that be better or would that just be a personal development thing
stuck forum
hey guys, would hexadecimal be easier for a application? say if you are working ...
Personal thing. They would be no different in terms of binary.
onyx root
hey guys, would hexadecimal be easier for a application? say if you are working ...
what seems easier about hex to you?
elfin sundial
hex is more compact than standard float but since the float is like 8 digits from the decimal point. it seems more logical to present those numbers in hex
but im not sure because hex seems more of a hassle to unwrap
onyx root
but im not sure because hex seems more of a hassle to unwrap
i would find it hard to debug if lat and long were in hex. And they aren't that much more compact.
elfin sundial
yeah im starting to realise it, and since its not a true repersentation of the data, it can undo waht im trying to achive anyway.
thanks for the reply anyway mate, good input.
queen ruin
hello, is there a way to get the inner function without putting the args in the outer function? like
def outer(c,d,e):
def inner(a,b,c):
print(func(a,b,c))
return inner
i wanna get the inner function, without passing the c,d,e to the outer
onyx root
hello, is there a way to get the inner function without putting the args in the ...
you can't call outer without passing three arguments. Can you show the real code?
queen ruin
umm, a lil too big >.< , is there something to get it with the byte code or smth, i swear this is not an x,y problem
onyx root
@queen ruin can you change outer and inner? Sounds like this shouldn't have been an inner function to begin with.
@queen ruin there's almost always a way with Python, but in this case, that way is going to be a few miles down a very bumpy road.
queen ruin
🤔 .. its fine, guide me lol, been searching it everywhere
onyx root
i don't know it off the top of my head, and I think it would be very difficult. why can't you change it to not be an inner function?
queen ruin
alr, so the thing goes like
@compiler.compile(embed=True)
async def format_bot_help(...):
def callback(...)
return callback
now the compiler decorator goes something like
@classmethod
def compile(cls, **kwargs):
def actual_decorator(func):
return cls.bot_help(func)
return actual_decorator
and cls.inner
@staticmethod
def bot_help(func):
async def inner(self, ctx, help_settings=None, get_pages=None):
...
# i need to get the callback() function from format_bot_help
return inner
soo, if any of that makes sense, i want to acces the callback() outside the format_bot_help
and i can't change anything, cause well, that's just how i made it kek
onyx root
wait, you wrote all this, and you can't change it?
@queen ruin you should un-inner that callback
marsh nexus
Hello, can someone give me an explanation of how str[::-1] reverses a string?
Doesn't [:] means from the start to the end, so how does [::-1] means start from the end and go backwards by 1 step?
spring jasper
The syntax is [start:stop:step] if you dont specify start and stop it means the whole array
A step of -1 means go backwards by one
If you start at the beginning of the array at index 0 and step -1 you get index = -1, the last item
If you keep stepping -1 you get index=-2 which is the second to last element and so on
brave oak
The syntax is `[start:stop:step]` if you dont specify start and stop it means th...
if step is negative, start and stop implicitly change
old rover
self.head = None
the guy in the video says that it's O(n) complexity
how do you know?
someone commented below and said it's O(1) complexity
uh
compact bloom
@old rover have you studied O notation and time complexity yet?
old rover
<@567030124306759710> have you studied O notation and time complexity yet?
yeah but I've never done it with just one single line
I think it should be O(1)
onyx root
@old rover you think what should be O(1)?
old rover
self.head = None
onyx root
that is O(1)
old rover
well then
I found another book
and it actually shows the implementation of a linked list in Python
onyx root
he's saying O(1), while the video annotates the line with O(n). confusing.
old rover
he's saying O(1), while the video annotates the line with O(n). confusing.
I thought a type declaration was just declaring the type
does he mean he's creating a linked list?
onyx root
you need to help us understand what you are referring to
old rover
where it says Following is a type declaration for a linked list of integers
onyx root
he means, "here is the definition of a class"
onyx root
this book is written like it's a Java book transliterated into Python
onyx root
it's a fancy way of saying, "translate each word independently so that you end up with a weird sentence rather than resaying what you mean in a different language"
onyx root
Python shouldn't have setData, getData, setNext, getNext.
old rover
this is what I was looking at before
would you say that the realpython implementation is better?
onyx root
yes
old rover
also why is that book's code so damn long
onyx root
though we've talked about the __repr__ there before.
old rover
onyx root
the book's code is long because they added a bunch of useless getters and setters
old rover
yeah I think real python is the better resource
I'll stick w that
false alarm this book is not my savior(joke)
I really wish I could just understand CLRS by reading it but that doesn't seem like an option
I probably should not be resource hopping
onyx root
@old rover i hope this doesn't seem harsh, but you've been at this a while. Maybe you need a different approach?
old rover
<@!567030124306759710> i hope this doesn't seem harsh, but you've been at this a...
what would you suggest?
onyx root
idk, i don't know you, what resources you have, or how you like to learn.
old rover
I like videos
with the code in Python
that's why I tried that video stuff bc I thought it would be a good option
onyx root
can i ask why you are working on linked lists?
old rover
bc I want to learn algos/DS
onyx root
why is that?
old rover
bc it'll make me learn better and I'll be able to understand the algorithms they use with sklearn better bc I'd have already seen multiple algorithms
it's not bc I want the fancy SWE job at FAANG
onyx root
sounds like your goal is to use sklearn?
onyx root
i think you should reflect on what has gone well, and what has not gone well, in your study of linked lists
you said, "I probably should not be resource hopping." That's a good insight.
old rover
hm
well I'll tell you what has not gone well
spending days trying to understand the psuedocode in CLRS has not gone well
onyx root
is that the book you pasted above?
old rover
no
onyx root
what has made it hard to understand clrs?
old rover
onyx root
this is a very mathematical approach
old rover
very scholarly and academically rigorous
onyx root
yes. Not many people need that.
old rover
I don't do well with those type of books
onyx root
get rid of that book
old rover
yeah I just pulled it up to show you it
even the explanation is interesting
textbooks don't seem to do ELI5
I just don't like how some of these books do linked lists
this whole problem originated with the fact that Grokking didn't even show an implementation of linked lists anywhere in the book
onyx root
what is Grokking?
old rover
Grokking is another book
for DS/algos
it's like 200 pages compared to CLRS's 1k pages
what's funny is that they show code for binary search but they refuse to show code for linked lists
if they had just explained linked lists with the way they explained binary search we wouldn't be having this conversation most likely
unfortunately these people aren't my friends that I'm gonna bang on their door and they're gonna show me an implementation of linked lists perfectly explained with clear and concise code
Cracking the Coding Interview just glances over the code because it's more problem oriented
onyx root
perhaps grokking doesn't cover linked lists because they aren't that important in Python?
old rover
hmmmm perhaps
onyx root
though wait: they are in that book, page 25
old rover
I'm saying he covers them
but he doesn't show code for them
the code is written in Python 2.7
but that's like no big deal
onyx root
the first thing you need to do is learn that it's ok to ignore a resource you don't like
onyx root
good. also get rid of that java-style book.
old rover
yep
onyx root
do you have a resource that you do like?
old rover
I am trying to get myself to like real python
onyx root
what's the problem?
old rover
no problem so far I just thought that videos were more my style
maybe not those kinds of videos like that sloppily edited one
onyx root
ok, but you've been referencing realpython for a while too. either it clicked or it didn't
old rover
I started it yesterday
didn't get through all the code on the website bc I had some other college stuff to do
onyx root
ok, stick with it
old rover
ok, stick with it
so what do you think of Grokking? do you prefer CLRS more?
I'm just curious
onyx root
this is a serious question: what does it matter what I prefer?
old rover
just a question
agile sundial
that answer is obvious, it must be mint chocolate chip
onyx root
@old rover my point is that it's very easy for new learners to fall into the trap of comparing themselves to others.
"how long did it take you to learn python?", etc. It's pointless
old rover
ok
grizzled schooner
that answer is obvious, it must be mint chocolate chip
nah coffee ;)
lean dome
<@&267629731250176001> ^
mint jewel
!tempban @restive crater 1m please do not post random gifs into the server
halcyon plankBOT
:incoming_envelope: :ok_hand: applied ban to @restive crater until 2021-04-07 18:28 (30 days and 23 hours).
spring jasper
if step is negative, start and stop implicitly change
Huh, so they do, but why? I would expect "hello world"[2::-1] to be "dlrow ol"
!e
print("hello world"[2::-1])
You are not allowed to use that command here. Please use the #bot-commands channel instead.
mint jewel
2 means you are starting from the the third element, and going by -1 gives you the result
the defaults are flipped since it is more useful that way
spring jasper
Starting from 2 to the end, but backwards is what i was expecting
mint jewel
well, the indicies are 2 1 0
just like range(2, -1, -1)
if you want to start the range at the end, you have to start at -1
start and stop don't switch places when a negative step is passed
compact bloom
@spring jasper you have to define where you want to start, then finish, then in what order you want it to be displayed. Like shown above
so from the 3rd index to the last index, then -1 meaning it will present it backwards each element
white marsh
hey everyone, I want to build an algo trading bot. does anyone know something about that?
white marsh
https://towardsdatascience.com/algorithmic-trading-bot-python-ab8f42c37145
Thank you so much dude!!
I just looked through that website and wow... you don't know how much you're bringing me further
old rover
yeah no problem
dapper sapphire
If we wanted to remove a node from the list, do we have to do the following:
del current.data
Is the following not good enough. Or is something lack in this?:
previous.next = current.next
My understanding is that when we point previous.next to current.next. Then we are not keeping track of current node anymore.
Since python has garbage collection
onyx root
you don't need del current.data
old rover
is there a .last attribute for linked lists in Python?
nah I don't think so
there's a .next, .prev, and .head
keen hearth
hey everyone, I want to build an algo trading bot. does anyone know something ab...
Tbh, that's a different sort of "algorithm" to the topic of this channel.
You might have more luck in #data-science-and-ml
grizzled schooner
is there a .last attribute for linked lists in Python?
there is if you make one.
that would be .tail i think
lean dome
nah I don't think so
If you have a linked list class and a node class, it's common to have a .tail in addition to .head on the linked list, for efficient appends at the end of the list
old rover
def add_last(self, node):
if self.head is None:
self.head = node
return
for current_node in self:
pass
current_node.next = node
so could you write this code shorter with the .tail?
keen hearth
My understanding is that when we point previous.next to current.next. Then we ar...
Yeah, that's correct. In fact del just deletes the variable, not the object. Objects are garbage collected when there are no references to them, or if they are otherwise unreachable.
lean dome
```python
def add_last(self, node):
if self.head is None:
self.head ...
Both shorter and more efficient, yes.
old rover
interesting
grizzled schooner
```python
def add_last(self, node):
if self.head is None:
self.head ...
yep. although i'm not sure that code works anyways?
old rover
"First, you want to traverse the whole list until you reach the end (that is, until the for loop raises a StopIteration exception). Next, you want to set the current_node as the last node on the list. Finally, you want to add the new node as the next value of that current_node."
here's their explanation
keen hearth
yep. although i'm not sure that code works anyways?
I guess they have an __iter__ method.
lean dome
def add_last(self, node):
node.next = None
if self.head is None:
self.head = node
self.tail = node
return
self.tail.next = node
self.tail = node
That's the efficient way to do it if you have tail
old rover
I guess they have an `__iter__` method.
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
the iter method
old rover
```py
def add_last(self, node):
node.next = None
if self.head is None:
...
why are we making both the head and the tail the same node?
lean dome
Because if there's only one node in the list, it's both the first and last node in the list.
keen hearth
```py
def add_last(self, node):
node.next = None
if self.head is None:
...
...
self.tail = node
head always refers to the first node in the list, and tail always refers to the last
dapper sapphire
Yeah, that's correct. In fact `del` just deletes the variable, not the object. O...
Got it thanks!!
old rover
`head` always refers to the first node in the list, and `tail` always refers to ...
why do you need that last line?
lean dome
To keep tail up to date
old rover
that line before says what comes after the tail is the node
but then that last line says that what is the tail is also the node
lean dome
Wherever a new node is added at the front, you need to update head to refer to it. Whenever a new node is added at the end, you need to update tail to refer to it
lean dome
but then that last line says that what is the tail is also the node
Right. The thing that comes after the old tail is the new node we're adding. The new tail is the new node we're adding.
old rover
interesting
lean dome
If we only had the first line, the new node would be reachable at part of the list, but the list wouldn't know it had a new last node. If we only had the second, the list would know it has a new last node, but it wouldn't be reachable by walking through the list starting at the first node.
old rover
let me see what happens when I try calling it
they gave me repr functions so I can see it visually
brave oak
Huh, so they do, but why? I would expect `"hello world"[2::-1]` to be "dlrow ol"
just to make everything line up
if it didn’t
string[::-1]’s first character would be s
and then g
old rover
interesting
it has an attribute for head but no tail?
hey guys
no one told me this existed???
this could be really helpful
interesting
interesting
mental zephyr
sup fam
old rover
new strategy
create a linked list and then write the functions based of the psuedocode visualalgo gives you
white marsh
Tbh, that's a different sort of "algorithm" to the topic of this channel.
alright I'll do that. thanks for clarifying
lean dome
Traceback (most recent call last):
File "main.py", line 63, in <module>
ll...
It has whatever attributes you create in __init__
You can make a linked list that stores a reference to the last node as tail, or you can make one that doesn't. It's up to you; there's advantages either way.
lean dome
Adding a new node at the end is much faster if you have tail, but keeping track of what the tail node is is extra work, so if you don't need to access the last node in the list, the extra work wouldn't have any benefits
old rover
if you wanted to do that?
class Node:
"""Node class"""
def __init__(self,data):
self.data = data
self.next = None #there's no next node
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
like that?
lean dome
yep.
old rover
good shit
maybe I am slowly learning OOP then
wait... it's all objects?
certain implementations will use tail others don't
lean dome
you might want to take a pause and learn the basics of OOP before circling back to data structures and algorithms. I bet a lot of things would make more sense if you had a better understanding of classes and objects.
old rover
I know the basics of OOP
lean dome
ok. "slowly learning" made it sound like you don't
old rover
I learnt it in college before
lean dome
but if you understand the basics of methods and what __init__ is for, you're probably fine.
old rover
methods are just functions in classes
everything I'm writing now is a method
bc it's in the class LinkedList
lean dome
yep, but the important thing about them, that makes them different from other functions, is that they get a reference to the object instance that they're called on, and they can access that instance's data
old rover
llist.add_first(Node("b"))
like over here where they use the dot notation to refer to the method that adds a node in front of the head
lean dome
right. That calls LinkedList.add_first(llist, Node("b"))
old rover
yep
dapper sapphire
So when have the following:
node.data = node.next.data
node.next = node.next.next
What we are doing is overwriting the value of the current node, and then point it's next to two nexts?
So if we have 1 -> 2 -> 3 -> None and we wanted to remove the node with value 1 and that's the node that we are currently at,
then with node.data = node.next.data -> 1 would become 2
with node.next = node.next.next current_node which now has the value of 2(previously 1), now points to 3?
So then we in a way delete the node that has the value of 2, but before we do that, we replace current node's value of 1 with it?
old rover
So when have the following:
```python
node.data = node.next.data
node.next = nod...
I actually like visualgo for this
bc it shows you it visually
Vertex vtx = new Vertex(v)
tail.next = vtx
tail = vtx
I'm confused on how to turn these 3 lines of psuedocode into python
oh that's easy actually
tail = self.tail
vtx = Vertex(v)
self.tail.next = vtx
self.tail = vtx
ok good
old rover
```py
vtx = Vertex(v)
self.tail.next = vtx
self.tail = vtx
```
is what I wrote valid too?
I did that to shorten it
lean dome
So then we in a way delete the node that has the `value of 2`, but before we do ...
Yep, that's exactly what's happening there.
lean dome
is what I wrote valid too?
You mean tail = self.tail? I'm not sure how that's useful. It's syntactically valid, but it doesn't update any instance attributes
old rover
hm
lean dome
You could do ```py
tail = self.tail
tail.next = Vertex(v)
self.tail = tail.next
I guess - but that's not really a clearer way to write it.maybe if you called it old_tail it would be clearer: ```py
old_tail = self.tail
self.tail = Vertex(v)
old_tail.next = self.tail
so here's a linked list with nodes 1,2,3
I inserted a node
I guess I'm confused about that second line
bc just doing tail.next = vtx
doesn't actually set vtx as the tail?
it just sets a reference to vtx?
is that a good way of explaining it?
you need to create the reference using the attribute before you assign things as head or tail
lean dome
doesn't actually set vtx as the tail?
it adds a link from the vertex that was previously the tail to the new vertex.
old rover
so I'm right
lean dome
Then the 3rd line sets the new vertex as the new tail.
old rover
kinda right
lean dome
So after the 2nd line, you have: 1 -> 2 -> 3 -> 21 head tail vtx and after the 3rd line, you have: ```
1 -> 2 -> 3 -> 21
head tail
vtx
Yeah. After the 2nd line, a new node has been added to the chain, but tail hasn't yet been updated. The 3rd line updates tail to refer to the new node.
old rover
yay
you have no idea how good that feels
it's taken some time to understand this stuff
compact bloom
ngl after learning data structures, half of them arent even necessary to actually learn to implement as there is usually pre defined functions for all of them
like partition() or hash()
lean dome
mature standard libraries have many of these data structures built in, so that you don't need to implement them yourself, yes. But it's still important to know how they work, so you can make the right choices about which data structure to use for what problem.
compact bloom
hashing is by far the coolest data structure, when implementing can you use different modules or frameworks for different hashing algos
if that makes sense
lean dome
hashing isn't a data structure at all - it's an algorithm used in the implementation of many different data structures, like hash tables, hash trees, hash sets, bloom filters, etc
compact bloom
yeah i mean im talking about hash tables
but you can implement different hash functions
lean dome
sure, that's true
the bloom filter data structure requires several distinct hash functions
compact bloom
ngl its so interesting
ive got so many cool project ideas like creating my own crypto currency, creating my own coding language..
i think different sorta projects will get me apprenticeship/ intern
old rover
I'm confused
for the insert option
you can insert stuff before the head and after the tail
but what's going on with that insert between two nodes?
it says specify both i in [1..N-1]
if I want to insert between 1 and 2 what do I have to put?
late wharf
Would it be 2?
old rover
then it says no duplicate vertex allowed
but 1 and 93 works?
idk
the site may be broken
OH
I figured it out
lean dome
I think the v it's asking is the value for the node to hold
old rover
yeah you're right
lean dome
and i is that node's index - if I understand.
old rover
I think it's the node's value
bc I put 1 and 93
it looks like that now
interesting
lol geeks 4 geeks doesn't even have inserting between two nodes
compact bloom
lol thats pretty basic stuff as well
late wharf
Ohh hm
compact bloom
i recommend cs dojo yt vids and brilliant.com
if ur not getting the correct content
thats what ive used
old rover
i recommend cs dojo yt vids and brilliant.com
I'm not sitting through 20 minute videos with a Java implementation of a linked list
what's brilliant.com?
late wharf
its a site that has a lot of content around problem solving
sometimes it has some wikis on algorithms and other cs concepts
onyx root
@old rover what happened to realpython?
spring jasper
Why does the language matter, its the concept that you should be learning
old rover
<@!567030124306759710> what happened to realpython?
that visualgo site was doing stuff shorter so I was interested
old rover
Why does the language matter, its the concept that you should be learning
bc I want it to be in Python?
spring jasper
The way linkedlists are defined arent python specific tho
old rover
I just don't feel like learning a whole new language rn
Vertex pre = head
for (k = 0; k < i-1; k++)
pre = pre.next
Vertex aft = pre.next
Vertex vtx = new Vertex(v)
vtx.next = aft
pre.next = vtx
this is for inserting between two nodes
but like what is that for loop even iterating through
def add_after(self, target_node_data, new_node):
if self.head is None:
raise Exception("List is empty")
for node in self:
if node.data == target_node_data:
new_node.next = node.next
node.next = new_node
return
raise Exception("Node with data '%s' not found" % target_node_data)
this is the code on real python
lean dome
```python
Vertex pre = head
for (k = 0; k < i-1; k++)
pre = pre.next
Vertex...
This pseudocode appears to be Java without semicolons, FWIW.
the book page that you pasted earlier was valid Pascal, I think.
spring jasper
I dont see whats wrong with it tbh, it looks perfectly readable
old rover
the book page that you pasted earlier was valid Pascal, I think.
which book page?
spring jasper
That for loop in the second code block requires a __iter__ function to be implemented
lean dome
this one ^
old rover
this one ^
yeah that's CLRS
so uh I'm still confused
for (k = 0; k < i-1; k++)
what is that for loop iterating through?
lean dome
it executes i-1 times.
onyx root
```python
for (k = 0; k < i-1; k++)
```
that's not python
old rover
that's not python
yeah ik
that looks like java to me
def add_after(self, target_node_data, new_node):
if self.head is None:
raise Exception("List is empty")
interesting
never seen that before
it raises an error and stops the program
so is it a form of error handling?
agile sundial
not really handling since it just ends the program
it's definitely an error though
old rover
oh error handling continues the program?
lean dome
it raises an exception. Something could later catch that exception and handle it
if nothing catches it, then the program ends.
old rover
for node in self:
if node.data == target_node_data:
new_node.next = node.next
node.next = new_node
return
so that for loop goes through every node in the linked list
then it sees if the data matches
that line before the return makes sense
that line creates a reference for the new node to be dropped in
lean dome
that walks through the list until it finds a node with the given data, and when it finds it, it inserts the new node after it.
old rover
so I'm right?
lean dome
yeah, the line before return creates a new reference to new_node in node.next
lean dome
what else would it return?
old rover
self?
lean dome
generally functions either have side effects (like modifying a list) or returns (giving you the value of the Nth node, or something).
usually, functions that have side effects don't return anything.
lean dome
things that modify an object, instead of just computing a new value
a function will typically either modify objects or return values, not both.
old rover
interesting
north zealot
Hello @fringe spear, that looks like an interesting console, but not the right channel for it. Maybe you can post it in #tools-and-devops ?
astral cliff
Hello, i've implemented this binary search tree with letters as the key and integers as values, I would like to ask if this tree is balanced?
Any help is much appreciated
onyx umbra
yes it is balanced since max height difference is 1
worldly pendant
And it's important to note that a binary tree is balanced if each subtree of each node is balanced. So in you're example if you removed Node G your tree would no longer be balanced
astral cliff
And it's important to note that a binary tree is balanced if each subtree of eac...
is it because Node F has the height 2 which is > 1?
astral cliff
yes it is balanced since max height difference is 1
Thanks!
onyx umbra
is it because Node F has the height 2 which is > 1?
yes
because its left node will have height 2 but right 0
worldly pendant
because its left node will have height 2 but right 0
exactly
astral cliff
Hmm, what if H is added to right of G and I is added to right of H?
onyx umbra
then it will become unbalanced at G
astral cliff
then it will become unbalanced at G
Oh right cause now height of G becomes 2
onyx umbra
since left height will be 0 and right 2
worldly pendant
Oh right cause now height of G becomes 2
Yup you need to check at each node
astral cliff
Alright, thank you so much!
worldly pendant
so height of g right is 2 and g left is 0
astral cliff
So as a general rule of thumb, i have to ensure that each node subtree's left and right height only has a max difference of 1?
onyx umbra
np
fringe spear
Hello <@!350072300399230999>, that looks like an interesting console, but not th...
Yeah, sorry!
old rover
def add_after(self, target_node_data, new_node):
if self.head is None:
raise Exception("List is empty")
for node in self:
if node.data == target_node_data:
new_node.next = node.next
node.next = new_node
return
raise Exception("Node with data '%s' not found" % target_node_data)
I'm curious
what's that last raise exception for?
spring jasper
in case there data you want to add after dont exist
spring jasper
its c style string formatting
spring jasper
target_node_data
spring jasper
yes?
fiery cosmos
can someone tell me what's wrong with this code? ```
x = input()
score = ['1', '2', '3']
if x == score:
print('your score = ' + score)
else:
print("there's no new scores")```
yes, I know I'm bad at codding so I'm coming here for help sorry
yes
ok, I'll try that
Ye, that's working thanks!
old rover
def add_after(self, target_node, new_node):
if self.head is None:
raise Exception("List is empty")
#if there is no head on the linked list, it's empty
for node in self:
#iterating through the linked list
if node.data == target_node.data:
#if the data of the node matches the data of the target node
new_node.next = node.next
#create references for the new node
node.next = new_node
#make the new node the last node or tail
return
is there any way I can write this shorter?
grizzled schooner
```python
def add_after(self, target_node, new_node):
if self.head is None:
...
maybe get rid of some of the comments? things like iterating through the linked list are pretty self explanatory.
old rover
maybe get rid of some of the comments? things like `iterating through the linked...
that's just there in case I look back at it months later and forget what that means
but I see your point
I am still confused about new_node.next = node.next
trim fiber
```python
def add_after(self, target_node, new_node):
if self.head is None:
...
Not tested
try:
node = list(filter(lambda node: node.data == target.data, self)).pop()
new_node = node.next
node.next = new_node
except IndexError:
pass
oof idk lambda yet
trim fiber
But I prefer to have for...in than filter solutions
agile sundial
filter doesn't have pop
trim fiber
`filter` doesn't have `pop`
Right... So list(filter(...))
👍
Or [node for node in self if node.data == target.data]
grizzled schooner
I don't think it's necessary for him to shorten his code
old rover
I mean I basically understand what it does
trim fiber
I don't think it's necessary for him to shorten his code
I am not diving into it, I just provide solution - he can compare which solution is better for him
dim sedge
Heya, im currently implementing Battleships, how do i check if a ship fits? I came up with
print("cant fit ship on board!")
else:```
, but im wondering if there are other solutions? i feel liek im missing something... Im currently using a list of lists as a structure for the gameboard.you can use try and except so that you can print "cant fit ship on board!" if you catch any IndexErrors
old rover
def addFirst(self, data):
new_node = Node(data)
new_node.next = self.head
#the one after the new node is the old head
self.head = new_node
#the new node becomes the head
def addLast(self, data):
tail = self.tail
#make the tail the end of the linked list
new_node = Node(data)
#create a new node
tail.next = new_node
#make a reference to the new node
tail = new_node
#make the new node the tail
I'm curious
if they added the whole if self.head is None: raise Exception("List is empty") in the add between two nodes
why not do it here?
agile sundial
because it doesn't need another node
if you have 0 nodes, when you add a node it's the last node
same with the first one
so it has no issues when there are 0 nodes
old rover
but when you add between you need to see if the list is empty
bc otherwise there are no nodes to add in between
grizzled schooner
yep
agile sundial
exactly
old rover
look at me finally understanding this stuff
def removeNode(self, target_node_data):
if self.head is None:
raise Exception("List is empty")
#if the linked list is empty then it stops the program
if self.head.data == target_node_data:
#if the head's data matches the target node's data
self.head = self.head.next
#self.head becomes the new target node???
previous_node = self.head
#what is this line for?
for node in self:
if node.data == target_node_data:
#if the data matches
previous_node.next = node.next
#idk
return
previous_node = node
#idk
am I right about that self.head = self.head.next?
In the above code, you first check that your list is not empty (line 2). If it is, then you raise an exception. After that, you check if the node to be removed is the current head of the list (line 5). If it is, then you want the next node in the list to become the new head.
If none of the above happens, then you start traversing the list looking for the node to be removed (line 10). If you find it, then you need to update its previous node to point to its next node, automatically removing the found node from the list. Finally, if you traverse the whole list without finding the node to be removed (line 16), then you raise an exception.
this is what they said
I got another question
would these above methods also work for doubly linked lists?
spring jasper
if youre iterating over self why are you also checking self.head by itself
agile sundial
because the for loop doesn't change head
old rover
idk dude this isn't my code
old rover
do you mean should or shouldn't
spring jasper
should
if self.head is the target node then that changes self.head but still goes on to run the loop
also comments are traditionally on the same line as the line they describe or above it, not below it
thats confusing
old rover
oh
ok then I'll fix it
self.head = self.head.next
what is the point of this code?
previous_node = self.head
and then this?
the next node is now the self.head
or it's creating a reference to the self. head and then the previous node becomes the self.head
when I see .next and .prev I like to think references
proper zenith
can anyone walk me through proving the correctness and time complexity [O(lg(n))] of this algorithm? would appreciate it a ton
Power(x,n)
if n = 0
return 1
if n mod 2 == 1
y <- Power(x,(n-1)/2)
return x*y*y
else
y <- Power(x,n/2)
return y*y
F in the chat for me ig
lean dome
```python
def add_after(self, target_node, new_node):
if self.head is None:
...
def add_after(self, target_node, new_node):
for node in self:
if node.data == target_node.data:
new_node.next = node.next
node.next = new_node
return
raise Exception("List has no such element")
Hey, have you tried a proof-by-induction for the correctness?
proper zenith
Hey, have you tried a proof-by-induction for the correctness?
i tried, but im pretty sure i got it wrong, im not very good with induction
can you take a look and give me some tips through DMs maybe? my work is pretty rough
keen hearth
Erm, can't help via DMs sorry!
Have you already done some work?
The key is first to prove the base-case n == 0, then show that if you assume that Power(x, n) is correct, then Power(x, 2n+1) and Power(x, 2n) are correct.
old rover
what's proof by induction?
keen hearth
For the first case: x^(2n+1) = x^(2n) * x = (x^n)^2 * x
keen hearth
what's proof by induction?
It's related to recursion. You would use it when you want to prove that something is true for every element in an infinite set.
For example if you wanted to prove something is true for every natural number (0, 1, 2, 3, ...), you prove it true for the the base-case, 0, then you prove that if it is true for k then it's also true for k+1. Then they sort-of fall like dominoes, and it's proven for all natural numbers.
