i've seen problems on leetcode about a binary search tree
#algos-and-data-structs
austere sparrow
Well, a tree is a very fundamental data structure in computing. Not just in computing, but in real life as well.
austere sparrow
uhhh
old rover
I mean you didn't use classes or anything
austere sparrow
no, don't see anything OO here
austere sparrow
It's just:
a) an empty list
b) a pair of: an element and another linked list
spring jasper
You can implement linked lists with classes or tuples or anything you want really
old rover
you can have another linked list in a linked list?
well yeah same way you can have a dictionary in a dictionary
or a list inside of a list
austere sparrow
no, I meant a different thing
old rover
hang on I will re read the Grokking chapter
austere sparrow
None -- empty list
(1, None) -- head of the list is 1, the rest of the list is None
(2, (1, None)) -- head of the list is 2, the rest of the list is (1, None)
yeah, maybe that
spring jasper
I feel doing this in haskell would be better, but maybe not
Haskell lists are linked lists and they have builtin function for head, tail, inits, etc
old rover
I'm still confused tho aren't arrays just lists in python
an array means that everything is stored next to each other in memory
spring jasper
Python lists are arrays under the hood
spring jasper
Well almost
old rover
"It’s like going to a movie with your friends and finding a place to sit— but another friend joins you, and there’s no place for them. You have to move to a new spot where you all fit. In this case, you need to ask your computer for a different chunk of memory that can fit four tasks. Then you need to move all your tasks there."
this is what Grokking says about arrays
spring jasper
Sounds ok tbh
old rover
so I think he's trying to say insertion is not that great for arrays?
spring jasper
Yea because you have to reallocate space for the array
old rover
got it
he also says you can "hold seats"
like hold chunks of memory
if you want to read everything in a linked list at once
but if you want to go from one node to another node that's far away you can't
you should be using a linked list bc you can just insert stuff
right?
you don't need to move anything around just insert stuff
spring jasper
You should make a distinction of inserting at the tail or the middle
Inserting at the tail is called appending
old rover
i forgot what it's called inserting at the head
spring jasper
Thats called prepending
old rover
oh ok
spring jasper
Just know that theyre different because they have different costs
old rover
got it
spring jasper
Also depending on how you implement the linked list appending could be O(1) or O(n)
old rover
ok and when you insert stuff in a list
you change what the node/previous element points to
but when you use arrays you shift everything down in memory
same w deletion too
when you delete stuff from a linked list you just change what the previous element was pointing to
vocal gorge
yeah, you'd care about insertions and pops here
old rover
a linked list has O(1) time for insertion and O(1) time for deletion
vocal gorge
so a linked-list-based queue
old rover
bc when stuff gets inserted the nodes can just switch to where they point
and same when it gets deleted too
the only bad thing about a linked list is lookups of a specific element
old rover
so a linked-list-based queue
what if they screwed up and wanted to look at something in the middle of the queue?
or is that just a dumb question
bc then an array would be better
spring jasper
Queues dont generally have items skip ahead
grizzled schooner
@old rover that scenario is unlikely within the context of the problem
old rover
ok
uhhhhh
# Node class
class Node:
# Function to initialize the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize next as null
# Linked List class
class LinkedList:
# Function to initialize the Linked List object
def __init__(self):
self.head = None
ok how do you do this without classes?
mint jewel
you don't really make data structures without classes
mint jewel
you don't need inheritance, but you will want to learn classes if you want to make data structures in python
it helps a lot
old rover
ok will do
mint jewel
don't be heapq
old rover
a what?
mint jewel
heapq is a python module which implements a heap
old rover
where should I look to learn it?
brave oak
it's List Cosplay Day 🙂
spring jasper
Learn what heaps are first
mint jewel
but instead of it being a class, it just runs it on top of some sequences.
https://realpython.com/python3-object-oriented-programming/ this is probably useful
you can skip the section on inheritance
old rover
is a heap another data structure
mint jewel
yes
spring jasper
Its a tree with some constraints
old rover
but instead of it being a class, it just runs it on top of some sequences.
so I mean does Grokking just expect that I already know OOP?
mint jewel
probably
mint jewel
you should be fine, inheritance tends to be the part that gets people
old rover
yeah it got me when I was doing Scala
brave oak
yeah it got me when I was doing Scala
great language
😂
one of my favourites
typeclasses are beautiful
brave oak
🥴
old rover
so am I just gonna have to flat out memorize how to create a linked list?
that doesn't sound fun
no you should understand it
lean dome
Once you know what a linked list is, it's easy to make one. There's really no memorization involved.
old rover
but I do know what a linked list is
it's a list that has nodes that point to each other w pointers
agile sundial
ok, make one
old rover
without looking at the code
lean dome
then, what's the problem? A simple singly linked list is basically just:
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
n1 = Node("c")
n2 = Node("b", n1)
n3 = Node("a", n2)
then what is up with this dude's implementation
lean dome
it's java-esque. He uses setters and getters for something that could just be attributes.
but that's mostly just stylistic. It's the same structure as what I wrote off the top of my head.
old rover
am noob sorry
old rover
how do i make my bot say invalid arguments
wrong channel
old rover
all good
lean dome
the author then takes the Node class, which is essentially what I wrote (and is the actual linked list), and created a LinkedList class that wraps it and provides algorithms on top of it.
old rover
but I don't want to memorize entire functions
lean dome
so... don't...
there's no memorization involved here. If you want to find the length of a linked list, you walk it until you find a node without a next. If you want to remove a specific node from a list, you set the previous node's next to the node you're removing's next.
old rover
maybe try understanding the functions then
lean dome
to insert an element after a specific node, set the new node's next to the next of the node you're inserting after, and then set the node you're inserting after's next to the new node.
the functions are showing you implementations of an algorithm. You just need to understand the algorithm - once you know the algorithm, it's easy to implement it.
old rover
I do understand the algorithm
lean dome
then I don't understand the problem. If you understand the algorithm for finding the size of a linked list, the size() function there is trivial
old rover
great thanks this was very helpful
lean dome
I'm not sure if that was sarcastic. If it was, perhaps try describing the problem and I'll see if I can be more specific.
old rover
I do understand the data structure I just don't know how to code it from scratch
and every guide I look at is so long
lean dome
If you understand the data structure and the algorithm, then you don't need to bother with the guide. Take the simple linked list I made:
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
n1 = Node("c")
n2 = Node("b", n1)
n3 = Node("a", n2)
Take that and walk it. Find its length. Insert an extra element between a and b. Delete b.
And if you don't know how to do any of those steps - is it that you don't understand the algorithm, or you don't know how to implement the algorithm?
spring jasper
I make my implementations have a node class and a linked list class with the usual methods
Instead of manually connecting nodes like that
I've seen that in a lot of tutorials and i dont understand why
agile sundial
it's easier to understand than manually connecting nodes ¯_(ツ)_/¯
lean dome
having a LinkedList class instead of just Node allows you to represent an empty list - that can't be done as easily with only Node
you need to assign a special meaning to a specific head node, or something.
spring jasper
Its also easier to compare to the python list and its methods
lean dome
yep. But at the same time, it's one extra level of indirection, and obscures the algorithms a little. Seeing how nodes manually connect is slightly easier IMHO.
old rover
I still don’t get it
lean dome
in a real world implementation I'd have a class that wraps the collection of nodes, though, most likely.
old rover
The bad thing is I can’t just google how to make a linked list during an interview
lean dome
I still don’t get it
what, specifically?
old rover
I just don’t know how to write out the code without looking at someone else’s implementation of it
lean dome
which code? The class(es) representing the data structure itself? The methods representing algorithms on it, like getting its length, or inserting or removing elements?
lean dome
OK - what's a specific example of a class or method from that website that you wouldn't be able to implement on your own?
There's 2 different data structures and 4 different algorithms shown there, depending on how you count.
old rover
I mean
Idk what to write for insertion, search, and deleting things without looking back at it
agile sundial
are you familiar with the algorithm?
old rover
Yes
old rover
You start with the first node and you iterate through until you find the node you want bc all the nodes aren’t close together in memory like they are in an array
agile sundial
do you know how to insert a node?
i don't understand how you can be familiar with an algorithm and not be able to implement it
old rover
I don’t bc grokking algorithms shows no coding snippets w data structures
I’ll look at CLRS tomorrow and see if it does
agile sundial
huhh? it doesn't show pseudocode?
old rover
no it doesn’t
agile sundial
can you show me the page where it describes how to search for a node?
old rover
it just goes to another sorting algorithm in the next chapter
agile sundial
like a screenshot or something
agile sundial
that's still talking about arrays, that first page
agile sundial
probably the next page
agile sundial
wow
it seems that book is not meant for learning the implementation, just the application
old rover
so maybe it would be better to read CLRS for that specific section
to get more than a surface level understanding of a linked list
agile sundial
idk about clrs, you seem to have bad experiences with that book ¯_(ツ)_/¯
old rover
then idk what to do dude
gotta try something
what kind of book doesn't even teach the actual implementation of the damn data structure?
agile sundial
a book concerned about applications
agile sundial
i didn't write the book ¯_(ツ)_/¯
lean dome
The "grokking algorithms" one seems to be an ELI5 type of thing.
old rover
a what?
lean dome
"explain it like I'm 5"
old rover
oh I didn't know that acronym
lean dome
if I were trying to explain a linked list to an elementary school student, my explanation would be like that one.
old rover
yeah that's true
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
that first class Node actually does what you did in your code before
dapper sapphire
Is that book Grokking algorithm?
old rover
Is that book Grokking algorithm?
correct
still I'm sure a 5th grader could understand the implementation in psuedocode
dapper sapphire
It doesnt show the actual code?
old rover
It doesnt show the actual code?
nope
not for a linked list
for a binary search algo it does
dapper sapphire
I remember reading somewhere that the intent of the book is to give an overview of what different data structures are.
dapper sapphire
It's not intended for step by step break down of what each algorithm does.
and how to do it.
dapper sapphire
each
agile sundial
ngl, linked lists are actually terrible
dapper sapphire
lmao
old rover
they're good for a certain purpose
agile sundial
not really
dapper sapphire
why do you say that?
dapper sapphire
what matters is that I know them
Do you?
agile sundial
as someone (probably knuth or something) said that one time, "talk is cheap, show me code"
ah, linus torvalds
dapper sapphire
as someone (probably knuth or something) said that one time, "talk is cheap, sho...
Agreed.
old rover
ok here's the new plan not that anyone really cares
use Grokking to get base level knowledge of stuff
then use CLRS to solidify what you already know
dapper sapphire
Wait werent you learning big O?
old rover
yeah
dapper sapphire
I have seen CLRS being highly regarded.
old rover
well it's a tough book to read cover to cover for me at least
agile sundial
probably for anyone
old rover
extremely long detailed paragraphs make it something you want to refer to
dapper sapphire
Yeah, that's also true. I have heard that its pretty hard.
agile sundial
it is very rigorous, in the sense that everything is fleshed out
old rover
I mean
I'm gonna need to get a bit rigorous w the material
if I really want to learn it
growth mindset or what not
I also like how these questions are very code based rather than concept based
agile sundial
of course. if you can't code it, who cares if you "know how to do it"
dapper sapphire
is this CLRS?
old rover
yes
agile sundial
it seems you've found it
dapper sapphire
Are you also still learning big O? Or are you diverting your focus to implementing data structures?
old rover
Are you also still learning big O? Or are you diverting your focus to implementi...
nah I spent like 3-4 days on big O
I am not staying in big O hell
Grokking algorithms says big O is just how fast an algorithm runs
dapper sapphire
hahahaha
dapper sapphire
I'm gonna steal that "big O hell"
old rover
hahaha
I mean
what do you want me to do? spend a whole month on just big O?
ain't nobody got time fo dat
dapper sapphire
No, i personally think you are doing the right thing by implementing them.
old rover
yeah a lot of the people on pydis said you're supposed to be learning data structures and algorithms along w big O
agile sundial
of course, you can't learn big O in isolation, that's just useless
old rover
not seperately
agile sundial
yes, exactly
old rover
Actually I think at UB they taught linked lists even before they taught big O
but that doesn't really make sense to me
agile sundial
at where
old rover
university at Buffalo
but I think their CS curriculum was pretty garbage anyways
so uh I'm gonna watch some netflix and then go to bed
it's been a very long day
Thanks guys for helping me I really appreciate it
trail plover
I'm trying to write a json response to a local file, then later access the file. I can write the response locally but I'm having a hard time accessing the data locally, if that makes any sense). Could anyone help?
old rover
Does it have to do w algos/DS?
dapper sapphire
json would be something you would get when you make a request to a server/api
You make a request and you get a response, that format of the response depends on who designed it, but in most cases it's json.
old rover
Yeah the only time I heard of JSON was web related stuff
trail plover
Yeah, currently I get the response and dump it into a local file, but it seems I can't access/print parts of it locally. I realize I should probably just open a help channel for this though
dapper sapphire
What do you mean, "seems I can't access/print parts of it locally"?
trail plover
What do you mean, "seems I can't access/print parts of it locally"?
when I try something like
print(tempFile['48hours'][1]['moving_avg'])
I get an error about
json.decoder.JSONDecodeError: Expecting value: line 1 column 1 (char 0)```printing just the tempFile gives me the same error
dapper sapphire
then there's something wrong with your tempFile, probably the way you are reading your json and storing it inside tempFile
how are you reading your json?
trail plover
with open('data.json', 'w') as outfile:
json.dump(requests.get(("https://api.warframe.market/v1/items/{}_prime_{}/statistics").format("ash","blueprint")).json()['payload']['statistics_live'], outfile)
with open('data.json') as json_data:
d = json.load(json_data)
print(d)
this prints the entire json
drowsy orchid
dapper sapphire
```py
with open('data.json', 'w') as outfile:
json.dump(requests.get(("https...
So you are able to print the entire json, but not part of it?
trail plover
Yeah, basically it wont let me access it like a json
Thought as far as I understand json.load should fix that
dapper sapphire
Then that has to do with your query
Something is not correct here, data['48hours'][1]['moving_avg']
trail plover
I replaced that section of the code, the entirely of my code is what I put in chat now. Heres what the json looks like just for reference
dapper sapphire
Yeah, basically it wont let me access it like a json
It should be 0 instead of 1.
wait my bad.
trail plover
Even ignoring the [1] and only putting ['48hours'] errors. However I'm trying to access it is incorrect, I just cant figure out why
dapper sapphire
can you paste your json here?
If it's not sensitive data and you are comfortable.
trail plover
Someone just helped me figure it out. I just needed to change how I'm printing
print(d['48hours'][1])
dapper sapphire
so can you do print(d['48hours'][1]["moving_avg"])?
trail plover
I was trying to change what part of the json d would be equal to, but since d becomes a dict I guess I can just access the separate sections
I can print that yeah
dapper sapphire
Then what was wrong?
trail plover
The way I was trying to print. I was trying to do ```py
d = json.load(json_data['48hours'])
print(d)
instead of
```py
d = json.load(json_data)
print(d['48hours'])
Oh ok yeah you have to pass the whole file when you load, and then afterwards you can access specific part of it.
trail plover
Oh ok yeah you have to pass the whole file when you load, and then afterwards yo...
Anyway, thank you
pure bronze
mint jewel
your file is still called rich.py
so python is importing that instead of the rich module
tiny niche
Do we really need to split array recurcivesly in mergesort?
when we can just split them in half and sort them using two pointers?
no, both approaches work and one of them doesn't require copying the array
inland iron
Im trying to make a defined algorithmic function that can determine if an inputed word is a palindrome or not (a word that is the same backwards, like racecar). are there any ways i could do this? This is for an assignment, so dont just give me the answer. All i need for now is a method i can build off of.
So far im thinking a loop and a list of some sort
agile sundial
sure, have you written any code?
inland iron
yeah
print ("Welcome to the PALINDROMATIC 5000!")
print("Please do not input numbers, symbols, individual letters, or special characters. (such as: A $ 5 ♡.)")
def checkPalindrome(str):
str = input("Please input a word: ")
reversedword = []
characterindex = len(str)
while characterindex > 0:
reversedword += str[characterindex - 1]
characterindex = characterindex - 1
return reversedword
reversedword = ''
if str == reversedword:
print("Yes")
else:
print("Naw")
print(checkPalindrome(str))
return reversedword will stop the function
inland iron
right
mint jewel
also, you take str as an argument, but instantly override it
inland iron
yeah, i fixed that
mint jewel
that isn't a bug, just weird code.
inland iron
print ("Welcome to the PALINDROMATIC 5000!")
print("Please do not input numbers, symbols, individual letters, or special characters. (such as: A $ 5 ♡.)")
def checkPalindrome():
str = input("Please input a word: ")
reversedword = []
characterindex = len(str)
while characterindex > 0:
reversedword += str[characterindex - 1]
characterindex = characterindex - 1
return reversedword
if str == reversedword:
print("Yes")
else:
print("Naw")
print(checkPalindrome())
What can I say, im a relatively new python user
I also mostly learn by trial and error but i dont have time for that, it takes too long
mint jewel
at least your reversing logic seems to work correctly
inland iron
Cause i looked up how to reverse a string but yeah
at the very least i can understand the reversing loop
but now I need to convert the list it outputs back into a string
halcyon plankBOT
mint jewel
is that understandable to you?
inland iron
yeah
old rover
hey I got a question
why is it that CLRS shows the psuedocode for searching stuff in a linked list, inserting stuff into a linked list, and deleting stuff from a linked list
but it never actually shows how to create the linked list??
I guess it just assumes that you already know how to make one???
inland iron
def checkPalindrome():
str = input("Please input a word: ")
reversedword = []
characterindex = len(str)
while characterindex > 0:
reversedword += str[characterindex - 1]
characterindex = characterindex - 1
reversedword = str.join(reversedword)
return reversedword
print(checkPalindrome())
``` Okay, oi added the join method, and it works but it prints multiple of the reversed characters. Like, if i input "racecar" it outputs "rracecararacecarcracecareracecarcracecararacecarr"how you create a linked list depends on the language
agile sundial
it does describe it
old rover
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
n1 = Node("c")
n2 = Node("b", n1)
n3 = Node("a", n2)
yeah but it doesn't show an implementation of it in psuedocode
agile sundial
agile sundial
it's right there
inland iron
what ami doing wrong
old rover
I know the difference between a linked list and a doubly linked list
where?
I don't see any psuedocode there
agile sundial
if i describe an algorithm to you in english, that's pseudocode
mint jewel
@inland iron the way you use str.join is like separator.join, so you want to write ''.join to join with no separator
it is the opposite order from what you would expect
agile sundial
it says:
each element of a doubly linked list L is an object with a key field
and two other pointer fields: next and prev
@old rover
mint jewel
the reason it went wrong as it did is because your parameter str
so you were joining reversedword with the original input as separator
old rover
it says:
> each element of a doubly linked list L is an object with a key field...
what's a key field?
agile sundial
it's a variable, which stores a "key"
old rover
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
n1 = Node("c")
n2 = Node("b", n1)
n3 = Node("a", n2)
so then what is the key field here?
agile sundial
self.data
old rover
I get what's happening up till the n1 = Node("c")
that's the first node
and then it goes to node B, and the reference is back to node 1?
old rover
ok
old rover
also this is for a doubly linked list
old rover
pointing to the other node
someone told me that there are no pointers in python
just references
agile sundial
that's correct
old rover
and references are just addresses in memory
agile sundial
sure
inland iron
Okay, now i have another assignment, but its the same as the one i just did. i just have to refactor my code: ```py
print ("Welcome to the PALINDROMATIC 5000!")
print("Please do not input numbers, symbols, individual letters, or special characters. (such as: A $ 5 ♡.)")
str = input("Please input a word: ")
def checkPalindrome():
reversedword = []
characterindex = len(str)
while characterindex > 0:
reversedword += str[characterindex - 1]
characterindex = characterindex - 1
reversedword = ''.join(reversedword)
if reversedword == str:
print("This word is a palindrome.")
return True
else:
print("This word is not a palindrome.")
return False
print(checkPalindrome())
do you have any ideas about how you would go about solving that?
inland iron
None
I mean, i refactored the code: ```py
def checkPalindrome(word):
reversedword = []
characterindex = len(str)
while characterindex > 0:
reversedword += str[characterindex - 1]
characterindex = characterindex - 1
reversedword = ''.join(reversedword)
if reversedword == str:
return True
else:
return False
print(checkPalindrome("racecar"))
print(checkPalindrome("banana"))
class linkedListNode:
def__init__(self, value, nextNode = None):
self.value = value
self.nextNode = nextNode
node1 = linkedListNode("3")
node2 = linkedListNode("7")
node3 = linkedListNode("10")
node1.nextNode = node2
node2.nextNode = node3
can someone explain why the colon after linkedListNode is being underlined in red?
agile sundial
is that the entire file?
old rover
yes
old rover
so one more to the right?
agile sundial
in between def and __init__
old rover
oh yeah I was wondering why it didn't get highlighted
thanks dude
yeah I really like this video for linked lists
it's in python 2.7 but who cares
old rover
you like snake case more?
so if this was a doubly linked list
wouldn't you just be using the .nextNode thing more?
so it's really not that bad
and CLRS has functions you can add to your linked list to make it do stuff
old rover
CLRS has functions that can make your linked list do stuff?
like insertion, deletion, searching
grizzled schooner
yeah...
agile sundial
ok?
old rover
time to add those
spring jasper
You need a linked list class for those
old rover
damn why doesn't it say that in CLRS
agile sundial
because you don't actually need a linked list class for those
old rover
but he just said
old rover
ok then thanks
spring jasper
It would make sense that those functions are part of a linked list class and not top level or part of the node class
agile sundial
it would, but it's not necessary
especially if you're unfamiliar with the oop concepts
grizzled schooner
also, afaik clrs tends to not give the overall structure of the code, only the individual functions
old rover
class linkedListNode:
def __init__(self, value, nextNode = None):
self.value = value
self.nextNode = nextNode
node1 = linkedListNode("3")
node2 = linkedListNode("7")
node3 = linkedListNode("10")
node1.nextNode = node2
node2.nextNode = node3
def listSearch(List, node):
x = List.head()
while x != None and x.node !=node:
x = x.nextNode
return x
ok I don't think there's any such thing as x.next
I think they mean next node?
agile sundial
yes
timid sluice
yes
agile sundial
it says so in the text
old rover
it probably says what x.next is before bc I don't see it in that paragraph
agile sundial
that's correct
grizzled schooner
It would be a good idea to read the paragraphs carefully
old rover
I am not reading this book cover to cover
I am reading the paragraphs that come w the functions
agile sundial
def listSearch(List, node):
x = List.head()
while x != None and x.node !=node:
x = x.nextNode
return x
you don't have a head method defined anywhere
old rover
I actually don't know how to write the head method of the linked list
agile sundial
I am not reading this book cover to cover
sure, but it'd certainly be useful to read the entire linked list section, since yuo're learning aobut linked lists
timid sluice
do you want that List to be head
you don't need .head() you need a list head variable
to be pass into the function
old rover
I need an extra paramater?
timid sluice
I'd suggest you read the book, but implement the idea yourself
old rover
I did read the chapter
timid sluice
Then you should know how it works
def listSearch(List, node): The List is already head of the list
old rover
ok
def listSearch(aList, node):
x = aList
while x != None and x.node !=node:
x = x.nextNode
return x
so is this correct then?
agile sundial
does it work?
old rover
I don't even know how to test it
agile sundial
create some nodes, connect them together, and use your function on it
vocal gorge
create some random lists, make them into linked lists, and test that your function returns the same position as .find on the original list
old rover
class linkedListNode:
def __init__(self, value, nextNode = None):
self.value = value
self.nextNode = nextNode
node1 = linkedListNode("3")
node2 = linkedListNode("7")
node3 = linkedListNode("10")
node1.nextNode = node2
node2.nextNode = node3
I have some nodes over here that I connected into a linked list
grizzled schooner
ok great, now try searching for one of them
timid sluice
that makes sense
mint jewel
later, I suggest you make a enlist function which will convert a list to a linked list
old rover
that exists????
agile sundial
it would if you make one
timid sluice
yep
vocal gorge
in some way, every function one can think of exists 😉
mint jewel
some don't
mint jewel
for example
def contains_infite_loop(program):
...
wdym?
spring jasper
Bro focus on this one
old rover
focus on what??
mint jewel
ye, write the search
spring jasper
The search thing
mint jewel
the conversion is harder
timid sluice
node = linkedListNode("3",
linkedListNode("7",
linkedListNode("10")))
so that's the entire linked list
agile sundial
yep
old rover
# This Function checks whether the value
# x present in the linked list
def search(self, x):
# Initialize current to head
current = self.head
# loop till current not equal to None
while current != None:
if current.data == x:
return True # data found
current = current.next
return False # Data Not found
I found this code on geeksforgeeks
old rover
yeah
vocal gorge
so it's __contains__, basically.
timid sluice
magic word
old rover
uhhh
vocal gorge
This method is how you'd implement the __contains__ magic method, which would allow in checks
vocal gorge
Have you written your own classes before?
spring jasper
You've never used in?
old rover
I used in
timid sluice
lol
vocal gorge
that's why - you need to know the magic methods when implementing your own classes with operators
It's a good goal to make your LinkedList one - you'll learn how to implement in, +, .extend (like on lists), how to do classmethods (to implement enlist)...
old rover
yeah
I'm just struggling
no two people implement a linked list the same
class linkedListNode:
def __init__(self, value, nextNode = None):
self.value = value
self.nextNode = nextNode
node1 = linkedListNode("3")
node2 = linkedListNode("7")
node3 = linkedListNode("10")
node1.nextNode = node2
node2.nextNode = node3
this part mostly stays the same
# This Function checks whether the value
# x present in the linked list
def search(self, x):
# Initialize current to head
current = self.head
# loop till current not equal to None
while current != None:
if current.data == x:
return True # data found
current = current.next
return False # Data Not found
what do they mean by current here?
agile sundial
it's the node you're currently checking
agile sundial
that's your "key"
old rover
sigh
grizzled schooner
is there a reason you're not using the pseudocode in clrs?
old rover
I have been using the psuedocode in CLRS for the past hour at least
and I haven't gotten anywhere
grizzled schooner
do you know what's giving you problems?
elfin pumice
hi hi : )
old rover
I understand the psuedocode
I just don't know how to write it in actual code
.head is a method in python right?
agile sundial
no, it's an attribute
old rover
it doesn't even show how they even create .head
agile sundial
because it's different for every language
vocal gorge
it's just an attribute they make the node-object have
agile sundial
seems like it's their linked list class
old rover
class SingleLinkedList:
def __init__(self):
"constructor to initiate this object"
self.head = None
self.tail = None
return
I googled how to find the head of a linked list and this is what I found
agile sundial
ok
old rover
I just wish the book didn't assume I just knew how they did .head
but wishing won't change anything
spring jasper
Its just a method that gets the first item in the list
icy venture
how do you post code?
spring jasper
You dont even need it
agile sundial
it does say in the introduction of the book, that it is not an introductory text for people who don't know how to program
it assumes familiarity with basic language concepts
icy venture
class Solution(object):
def twoSum(self, nums, target):
self.nums = nums
self.target = target
self.indicies = []
for i in nums:
if target - i in nums:
x = nums.index(i)
self.indicies.append(x)
print(self.indicies)
im not sure why im getting the first 0 when outputted?
old rover
oh boy I asked in my college's coding server and now they're saying to do it in C++
agile sundial
it is probably a better language for dsa
old rover
but python
spring jasper
The language doesnt matter and anyone telling otherwise is a dumbass
old rover
what is a constructor?
grizzled schooner
Try thinking about it logically; you know what the head of a list is, right? so when the user creates the head of the list, you can set self.head to that node
old rover
I kinda forgot the definition
agile sundial
i'm not saying you can't learn dsa, but you must have a handle on programming in your language of choice before tackling them
a constructor creates and initializes an object
vocal gorge
If you end up doing it in another language, there's an entire guide on Rust based on implementing tons of shitty linked lists 🙂
https://rust-unofficial.github.io/too-many-lists/index.html
agile sundial
i love that tutorial
vocal gorge
(even with a rant at the beginning about why linked lists are horrible and why no one should ever use them for anything except educational purposes)
scarlet maple
(even with a rant at the beginning about why linked lists are horrible and why n...
(thats the same explanation as why you have to learn freudian psychology in every intro to psych class)
"here are all of freudians theories. also they are all wrong"
"but learn them anyways bc hes the father of psychology"
vocal gorge
because Freudian psychology, despite being an outdated pseudoscience, happens to be exactly as effective as fancy modern psychotherapy methods? 😛
scarlet maple
💀
old rover
sounds like the people who worshipped Siraj Rival
vocal gorge
I just realised this isn't offtopic.
scarlet maple
when all the channels merge together
austere sparrow
(even with a rant at the beginning about why linked lists are horrible and why n...
Yeah, cache locality = dead
Although streams (infinite lists) are kinda useful, and they're sort of like linked lists
agile sundial
linked lists are still good for merging and inserting near the center
although, that is quite rare
old rover
def add_list_item(self, item):
"add an item at the end of the list"
if not isinstance(item, ListNode):
item = ListNode(item)
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
so isInstance returns a boolean
if it matches the data type in the second paramater?
old rover
class SingleLinkedList:
def __init__(self):
"constructor to initiate this object"
self.head = None
self.tail = None
return
this is how they create the .head method
is that how CLRS wants me to do it?
spring jasper
head isnt a method there
old rover
is a stack another data structure?
agile sundial
yes
old rover
oh well F in the chat for me ig
I'm looking at this book and it doesn't implement a linked list on its own
vocal gorge
well, in a way
old rover
only w a stack
vocal gorge
stacks can be implemented via linked lists
it depends on what methods you attach to your linked list, basically
agile sundial
stacks can also be implemented via arrays
vocal gorge
true
old rover
searching a linked list
vocal gorge
didn't you make a working method for that?
vocal gorge
Pretty much:
- Take the head as the current node
- Until you find a node that has the right value or hit a node without a
.next(the tail), take the current node's.nextas the new current node.
old rover
but I can't even take the head of the current node
bc I don't know how to write the function to take the head
vocal gorge
Of the linked list, you mean? Why?
spring jasper
The head is the first node
vocal gorge
I think you don't quite get how linked lists work
old rover
yeah I know the head is the first node
spring jasper
Ok then whats the problem
old rover
I don't know how to write the code for it
vocal gorge
There are two ways to implemnet a linked list, basically:
- Only have the Node class. It has a certain
.nextand a value, and that's it. To hold a reference to the linked list, you hold a reference to its head node. The problem with that approach is that you can't really truly modify the list in a way that changes it head - you'd need to somehow tell every other function/whatever that has a reference to the first node "hey, the head is changed now"
- Have a
Nodeclass, and also have aLinkedListclass. The latter would have a reference to itshead, a reference to itstail, maybe also itslength, and have all the methods for working with linked lists.
With the second approach, the problem of the first one vanishes - one only holds the reference to the linked list itself, and the list's head can be updated however you want.
It seems to me that you're confused because you're trying to use the former approach and so are confused what head is supposed to be.
So use the second one - you need another class.
floral dew
@vocal gorge im here now 🙂
also, regarding the constant M
Let
T(n)andf(n)be two positive functions. We writeT(n) ∊ O(f(n)), and say thatT(n)has order off(n), if there are positive constantsMandn₀such thatT(n) ≤ M·f(n)for alln ≥ n₀.
there's the M... idk what's its purpose lol
vocal gorge
ah, I see. Yeah, it's the definition.
vocal gorge
there's the M... idk what's its purpose lol
Because what that means is that, say, n^2 is not O(n). Why? Because no matter what M you choose, even 10**100, the statement n^2 < M n will stop being true for sufficiently big n.
But 48101203213 n is O(n) (pick any M bigger that 48101203213)
floral dew
Because what that means is that, say, `n^2` is not `O(n)`. Why? Because no matte...
OHHHH I GET IT NOW!
so the M is there to signify this sort of... transcendence almost
vocal gorge
yeah
essentially, this is necessary for the definition to be invariant with regards to multiplication by a constant. The O-notation is about, basically, making a hierarchy of functions that asymptotically exceed each other.
floral dew
linked lists! love 'em
vocal gorge
Any function that's O(n log n) will eventually exceed a function that's asymptotically O(n), and they will exceed the O(sqrt(n)) ones, and so on
old rover
but I know that bc it's hard coded in there that it's 3
vocal gorge
ok so the head here would be node1 right?
yeah
old rover
how do I find the head if I'm not creating the node myself?
floral dew
Any function that's O(n log n) will eventually exceed a function that's asymptot...
yep thx so much! i understand
old rover
you can't go linkedList[0] bc there's no index since they're far apart in memory
floral dew
wait... this means that AFTER FOUR FKING ATTEMPTS I FINALLY COMPLETELY UNDERSTOOD THE DEFINITION OF BIG O
YESSSSSSSSSSSSSSSSSSSSSSSSSSS
vocal gorge
how do I find the head if I'm not creating the node myself?
With approach 1, the head is the node that's passed to you, always (there's nothing special about the head with approach1, so that's the only way you can know what the head is).
With approach 2, make a LinkedList class - you're still lacking it.
old rover
ok so I created a linkedList class
floral dew
ok so I created a linkedList class
is that camelCase i see in a class name??
jolly mortar
PascalCase pls
vocal gorge
your linked list is basically a "wrapper" around the chain of nodes inside
old rover
idk what Pascalcase is dude
jolly mortar
LinkedList instead of linkedList
floral dew
idk what Pascalcase is dude
like camelCase but you capitalize the first word as well
jolly mortar
but whatever
vocal gorge
it should have a head attribute, a tail attribute, maybe a length attribute, and of course, that's what you'll attach all the methods to.
head and tail will be references to Node instances. A LinkedList always has a head and a tail unless it's empty.
(if it's length 1, they are the same Node).
old rover
class LinkedList:
def __init__(self, head, tail, length):
self.head = head
self.tail = tail
self.length = length
like that?
vocal gorge
mmm, it'd be pretty annoying to create the list like that
because it'd mean you have to manually build the list like you were doing before you can wrap it in a LinkedList
instead, I'd suggest just:
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
and then start attaching methods, starting with push (append a node to the tail) and pushleft (append a node before the head)
old rover
is that self.head = None the same thing as putting head = None
in the def init paramater?
def init(self, head= None)
like that?
vocal gorge
No, in my case the init accepts no arguments.
vocal gorge
After you implement these two methods, you'll be able to build your lists pretty easily.
vocal gorge
depends on whether you need to
old rover
if I wanted to do search through the linked list
vocal gorge
I'd implement building it first.
agile sundial
a bit difficult to search through something you don't have
vocal gorge
Since I get the impression you don't quite get why this should be done this way, still, and implementing a working LinkedList will probably make it clearer.
So make a list you can add elements to, then bother with searching.
the idea behind push is basically:
- if the list is empty, just make the new Node the new head and new tail.
- If it's not, take the current
tail, and set the new Node as its.next. - In both cases, increment
.length.
start with that.
oh, and step 0) wrap the value you need to add in a Node
old rover
oh lord what have I gotten myself into
vocal gorge
...linked lists? 😛
old rover
why is all the code for linked lists I look at manually coding the linked list
but not building the linked list with an input
interesting
mint jewel
why does the book even start with linked lists?
jolly mortar
don't they all
agile sundial
no lol
mint jewel
I would hope not
when in procedural programming do you even see a linked list
compile time macros creating traces
jolly mortar
I dunno
the first ds in almost all the resources I've ever come across is linked list
mint jewel
I guess an array is too simple
agile sundial
you'd think, but start with a vector then 😔
old rover
idk what those are yet
mint jewel
a binary search tree <> binary search
old rover
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.last_node = None
def append(self, data):
if self.last_node is None:
self.head = Node(data)
self.last_node = self.head
else:
self.last_node.next = Node(data)
self.last_node = self.last_node.next
def display(self):
current = self.head
while current is not None:
print(current.data, end = ' ')
current = current.next
a_llist = LinkedList()
n = int(input('How many elements would you like to add? '))
for i in range(n):
data = int(input('Enter data item: '))
a_llist.append(data)
print('The linked list: ', end = '')
a_llist.display()
i thought it meant isomorphic
mint jewel
It can mean a lot of things
old rover
so is that append function how you build a linked list?
mint jewel
it is very flexible
old rover
the code?
agile sundial
it is very flexible
fair enough ¯_(ツ)_/¯
old rover
god knows I haven't even tried it
is the reason why they're setting last_Node = None bc it doesn't exist yet?
mint jewel
ye, the constructor should create an empty linked list
old rover
ok
vocal gorge
...why did you change tail to last_node?..
agile sundial
i think you need to just stop looking up code, and start producing your own
old rover
I would if I knew what to write
vocal gorge
it also doesn't do what I described. Rather, your append is what I described above as pushleft - it appends to the beginning of the list.
agile sundial
review your resources until you are able to produce a linked list on your own
old rover
dude
I have been staring at CLRS for the past 2 hours
and Grokking too
and the other book I have
mint jewel
or start even simpler than a linked list. Try making a box. It holds a single value and has get and set methods
get returns the value in the box, set sets the value in the box
grizzled schooner
if you're not able to do it on your own, maybe you're not ready to do it yet.
vocal gorge
~~I would if I knew what to write~~
Well, see my message above:
the idea behind
pushis basically:
- if the list is empty, just make the new Node the new head and new tail.
- If it's not, take the current
tail, and set the new Node as its.next.- In both cases, increment
.length.
So:
def push(self, val):
node = LinkedListNode(val) # wrap the value in a node
if self.length == 0: # if the list was empty, make it the head and the tail
self.head = self.tail = node
else: # otherwise, append to the tail and make the node the new tail
self.tail.next = node
self.tail = node
self.length += 1
damn dude maybe you should try never learning anything that you have a hard time w initially
mint jewel
if self.last_node is None:
self.head = Node(data)
self.last_node = self.head
else:
self.last_node.next = Node(data)
self.last_node = self.last_node.next
``` that looks about the same as this, expect not storing an internal lengthConsider now how to do pushleft (or whatever the common way to call that method is). It'll be very similar, but you need to set the head to the new node, and make sure the new node's next is set to the old head.
mint jewel
I am serious, try making a box. Maybe learning classes and data structures and algorithms is too much at once for you. That is fine
take it step by step
there is nowhere to rush to
old rover
I don't want to make a box
floral dew
if you're not able to do it on your own, maybe you're not ready to do it yet.
...well that's not good learning attitude
mint jewel
if you have no idea where to really go with a linked list, you need more practice with simpler classes. That is perfectly fine. Keep in mind textbooks are supposed to have a highly competent teacher along with them explaining everything, not be used alone. Which is why they start so harshly a lot of the time
grizzled schooner
sorry, i didn't mean that you should just give up, but sometimes it's better to wait until you have more experience. i remember a couple months ago i got really confused whenever i looked at anything oop-related, but now i'm able to understand much better because i have more experience
old rover
I'm not waiting for another couple of months
I'm doing it and I'm doing it now
I understand helping a complete beginner to DS/algos is frustrating
especially when you're like how do they not understand this concept? I learnt it in one day
mint jewel
that is not the issue here. I just think you would have an easier time if you started with something simpler and worked your way. If you bash your head against a wall long enough, it will work, but there are better ways to learn.
old rover
this is one of the simplest data structures
old rover
well if you go through hell keep going
mint jewel
I have no idea why they are so common, they are really only used for flow control with recursion and some obscure places
grizzled schooner
clrs starts with stacks, right? maybe try that and go in order of the textbook
mint jewel
stacks are a useful data structure
old rover
Nah I like Grokking more
I don't like the gigantic paragraphs with every miniscule detail involved
even now I still don't get entirely what CLRS is saying after reading the chapter multiple times
mint jewel
very well, lets get back to bashing heads against the wall
old rover
welcome to daspecito land
mint jewel
how far did you get with writing a linked list yourself?
old rover
hey at least I'm not trying to do leetcode questions without knowing any ds/algos
old rover
how far did you get with writing a linked list yourself?
I created a linked list manually
but I didn't know how to create it w someone else's input
mint jewel
ah, I remember now
alright, an easier operation than append or push is just prepend
where you take a linked list, a value and create a new linked list which starts with that value
make that function
what actually the proper name for this that isn't cons
old rover
I found a GitHub repo
that actually does all off the adding and searching in a couple of lines
I will check it out after lunch
@mint jewel it you want to look at it
mint jewel
that's a doubly linked list
old rover
ok then that’s just one thing to change
a doubly linked list just has the pointers from a node pointing to the previous one and the one ahead
mint jewel
If you think looking at a complete implementation of a linked list would help you, I could write one.
old rover
yes please
class Node :
def __init__( self, data ) :
self.data = data
self.next = None
self.prev = None
class LinkedList :
def __init__( self ) :
self.head = None
def add( self, data ) :
node = Node( data )
if self.head == None :
self.head = node
else :
node.next = self.head
node.next.prev = node
self.head = node
def search( self, k ) :
p = self.head
if p != None :
while p.next != None :
if ( p.data == k ) :
return p
p = p.next
if ( p.data == k ) :
return p
return None
def remove( self, p ) :
tmp = p.prev
p.prev.next = p.next
p.prev = tmp
def __str__( self ) :
s = ""
p = self.head
if p != None :
while p.next != None :
s += p.data
p = p.next
s += p.data
return s
so like how do you tell that this is a doubly linked list?
mint jewel
every node has a self.next and a self.prev
jolly mortar
every Node has a prev and a next reference
halcyon plankBOT
old rover
also
they just use .head exactly like how the textbook does
but no one ever shows how they defined head
grizzled schooner
The code that you just posted defines head.
grizzled schooner
```python
class Node :
def __init__( self, data ) :
self.data = data...
.
old rover
I thought you guys wanted me to write a function for head
mint jewel
yes please
https://paste.pythondiscord.com/ekakakafew.rb there ya go. Ran some unit tests, so it should be correct at least, feel free to ask if you have questions (no idea why it indents with tabs, in the file its with spaces.)
old rover
this is great thanks
class Node:
def __init__(self, head, tail):
self.head = head
self.tail = tail
def __repr__(self):
return f'({self.head!r} {self.tail!r})'
so you can't call .head without this?
I thought it was just a property
class LL_Node: # class of linked list node objects
def __init__(self, data, next=None):
self.data = data
self.next = next
def update_data(self, new_data):
self.data = new_data
def update_next(self, new_next):
self.next = new_next
class LL: # actual linked list
def __init__(self, base_list=[]):
self.head = None
for elem in base_list:
self.head = LL_Node(elem, self.head)
... # other linked list functions
like here's some code that just uses .head
mint jewel
most of the lists you will find do this silly thing where they use self.head on the list itself to be the top node
and then self.head of the node is the value at that node
vocal gorge
what's that !r?
vocal gorge
oh, nice, never seen that before
mint jewel
so a list of strings would print with quotes
mint jewel
return f'({self.head!r} {self.tail!r})'
old rover
ok
mint jewel
don't worry about how this works too much, it was more to help pytest give sensible output than to be part of the example
old rover
when you say this is more or less entirely wrong are you referring to the code I sent?
mint jewel
head of a linked list is always a single value
you can see how head is implemented in my case
def head(self):
try:
return self.value.head
except AttributeError:
raise ValueError("head of empty list")
it just returns the head of the top node
undone mauve
every node has a self.next and a self.prev
in a doubly linked list
mint jewel
it was in response to
undone mauve
ahh
mint jewel
ah, I should've made pop_left
undone mauve
this is more or less entirely wrong
howcome
mint jewel
because now you have two things the head of a list means
and what it actually make sense to mean is the first value of the list
since tail then becomes the second node
first node is just the list itself
undone mauve
hmm
mint jewel
most linked lists don't cache the last elements, that is only really useful for linked list backed queue
undone mauve
what would you call the first node then
mint jewel
data LinkedList a = Node a (LinkedList a) | Nil
the only reason to have separate class from the node itself is if you want a queue
which my example isn't, since I have no poll
undone mauve
ah
mint jewel
the way we defined linked lists in gurklang was literally just 2 long tuples
(head, (element, (next_element, None)))
``` with absolutely no classesdamn why doesn't python do that
mint jewel
because most of the time, you don't need linked lists in python
mint jewel
that is true
grizzled schooner
and advent of code :P
old rover
what's advent of code?
mint jewel
when did you need a linked list for that?
I can't think of too many real algos where that is used
grizzled schooner
series of short algo problems throughout december, one per day like an advent calender
err i think it was one of the later days, it probably involved inserting in the middle of a list or something? i kind of forget
mint jewel
that seems like a case for a finger tree
though a linked list is probably easier to implement
grizzled schooner
but the input was large enough that using other things would take way too long
yeah, maybe
mint jewel
I still don't know how linked lists got such a special treatment
a trie is arguably more useful, but most programmers aren't expected to know how to make one
old rover
you ever heard of that joke
reversing a linked list
or something like that
I think the other one is like inverting a binary tree or something
class Node(object):
# Each node has its data and a pointer that points to next node in the Linked List
def __init__(self, data, next = None):
self.data = data;
self.next = next;
# function to set data
def setData(self, data):
self.data = data;
whoms't
what does setData even do?
mint jewel
that is just bad code
old rover
so skip that ig
mint jewel
you won't get anywhere googling around for a perfect linked list implementation
mint jewel
well, start by making a node class. You saw several already, but write one yourself, actually typing out all the characters
just a basic head tail one
old rover
uhhhh
you know what lakmatiol?
what I was looking back at I don't think this person even knows python
class Node(object):
# Each node has its data and a pointer that points to next node in the Linked List
def __init__(self, data, next = None):
self.data = data;
self.next = next;
semi colons after everything????
sus
mint jewel
you could tell from the fact they made a setData function
no competent python programmer makes a setter function
old rover
guess you shouldn't just randomly look at someone's github repo for implementations when they don't even know the language
mint jewel
most of the code on the internet is quite bad
undone mauve
wack
mint jewel
so you will find it in older code
undone mauve
are there any alternatives
mint jewel
what do you mean alternatives?
old rover
was semi colons after everything ever needed in python?
undone mauve
like things you can put other than option
fuck
things you can put other than object
lmao
mint jewel
that is where you put parent classes, and optionally a metaclass, as well as kwargs for __init_subclass__
old rover
what's kwargs....
mint jewel
it is nice if a function has a lot of arguments
old rover
yeah it's like type hints but w paramaters
undone mauve
interesting
old rover
class Node :
def __init__( self, data ) :
self.data = data
self.next = None
self.prev = None
class LinkedList :
def __init__( self ) :
self.head = None
def add( self, data ) :
node = Node( data )
if self.head == None :
self.head = node
else :
node.next = self.head
node.next.prev = node
self.head = node
ignoring the fact that it's a doubly linked list
what do you guys think of this code?
this is how insertion is written in pseudocode in CLRS
I don't get what they mean by x.next
the next node?
are subclasses just classes below classes?
old rover
x.next isn't really explained
vocal gorge
I don't get what they mean by x.next
They mean the attributenextofx😛
which for Nodes is a reference to the next node or None
vocal gorge
WDYM by that?
old rover
what's a field?
vocal gorge
mmm, all of this terminology is somewhat hard to explain in Python because it doesn't really have fields like structs in C-like languages do. Basically, by field I mean "attribute that is a value (not a method)"
so yeah, property, field, attribute - basically interchangable.
vocal gorge
Of LinkedList instances, yes.
old rover
damn so that helper was wrong then
vocal gorge
damn so that helper was wrong then
hmm?