that just how mathematicians name things
#algos-and-data-structs
mint jewel
that's my (voluntary) job
old rover
š
vocal gorge
I mean, it's not like it just provides the code with no comments, there's a description of what the code does and what the variables mean
old rover
it does say "given an element x"
so that's ok ig
hey at least I am improving my reading skills by doing this stuff
the first node is getting assigned to the next node?
am confused
Inserting into a linked list
Given an element x whose key attribute has already been set, the LIST-INSERT procedure āsplicesā x onto the front of the linked list, as shown in Figure 10.3(b).
this is all it says
vocal gorge
What line is confusing?
old rover
why are they assigning x.next = L.head?
def listInsert(linkedList, aNode):
aNode.next = linkedList.head()
if linkedList.head != None:
linkedList.head.prev = aNode
linkedList.head = aNode
aNode.prev = None
this is how I put it in Python code
vocal gorge
Because after the new node is put at the beginning of the list, that node's successor will be the node that's currently (but not for much longer š ) the head.
old rover
and that is why linked lists have O(1) time complexity for insertions
and deletions as well
maybe it would help if I saw it visually?
vocal gorge
and that is why linked lists have O(1) time complexity for insertions
because the code only ever works with the current head and doesn't care at all about the size of the list, yes.
old rover
and you would slightly alter the code to insert it at the end or at the beginning
is this code inserting stuff at the end or the beginning?
or does it depend on what you put in
vocal gorge
is this code inserting stuff at the end or the beginning?
What do you think?
vocal gorge
I mean, in addition to the code reassigning the head of the list to the new node (so it becomes the new head, so it's added to the beginning), it's also mentioned here:
vocal gorge
Because after the new node is put at the beginning of the list, that node's succ...
and I too mentioned it:
old rover
I should really read everything before I talk
also
is the term for adding to the front of a linked list still prepending?
or is it a different term
It's a list so why would the term be different
vocal gorge
I don't really care about the terms much and not sure who does, so sure I guess š
old rover
idk why I care
dumb question
"The procedure LIST-SEARCH.L;k/ finds the first element with key k in list L by a simple linear search, returning a pointer to this element."
what is a key?
vocal gorge
old rover
is a key an element?
vocal gorge
the data attached to the node, basically. What you've been calling .data in some of your snippets and I called .val a few times.
old rover
ohhhhhhh
ok
I have another question
is the head also considered a node?
yes right?
I'm watching a vid of them visually putting a node in
vocal gorge
The head is a node.
The head of a list is its first node. The tail is the last one.
Or if you prefer to think of it this way: llist.head is a reference to a Node or None.
old rover
ok bc I just watched this shit and it confused me
what the hell is ptr???
what language is that??
oh it's in C
ok
vocal gorge
welcome to the beauty of raw pointers
where if you implement your linked list incorrectly, you'll get a segmentation fault trying to access it!
old rover
does that happen in python?
agile sundial
only if you let it
vocal gorge
Python doesn't have raw pointers.
You can't have a reference which doesn't lead to what it should lead to.
agile sundial
ctypes will let you mess with the underlying C, but you won't get any issues if you're not messing with that
vocal gorge
and you also need to manually allocate memory in C, say.
basically use Rust instead lol(no raw pointers unless you really want to) (and linked list (as a stack, say) can be implemented without them) (and there's an awesome book about learning Rust by doing so!)
agile sundial
RustPython š©
wide harness
is this channel occupied
mint jewel
Topical channels are free to use whenever, it is possible to have multiple conversations at the same time
undone mauve
so linked lists are just
data LinkedList a = Empty | Cons a (LinkedList a)
```right? so say i wanted to do that in python. i can do
```py
class LinkedList:
def __init__(self, data, next=None):
self.data = data
self.next = next
def head(self):
return self.data
def tail(self):
return self.next
```or whatever, but what i'm confused about is that that is basically just how would i represent the empty list?? i wanna represent the empty list >:(an empty list is a bit difficult with just a node class
undone mauve
...right which is why i'm asking how to do it lmfao
i know why it is difficult
what are you suggesting
?
bruh
:/
vocal gorge
Have data have a default value of None?
vocal gorge
You can't really do it the right way because Python doesn't have enums with nontrivial variants.
like enums in Rust or Haskell's... everything.
undone mauve
well i was going to have a node class and a separate list class but someone said that was wrong
vocal gorge
so you can't have a "nothing or a list" object, hmm
although, well, I guess you can always do
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
def append(self,data):
data = Node(data)
if not self.length:
self.head = self.tail = data
else:
self.tail.next = data
self.tail = data
self.length += 1
class Node:
def __init__(self,data):
self.data = data
self.next = None1
sorry, was doing something. what reptile said
lean dome
well i was going to have a node class and a separate list class but _someone_ sa...
It's definitely not wrong; it's the canonical way to implement a generic linked list.
lean dome
for special purpose lists where you can know for certain they'll never be empty, it's pretty common to get away with only having the Node class. In cases where you need the ability to represent emptiness - including the stdlib implementation of a linked list in every language I can think of - there's a LinkedList class that holds references to Node classes.
though glib does it with only the Node class: https://github.com/GNOME/glib/blob/master/glib/gslist.h#L37-L43
They do that by:
Each element in the list contains a piece of data, together with a pointer which links to the next element in the list.
There is no function to create a GSList. NULL is considered to be the empty list so you simply set a GSList* to NULL.
old rover
class Node:
def ___init__(self, data, next=None):
self.data = data
self.next = next
node1 = Node("3")
why is Node being underlined in red?
I need an actual linked list if I want to insert stuff into it with this function
def listInsert(linkedList, aNode):
aNode.next = linkedList.head()
if linkedList.head != None:
linkedList.head.prev = aNode
linkedList.head = aNode
aNode.prev = None
bc this takes a linkedList
grizzled schooner
@old rover you have 3 underscores before init lol
old rover
oh
dry crow
was about to say that
grizzled schooner
what error are you getting?
old rover
it was bc the node was under the class
the indentation of the node should be out of the class
brisk saddle
__method__ are called "Dunder Methods."
they basically allow for you to overload your class.
basically integrating your class with Python's standard functions like len and math and bitwise operators (and more) with custom behavior.
lean dome
why is Node being underlined in red?
Because it's indented too far.
lean dome
it was bc the node was under the class
ah, yeah, you spotted it.
jovial tartan
why is the best case for quicksort when the list is partitioned in half every time? Wouldn't any partition location for an already-sorted list be the same? If one sublist is 3/4 and the other is 1/4 we're still traversing the same length in the partition procedure as when both sublists are 1/2, right?
agile sundial
technically, as long as the list is being partitioned by a constant fraction, e.g. 1/9, you will still get best case performance
the reason is exactly as you said
jovial tartan
huh, ok that makes sense. So best case is always when you're picking a constant pivot point on an already-sorted list?
austere sparrow
why is the best case for quicksort when the list is partitioned in half every ti...
If you partition as 1 : n - 1, you're going to make O(n) steps, each of them going over O(n) elements.
which leads to O(n^2) performance
jovial tartan
that's worst case tho
austere sparrow
yes.
in half will look like the left, not in half -- like the right
if you drag the right case to the extreme, you move towards the N^2 case
jovial tartan
ohhhh yeah because it's maximizing the number of recursive calls made to N
jovial tartan
yeah that looks like expected i think
austere sparrow
And this is a bit better:
jovial tartan
what's the pivot for that one
austere sparrow
algorithm is the same -- the pivot is the first element
ruby owl
Hello can someone help me
jovial tartan
heavy cloak
can someone explain why the rest of my string is declared as variables
click on it its way to small to read
nvm
i got it
nvm i didnt
help
jovial tartan
algorithm is the same -- the pivot is the first element
wait so when determining big O of quicksort, are we assuming it's presorted? Or not?
if it's already sorted then the last element in the array will be worst case but not necessarily if the array is permuted
austere sparrow
wait so when determining big O of quicksort, are we assuming it's presorted? Or ...
'big O' depends on the context. The actual mathematical notaiton will not be O, it would be o, O and theta, but nobody really cares. We just discuss the average case and the worst case.
The average case is useful to approximate the throughput, and the worst case is useful when e.g. figuring out how an attacker can leverage a weakness of the algorithm to bring the system down
heavy cloak
can someone help with this
jovial tartan
so then growth rate is based on a permuted input because that's what the random case would be?
jovial tartan
The throughput??
google says it'sthe amount of material or items passing through a system or process.
austere sparrow
The throughput??
yeah, how many... things you can do per a unit of time
Well, it's not directly related to algorithms.
old rover
ok
jovial tartan
my professor has asked me how the growth rate of quicksort changes based on what the pivot is but didn't specify if it's permuted or sorted
in that situation should I just give the best, average, and worst case for each pivot?
austere sparrow
If you select a random pivot or a pivot at a fixed point, you're going to get the same average and worst case.
but e.g. selecting a random pivot point will make it harder to forge a worst case
there are algorithms to select the pivot point to improve performance
jovial tartan
wouldn't worst case be O(N^2) when the array is permuted and there's a fixed pivot?
austere sparrow
well, the worst case is still there
( O(n^2) )
but choosing pivot with e.g. choosing a median element as the pivot might improve performance on real-world data
but it doesn't change the complexity AFAIK
old rover
I think Iām learning selection sort next
itās in the next chapter of grokking algorithms
median tundra
need code
input:
[
{
list: [1,2,3,4]
},
{
list: [1,2,3]
},
{
list: [1,2,3,4, 5]
},
{
list: [1,2,3,4,5,6,7]
},
{
list: [1,2,3]
},
]
output:
[1,2,3]
trim fiber
need code
input:
```
[
{
list: [1,2,3,4]
},
{
list: [1,2,3]
},...
What?
What it should do?
median tundra
for example this input above data and i need all match like 1,2,3 then it should be output [1,2,3]
trim fiber
And what did you do? What is the problem?
median tundra
And what did you do? What is the problem?
i have no idea how to do it
trim fiber
for example this input above data and i need all match like 1,2,3 then it should...
Match the biggest subset of each array?
median tundra
please check #āhelp-coffee
median tundra
Match the biggest subset of each array?
like example?
trim fiber
like example?
It provides same result but I don't know is that a valid algorithm, you are asking about that
median tundra
#āhelp-coffee helped me anyway thank you
azure gazelle
Hello, I assume this would go here, I am trying to run this code:py for guild_id in bot_info['Prefixes']: if bot_info['Prefixes'][guild_id] == "itsb-": bot_info['Prefixes'].pop(guild_id) write_json("bot info", bot_info) But it gives me this as a error:```for guild_id in bot_info['Prefixes']:
RuntimeError: dictionary changed size during iteration
How would I go about fixing?found a temp fix (or perm):```py
test = []
for guild_id in bot_info['Prefixes']:
if bot_info['Prefixes'][guild_id] == "itsb-":
test.append(guild_id)
for guild_id in test:
bot_info['Prefixes'].pop(guild_id)
write_json("bot info", bot_info)
How about this
bot_info['Prefixes'] = {key: value for key, value in bot_info['Prefixes'].items() if key != "itsb-"}
I just realized that I don't need to do this xD
but thanks
inland iron
how do you make functions accept multiple arguments?
old rover
how do you make functions accept multiple arguments?
you can have a function accept as many arguments as you want
it's just how many paramaters you put in the parentheses.
inland iron
so like, def pogfunction(pog, poggers, gamer):?
inland iron
and when you call the function you can do something like ```py
print(pogfunction(input("REEE"), input("GG"), input("pOG")))
because the arguments are just variables that are assigned when the function is called, right?
old rover
well
agile sundial
yes, basically
inland iron
cause im trying to make a function that prints stairs with a specific user inputed character and size
so like, ```py
def makeStairs(size, character, mirror):
size = int(input("Please enter the size of the stairs: "))
character = str(input("Please input a character: "))
mirror = input("Do you want the stairs to be mirrored? Y/N" )
print(makeStairs(input("Please enter the size of the stairs: "), input("Please input a character: "), input("Do you want the stairs to be mirrored? Y/N" )))
def printList(aList):
print(aList)
return aList
print(printList([5,3]))
but the issue is my function call iS HUGE
inland iron
Yep
inland iron
and character is a string, and the mirror choice is a true false boolean
agile sundial
you define the variables twice, they're already defined when you pass them in as apguments
old rover
so you don't need input
inland iron
Yeah, im just not sure which way to do it cause defining them within the function looks cleaner
agile sundial
that removes the purpose of using a function
inland iron
yeah, good point
So, how do i assign the user input to the function arguments without making a mess?
inland iron
Cause this is a garbage fire: ```py
print(makeStairs(input("Please enter the size of the stairs: "), input("Please input a character: "), input("Do you want the stairs to be mirrored? Y/N" )))
have you tried testing the function or is that what you're struggling on?
agile sundial
you can always do something like
a = input()
b = input()
c = input()
func(a, b, c)
yeah good point
Thats actually what i tried ```py
print('Welcome to the StairCaser 8000!')
stairSize = input("Please enter the size of the stairs: ")
stairChar = input("Please input a character: ")
isMirror = input("Do you want the stairs to be mirrored? Y/N" )
def makeStairs(size, character, mirror):
print("placeholder")
print(makeStairs(stairSize, stairChar, isMirror))
Wait, holup
agile sundial
wdym "actual inputs"
inland iron
So, something along these lines (of code)? ```py
print('Welcome to the StairCaser 8000!')
stairSize = int(input("Please enter the size of the stairs: "))
stairChar = str(input("Please input a character: "))
isMirror = bool(input("Do you want the stairs to be mirrored? Y/N" ))
def makeStairs(size, character, mirror):
print("placeholder")
print(makeStairs(stairSize, stairChar, isMirror))
print(makeStairs(5,"a",True)
hm
old rover
idk if character is a single character or
inland iron
yeah it is
old rover
ok
agile sundial
So, something along these lines (of code)? ```py
print('Welcome to the StairCase...
input always returns a string, so isMirror will be True if the user inputs anything
old rover
are you new to Python?
inland iron
This is for an assignment btw, i took some notes as to what the program is supposed to do
inland iron
are you new to Python?
I specify that pretty much every time
yeah i am
I have moderate to limited knowledge
ive been using python for about a month
3 weeks total
old rover
good stuff
well this being an assignment kinda changes things bc I can't just give you code
inland iron
Yeah ik
I come here for guidance, not answers
Cause I usually learn from trial and error but its way too slow of a proccess
old rover
no I get that
that's good
keep doing that
this is the perfect community to help guide you
idk if you read it yet but I would read Automate the Boring Stuff w Python
inland iron
Okay, will do. anyways, where were we
Here are my notes on the program requirements:
Creates a staircase given a size, character, and mirroring (i.e. left or right).
INPUT 1 (size) is the size of the staircase.
INPUT 2 (character) is the character to render the staircase from.
INPUT 3 (mirror) is a Boolean indicating if the staircase should be mirrored.
RETURNS a multiline string containing the staircase.
def makeStairs(size, character, mirror):
For example, if you call the function with makeStairs(5, '*', False) the return string will be...
**
If you call the function with makeStairs(4, '%', True) the return string will be...
%
%%
%%%
%%%%
agile sundial
if you're familiar with the functiosn in the book, you can easily create such a function
old rover
I'm kind of sad that it took me an entire day to understand 5 lines of psuedocode
inland iron
took me a week just to fully understand just the basic python operators
old rover
what's a sentinel?
why does that even matter?
dummy object that allows you to simplify boundary conditions??
what does that even mean?
vocal gorge
precisely what it says - compare the snippets they provide for insertion without and with sentinels
agile sundial
so it's simpler
agile sundial
yeah, pretty myuch
old rover
would it be a good idea to make a github repo and upload this stuff
so I can look back on it later as a study tool?
bc most of the linked list implementations are either wrong or very very long
agile sundial
upload what stuff
old rover
like code snippets of the linked list implementation
old rover
ok sounds good
ok so I get that first line if the node before it is equal to nothing
but then what is x.prev.next?
agile sundial
(Recall that our attribute notation can cascade, so that L.head.prev denotes the prev attribute of the object that L.head points to.)
onyx umbra
hello
agile sundial
so that L.head.prev denotes the prev attribute of the object that L.head points to.
old rover
ELI5
agile sundial
so imagine first, L.head
old rover
ok
agile sundial
then, the prev attribute of L.head
old rover
it goes backwards to the other node?
agile sundial
L.head.prev
old rover
I read somewhere that doubly linked lists have an advantage over singly linked lists bc you can go backwards in nodes
agile sundial
yes, that's correct
old rover
oh ok
agile sundial
they also require a bit more space, but that's a non-issue
old rover
so does .prev not exist as an attribute for a singly linked list?
agile sundial
it does not
old rover
that actually makes sense
I feel like I'm learning now
so uh why does CLRS only show the implementation of a double linked list? why not a single linked list?
bc if you know that then you can do the single linked list too
spring jasper
Its not an implementation, its pseudocode
onyx umbra
because its not for every case
old rover
ok whatever
onyx umbra
u need to try for every case
agile sundial
bc if you know that then you can do the single linked list too
that's exactly the reason, it only needs to show one
agile sundial
different how?
old rover
can you go backwards in nodes in a circular linked list?
old rover
right
onyx umbra
yes but u need to be carefull not to run into an infinite loop
old rover
oh ok
I apologize for asking all these questions lmao
must be overwhelming to answer
agile sundial
no worries lol, it's letting me review
onyx umbra
lol why apologise
old rover
I just need to understand the methods not memorize them
I've seen some people on tik tok who are like oh yeah just memorize them haha no big deal
you know I actually understand the search method now
onyx umbra
tik tok? for coding? huh
old rover
not yet but I can explain the pseudocode when I look at it
we're getting there
understanding the psuedocode in CLRS is like half the battle
spring jasper
Its something but as Feynman said, if you cant create something you don't understand it yet
agile sundial
yeah, exactly
agile sundial
the value of the node
agile sundial
depends what you mean by worth
spring jasper
Yes?
old rover
I mean you understand how it works you can implement it anywhere
agile sundial
definitely not, then
old rover
it's not worth it?
onyx umbra
if u r in college, then my suggestion is to understand them
agile sundial
absolutely not
there is literally no reason to learn data structures with the intent to implement them in your code
old rover
but I need them for interviews
agile sundial
it has already been done for you, and much better than you can possibly hope to acheive
old rover
have to play the interview game
onyx umbra
but I need them for interviews
exactly
u need them for interviews more than anything else
old rover
I really should read more carefully
it says in CLRS that for the rest of this section we're using a doubly linked list
agile sundial
yes, reading is important
old rover
I wish he used bold text for that
agile sundial
ĀÆ_(ć)_/ĀÆ
old rover
this is just how scientific papers write ig
wrong place
bc it's in the wrong place
you can ask questions tho
if you have any
what does that second line mean?
onyx umbra
it moves x forward if x's key is not k
agile sundial
what second line
onyx umbra
it checks this untill it finds k or the list ends
old rover
what second line
while x != None and x.key != k
is that while x !=None so it goes until the end?
agile sundial
keep looping as long as there are more nodes and we haven't found the one we're looking for
onyx umbra
is that while x !=None so it goes until the end?
yes, if u dont check that then it will throw an error because "None" does not have any key
old rover
yes, if u dont check that then it will throw an error because "None" does not ha...
oh ok
so a node includes a pointer and a key?
well in python it's references
and the key contains like a number or a string?
old rover
ok
old rover
the key is a reference to some object
does it really matter if I used the sentinel version of deleting, looking up, and adding stuff to a linked list?
I can screenshot that part of the textbook if it helps
it's just shorter code
agile sundial
not really? they're basically the same, but easier
vocal gorge
I mean
old rover
yeah I'm going for the easy option then
vocal gorge
it depends on whether you have sentinels lol
old rover
how do you know if you have a sentinel
agile sundial
did you add them
old rover
no I don't even know what a sentinel looks like
agile sundial
then you don't have a sentinel
old rover
so you can't use the sentinel functions if there aren't any
ok
can you use the normal functions if you have sentinels?
def listDelete(linkedList, aNode):
if aNode.prev = None:
aNode.prev.next = aNode.next
else:
linkedList.head = aNode.next
if x.next != None:
aNode.next.prev = aNode
why is none being underlined in red
that's the pseudocode
also I would use elif not if
agile sundial
!comparison
halcyon plankBOT
old rover
oh nice catch
it should be !=
ok so
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
node1 = Node("3")
node2 = Node("7")
node3 = Node("10")
node4 = Node("77")
node1.next = node2
node2.next = node3
node3.next = node4
does this even count as a linked list?
this is the customary way of making one but I don't know how to actually call it
mint jewel
that is a linked list indeed
old rover
ok so for this function
def listSearch(linkedList, key):
headLL = linkedList.head
while headLL!= None and headLL.key != key:
headLL = headLL.next
return headLL
print(listSearch("what do I pass in", 5))
well, the way that function is written it expects another object which stores the first node in a head attribute
old rover
I can't just pass an entire linked list in?
node1.next = node2
node2.next = node3
node3.next = node4
I get this is what it creates the linked list
mint jewel
essentially, the issue is that there are two things you can conventionally call a linked list
old rover
a node
mint jewel
one is the very functional definition where a linked list is essentially a 2 element tuple, or some empty value (used in haskell and lisp)
another is the definition clrs seems to use, where there is a linked list, which stores the top node in a head attribute
the function you have requires the second type
mint jewel
headLL = linkedList.head would raise an attribute error
and also, you don't have keys on your nodes
old rover
this is what CLRS says
they use the term key
where can I see all the attributes of a linked list?
like .prev, .head
mint jewel
well, they are mostly defined as needed, there may be a comprehensive list in the book somehwere
old rover
I just looked at the python doc
are the linked lists in that link the same ones they're talking about in CLRS?
mint jewel
seems to be so
old rover
holy shit
mint jewel
though it uses first instead of head
old rover
then I have been wasting my time
let me try looking at the doc and figuring stuff out
maybe CLRS isn't the best tool
vocal gorge
I wonder if it might be a good idea to stop reading anything and try implementing a linked list based on only a description of what methods it should have and a general notion of the structure (a chain of nodes, each of them holding an element and a reference to the next node (if it exists))
old rover
is that sarcasm?
vocal gorge
Because all of these attributes aren't needed "just because" - the reference to the tail is needed for adding elements to the end to be O(1), for example. Basically, I'm feeling like you'd understand what they are all for better by trying to implementing the list and seeing that there's no way without them
vocal gorge
is that sarcasm?
not at all, no
old rover
do you think it's valid if I just use the python module for linked lists?
I mean it's not like they're gonna shut off the module during the interview
mint jewel
that is not a standard module
vocal gorge
that'd kinda defeat the entire purpose
mint jewel
that is an external dependency
vocal gorge
though what module are you talking about, collections.deque? Because list is some third-party lib.
old rover
it's in the docs so I assumed it was a module
vocal gorge
it's not in the docs
onyx umbra
point of interview is to test your DSA skills not python
agile sundial
there's no linked list module
vocal gorge
it's just a site that looks similarly and has python in the name, but it's not docs.python.org š
old rover
nvm then
agile sundial
and yeah, if they asked you to implement a data structure, i'm sure they would not let you import a module
old rover
ok
vocal gorge
more importantly, weren't you borrowing code from the internet for the last day or so? It doesn't seem like that worked out, so I don't see how importing an entire module would help you understand LLs.
old rover
ok I get the point
hey @mint jewel you were right it does raise an attribute error
but how do I even fix that?
AttributeError: 'Node' object has no attribute 'head'
brisk saddle
greetings friends.
brisk saddle
^ that should be the List
your Node should have a next and or previous node if you want to make it a Doubly Linked List.
old rover
I guess that's my question
def listSearch(linkedList, key):
headLL = linkedList.head
while headLL!= None and headLL.key != key:
headLL = headLL.next
return headLL
when I call this function
how do I pass in the linked list?
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
node1 = Node("3")
node2 = Node("7")
node3 = Node("10")
node4 = Node("77")
node1.next = node2
node2.next = node3
node3.next = node4
it is done automatically if this is a method inside a class.
old rover
the second snippet of code is how I created the linked list
onyx umbra
linked list is not an object but it is a link of nodes, so u pass head node directly
old rover
isn't the head node here node1?
brisk saddle
@onyx umbra it can be held inside a Class, though.
onyx umbra
isn't the head node here node1?
yes
onyx umbra
<@!561539904262242305> it can be held inside a Class, though.
yes ofc, but for him its easier that way
old rover
ok but if I pass in node1 it's an attribute error
onyx umbra
yea then u dont need node1.head beacuse node1 is head
spring jasper
headLL = linkedList.head get rid of this
old rover
`headLL = linkedList.head` get rid of this
done
brisk saddle
class Node():
def __init__(self, value):
self.value = value
self.next_node = None
class LinkedList():
length = 0
head = None
tail = None
def __init__(self, *values):
# Load up all Nodes from the *values tuple by
# shifting the tail field as you add new Nodes.
this is the general outline i guess.
vocal gorge
linked list is not an object but it is a link of nodes, so u pass head node dire...
you can't append to the end of a chain of nodes in O(1) (that needs a reference to the tail), nor do any operations that change the list's head. So that's quite an underpowered way to do it, which would allow to implement, uhh... nothing efficient, I think, you could implement a stack with O(n) insertion, which is pretty yikes
old rover
am confused
brisk saddle
@vocal gorge if you do an insert at 0 that can change the head if you new nodes after it.
or does an insert operation insert it after?
vocal gorge
<@!266216750876459008> if you do an insert at ``0`` that can change the head if ...
Yeah, but then you'd need your head to be a fake-node that doesn't actually store any data.
onyx umbra
you can't append to the end of a chain of nodes in O(1) (that needs a reference ...
uh i know all that, i was just trying to make it simple for him
vocal gorge
then you could implement a proper stack.
brisk saddle
old rover
I'm still hella confused
mariosis said to delete headLL = linkedList.head
so now everything's red
spring jasper
change the function param too
old rover
ok to what
spring jasper
def listSearch(headNode, key):
while headNode!= None and headNode.key != key:
headNode = headNode.next
return headNode
like that
brisk saddle
CLRS?
brisk saddle
spring jasper
CLRS is fine, it wouldnt be called a bible if it wasnt
onyx umbra
CLRS is not beginners, no offence
old rover
CLRS is not beginners, no offence
ok? you can delay ds/algos as much as you want
onyx umbra
you should start with something simpler
old rover
there's only one way through it
spring jasper
i said it from the very beginning, its not a learning book, its a reference
old rover
I use Grokking
brisk saddle
oh it is a reference?
old rover
but Grokking has no implementation of a linked list
brisk saddle
that would explain a thing or two.
old rover
oh it is a reference?
yeah you're not supposed to read it cover to cover
but I referenced it bc Grokking doesn't show an actual implementation
brisk saddle
@old rover maybe you should look at a place that is intended to teach you how it works.
vocal gorge
that actually makes more sense than the textbook
isn't that exactly like CLRS's?
old rover
<@!567030124306759710> maybe you should look at a place that is intended to teac...
I have searched all over
old rover
isn't that exactly like CLRS's?
attribute error
brisk saddle
not the biggest fan of GeeksforGeeks, i usually read Wikipedia pages, but you can use this if you wish.
onyx umbra
i like geekforgeeks
brisk saddle
i have problems putting my pride aside and looking at Psuedocode or implementations people have written.
but! does not matter.
@old rover i can show you some more places if you wish.
old rover
<@!567030124306759710> i can show you some more places if you wish.
I'm trying to find an implementation in python
brisk saddle
one moment. i might have one laying around if you really wanna look at it..
old rover
hang on geek for geeks may be good
brisk saddle
nope, i only got these three.
but Queues might as well just be Linked Lists where you only have operations on the front and back.
brisk saddle
so maybe looking at my Queue implementation would lead you in the right direction.
brisk saddle
alright, cool.
old rover
I'll be back w more questions
spring jasper
g4g does this tho
llist = LinkedList()
llist.head = Node(1)
second = Node(2)
third = Node(3)
llist.head.next = second; # Link first node with second
second.next = third;
which is frankly disgusting
oblique panther
geeks 4 geeks usually has awful Python code
spring jasper
yea i was kinda disappointed in them when i was doing my DS work
its not hard to write some decent python code, why do they do this
oblique panther
actually, what I did for my ADS class was re-write the awful g4g code
and that helped me learn how they worked
onyx umbra
its people writing and posting there
spring jasper
i looked at their java examples and translated that to python, with improvements
agile sundial
š
oblique panther
@old rover are there other programming languages that you know how to read (even if you can't write in them)? I think I agree that the textbook you've been using is very... formal
and I don't fully understand the notation they use myself.
agile sundial
seriously though, i'd recommend you stop looking for implementations of what you want online, and simply producing your own
it seems many of the problems you're facing stem from inadequate examples you're getting online
old rover
<@!567030124306759710> are there other programming languages that you know how t...
javascript
but not really
oblique panther
So let's turn this into a three-step process
- understand what a linked list is and how they use linkable nodes to store data. what is the relationship between a "linked list" and the general concept of having ordered data? and what is the difference between a node, an index, and an element?
- implement a few basic linked list operations. you might start with only appending new elements and accessing existing elements via their index. that will give you a sense for how node linking works
- describe the runtime complexities for the operations that you've implemented
does that sound more digestible?
old rover
ok
oblique panther
also, you will see people talk about singly linked lists, and doubly linked ones. focus on singly linked
old rover
CLRS only has stuff for doubly linked lists
oblique panther
alright, maybe put that book down for now
you'll get to a point where that book makes more sense to you
old rover
I think I'll use Grokking for now
I was making good progress w it for a while
it's more ELI5 content which I think is helpful
oblique panther
I have a few minutes to help you with the first of the three steps I mentioned
brisk saddle
Double Circularly Linked List gang.
oblique panther
earlier I saw that you asked how to turn a linked list into a list. what did you mean by this?
brisk saddle
probably like, an actual Python List.
onyx umbra
an array
oblique panther
I want daspecito to answer.
brisk saddle
if so, if he makes the Linked List iterable, he can just do list(*my_linked_list)
old rover
earlier I saw that you asked how to turn a linked list into a list. what did you...
someone said that you can write a function to turn a list into a linked list
oblique panther
someone said that you can write a function to turn a list into a linked list
so you're referring specifically to Python lists?
old rover
so you're referring specifically to Python lists?
yes
oblique panther
you can actually make linked lists that behave almost exactly the same as regular python lists
old rover
interesting
oblique panther
however an important distinction to make
brisk saddle
it will still take a worst case of O(n) time for indexing.
oblique panther
this is true
there's the external behavior of a data type, and then there's its implementation
Python lists are implemented as C arrays
brisk saddle
yeah, functionally, you can make them behave basically the same.
oh that is not what you meant.
oblique panther
but they could change them to be implemented internally as linked lists. and that would decrease their efficiency, but they would have the same behavior.
brisk saddle
yeah.
oblique panther
@old rover does that make sense?
brisk saddle
Dynamic Array gang š
old rover
<@!567030124306759710> does that make sense?
yes
oblique panther
yes
so if you want to make a linked list that has append and index methods (where index looks up an element by its index), you need to define two classes, and one of those classes needs at least three methods. do you know which two classes and which three methods?
old rover
so if you want to make a linked list that has `append` and `index` methods (wher...
you need a node class and a linked list class
oblique panther
and the three methods?
brisk saddle
wait, did you mean fields?
oblique panther
No, I was asking about methods
old rover
hmmm
brisk saddle
@old rover an attribute or field is just data that is stored in an object.
oblique panther
for one of the classes
old rover
you'd need a method to put stuff in front of the head
a method to put stuff behind the tail
and a method to insert behind any given node
oblique panther
you'd need a method to put stuff in front of the head
for now, focus on putting stuff at the end. and do a singly linked list (which means no tail or prev)
old rover
oh ok
brisk saddle
class MyClass():
x = 5
n = MyClass()
print(n.x) #=> 5
x is an attribute / field of the class.
pretty sure "field" and "attribute" are interchangable.
oblique panther
which three linked list methods would you need to implement to get the basic behaviors I described earlier?
oblique panther
```python
class MyClass():
x = 5
n = MyClass()
print(n.x) #=> 5
```
``x`` i...
are you aware that x will now be a class attribute rather than an instance one?
brisk saddle
that would explain my problem with my Tree implementation earlier..
i did not know that.
old rover
I actually don't know the linked list methods then
oblique panther
that would explain my problem with my Tree implementation earlier..
variables defined in the class-level scope belong to the whole class.
brisk saddle
they were all inserting into the same child_nodes list because i did this:
class Node():
children = []
ah, alright.
oblique panther
they were all inserting into the same ``child_nodes`` list because i did this:
`...
that would explain it, yes. Also, just so you know, you don't need () after the name of the class unless you put something in them
oblique panther
I actually don't know the linked list methods then
you will need to have append, index and __init__ methods
oblique panther
That's fine. you can come back to this another time.
oblique panther
honestly it is just preference. does PEP8 say against it? š¤Ø
not sure
old rover
got it
vocal gorge
I personally don't like saying that attributes "are stored in the object", because that makes me think of C or Rust structs whose fields, like, actually determine how the object is laid out in memory. They actually contain their fields, in a very literal way. In Python, attributes are pretty much just names bound to objects. Just like you can have a global variable some_var, you can have a class each instance of which has an attribute some_var, accessible as my_instance.some_var. This is, generally, just a name, and can refer to anything. There's generally no guarantee, say, that the object this name refers to doesn't have any other references (and so no guarantee that the object my_instance.some_var points to will be collected when the instance goes out of scope - maybe there's tons of other references to it).
vocal gorge
```python
class MyClass():
x = 5
n = MyClass()
print(n.x) #=> 5
```
``x`` i...
that's responding to this, pretty much^
(This is all pointless pedantry, but that's, like, my middle name š )
agile sundial
ConfusedPointlessPedantryReptile
stuck forum
I personally don't like saying that attributes "are stored in the object", becau...
That's the nature of Python's dynamic nature, everything is basically a pointer. When you are calling var.name, name could literally refer to anything. You could call it in one line and rebound to something else completely in the next. I think in practice people stay sane don't do strange things so it's not really a problem.
Note that there are ways to enforce types and consistency like numpy arrays are forced to a specific type for memory and speed reasons.
vocal gorge
yeah, basically
stuck forum
ConfusedPointlessPedantryReptile
While it seems like being a pain in the ass to point out that everything is an object sometimes it does matter like space. If you have something like a point class, you do pay for that overhead and that gets really bad if you have a lot them. You get around this with slots or using tuples.
vocal gorge
heh, now that I think of it, Python floats are 24 bytes due to the overhead of being a Python object (only of of them being the actual float64 data). A Node defined like:
class Node:
def __init(self, val, next = None):
self.val = val
self.next = next
is 48 bytes.
onyx root
@vocal gorge it's hard to measure memory footprint in Python. Node() is 48 bytes, but Node().__dict__ is another 104 bytes
stuck forum
You got to pay for that abstraction somehow. That's why people use C++. It's (supposed to be) more clear about what costs in abstraction and what doesn't.
vocal gorge
Line # Mem usage Increment Line Contents
================================================
5 49.7 MiB 49.7 MiB def func():
6 49.7 MiB 0.0 MiB n = 100000
7 49.7 MiB 0.0 MiB head = Node(0)
8 49.7 MiB 0.0 MiB tail = head
9 68.4 MiB 0.0 MiB for i in range(1,n+1):
10 68.4 MiB 0.0 MiB tail.next = Node(i)
11 68.4 MiB 0.0 MiB tail = tail.next
12 68.4 MiB 0.0 MiB return head
looks like 187 bytes per Node with an int inside.
stuck forum
Although, there are languages like Julia where they promise Python like ease of use but with static compiling for speed. I used it and they basically do that by making everything a generic. Also speed and memory is not straight forward at all. You really can't just say that Python is always slower when you have things like numpy.
onyx root
You got to pay for that abstraction somehow. That's why people use C++. It's (su...
I think some people use C++ because they think it's more "serious", or because they think Python is "just a scripting language."
agile sundial
@vocal gorge what aer you using to profile there?
vocal gorge
<@!266216750876459008> what aer you using to profile there?
https://pypi.org/project/memory-profiler/, used as a Jupyter extension.
# Cell 1
%load_ext memory_profiler
# Cell 2
%%file mprun_demo.py
class Node:
def __init__(self, val, next = None):
self.val = val
self.next = next
def func():
n = 300000
head = Node(0.0)
tail = head
for i in range(1,n+1):
tail.next = Node(i/n)
tail = tail.next
return head
# Cell 3
from mprun_demo import func
%mprun -f func a = func()
Honestly, that's why I say (supposed to be). I feel like a lot of technology is picked like fashion and clothes. People can't possibly know everything about a language beforehand so they work with what other people told them about it.
onyx root
```py
Line # Mem usage Increment Line Contents
=========================...
You have rounding error, and int interning to deal with there, so 187 is just an approximation.
vocal gorge
You have rounding error, and int interning to deal with there, so 187 is just an...
yeah, I realised that and remeasured with floats, and got
5 49.9 MiB 49.9 MiB def func():
6 49.9 MiB 0.0 MiB n = 300000
7 49.9 MiB 0.0 MiB head = Node(0.0)
8 49.9 MiB 0.0 MiB tail = head
9 105.8 MiB 0.0 MiB for i in range(1,n+1):
10 105.8 MiB 0.0 MiB tail.next = Node(i/(n))
11 105.8 MiB 0.0 MiB tail = tail.next
12 105.8 MiB 0.0 MiB return head
which is again ~186.3 bytes per node
mint jewel
there is a fun book about linked lists in rust https://rust-unofficial.github.io/too-many-lists/, but it is quite involved and expects the reader to know what a linked list is
vocal gorge
anyway, 186 bytes per float is around 4.8 times higher than Python lists (I measured them at ~38.8 bytes per float), and of course 23 times higher than a numpy array can do
for comparison, an implementation in a compiled language can do "only" 2x, I believe - each node would be just a 64-bit float and a 64-bit pointer to the next element
mint jewel
tbh, linked lists are mainly useful on massive objects where the lack of preallocation helps
vocal gorge
not trying to throw dirt or anything, but I personally only recently realised this. It's easy to notice that Python is slower, but it also can use 4-5x the memory (due to overhead of storing small items in lists)
mint jewel
for most things, memory doesn't even register as a constraint
vocal gorge
tbh, linked lists are mainly useful on massive objects where the lack of preallo...
yeah, linked lists in general are only this painful when the data is small (and so the pointers you have to slap on it are comparable to the piece of data in question)
brisk saddle
Ordered Dictionary =D
Linked Lists or just straight up appending Nodes onto a regular array are good for that kind of thing.
or prepending them onto a regular array.
vocal gorge
I actually have no idea how Python's impl of that works
mint jewel
there is a talk on this
brisk saddle
Ordered Dict from the collections module?
mint jewel
regular dict is also ordered
brisk saddle
š¤Ø it is?
vocal gorge
no, I meant the 3.6+ dicts which are ordered in insertion order
agile sundial
ordered in a different way though
vocal gorge
unlike sets which still aren't for some reason
brisk saddle
how on earth do they pull off that but also have hashing?
mint jewel
brisk saddle
oh sick.
mint jewel
Raymond is quite competent at explaning things
brisk saddle
i mean yeah when i say "ordered dict" i think of insertion order, not in the way of like the data is ordered based off contents.
oh well.
i will watch the video, thank you Lak.
mint jewel
yeah, that is how python dicts work
vocal gorge
OrderedDicts are now far less useful, but they have some methods dicts don't
mint jewel
!e
print({7: 1, 6: 2, 8: 4, 9: 8, -2: 34, 'a': 32423})
@mint jewel :white_check_mark: Your eval job has completed with return code 0.
{7: 1, 6: 2, 8: 4, 9: 8, -2: 34, 'a': 32423}
see, it keeps the order
brisk saddle
ye
agile sundial
unlike sets which still aren't for some reason
the implementation isn't connected
brisk saddle
!e
print({1, 7, 2, 9, 5})
You are not allowed to use that command here. Please use the #bot-commands channel instead.
brisk saddle
old rover
if I had a linked list that was just 3 nodes
would I get to the last one by writing head.next.next?
brisk saddle
yup.
vocal gorge
hopefully you'd use a loop, but yeah
brisk saddle
but you should have a tail field.
vocal gorge
but you should have a ``tail`` field.
if they are doing an approach without a LinkedList class, that's not possible
mint jewel
depends on what you need the linked list to do
brisk saddle
it is not required but it makes initialization a bit quicker.
@vocal gorge yeah actually i forgot.
mint jewel
it is mostly needed for linked list backed queues
spring jasper
isnt the tail the rest of the list after the head
brisk saddle
i found the functional programmer.
mint jewel
not here.
brisk saddle
now that i think about it, you could just store the current last node during the initialization process.
mint jewel
the terminology used is head - first node, tail - last node. next - node after a node, datakey - value of a node
old rover
then what is key
mint jewel
key is something you search by
old rover
is data and key the same thing?
mint jewel
often
but not always
for example, you could be looking for a 26 year old student
so data would be the student, and key would be the age
brisk saddle
x = {
# key: value
"Daniel": 27,
"Amanda": 18,
"Jeremy": 23,
}
tbh, I still like cons car cdr caar cddr cadr cdar ... more than whatever CLRS is trying to be
vocal gorge
then what is key
key in the IntToAlg book is what lakmatiol called data here.
mint jewel
is it? I thought they had separate .data for the value .key for the search key
vocal gorge
it's just how they call the value. That's probably the weirdest choice of notation here, IMO.
mint jewel
because the code g4g gives you is an abomination and should be purged with extreme prejudice from the face of the internet for ever and ever
vocal gorge
consider us successfully trolled
spring jasper
no it wont
old rover
we shall see
agile sundial
we have already seen for you, so you don't have to
old rover
but spending weeks on CLRS will get me nowhere
spring jasper
bruh didnt you start a couple days ago
old rover
yeah
spring jasper
steler also said some things about geeks4geeks too btw
agile sundial
that's about right
old rover
whatever
spring jasper
you dont have to be so dismissive with people trying to help you
old rover
Iām not even gonna respond to that
stuck forum
because the code g4g gives you is an abomination and should be purged with extre...
I agree. The code quality of g4g makes my eyes bleed. I go there to get a rough idea of things. I feel bad for people who copy and paste that stuff.
I didn't learn data structures from CLRS so it's not like you need that textbook. I read some parts of it and I think it's great. But I learn data structures the most just by doing them and messing with them in Python or C++.
For all the crap that leetcode gets, it does make you use them.
mint jewel
ye, I find that is the case with most code trying to show off an algorithm on the internet. I generally just transcribe the pseudocode, generally doesn't take too long, especially with the half english wikipedia syntax
stuck forum
I like the half english syntax of wikipedia because you can't complain about code quality with it. But some pages in CS wikipedia are confusing as hell.
old rover
I generally understand psuedocode
mint jewel
yeah, my main issue with leetcode is that it isn't about being smart (though there are such problems, like adding linked lists of digits), and more about knowing which data structures and algorithms exist and using those. A lot of the problems I got stuck on were using some magic algorithm the creator won an award for.
old rover
like the TAs at my college only gave me psuedocode bc it was against college policy to give code
I just donāt get why I donāt understand CLRSās psuedocode
austere sparrow
because the code g4g gives you is an abomination and should be purged with extre...
it do be like that sometimes
even w3schools is better
mint jewel
procedure LIST_SEARCH(List L, key K):
current_head = head of L
while current_head is not NIL and key of current_head is not K do
current_head = next node of current_head
return current_head
``` is imo much better than the weirdness in clrshey, I copied some very important css from there 
austere sparrow
```pascal
procedure LIST_SEARCH(List L, key K):
current_head = head of L
...
what language is that?
mint jewel
pseudocode
austere sparrow
ah
mint jewel
I don't think any language uses of for attribute access
spring jasper
what bothers me most about w3s is they overdo their SEO and get like top 5 results
mint jewel
that would be weird
to be fair, they do define the . operator in the book
also, they pretend to be related to w3
which are much more important, and have asked them to rename
mint jewel
it would be more like calling a python tutorial website PSFTutors
oblique panther
he said it's trash
to be clear, my point is that g4g's Python code is not idiomatic.
I don't really like the pseudocode in CLRS, either. I've actually considered putting my repository of Python alogs/data structs on github, but I don't have time to make sure they're something I want to present to the public.
frail vine
oblique panther
<@!253696366952316929> dude when you do that please tell me
did you implement the three methods I mentioned earlier?
old rover
Havenāt found the time busy shopping at Costco w my mom
Iāll try by the end of today
oblique panther
see how many free samples you can get š“
old rover
I saw this github repo using python and it had semi colons
it looked more like java than python
my point is that some GitHub repos w code snippets arenāt that amazing
brisk saddle
i mean, semi-colons are not necessary..
but it is not like it makes the Python code bad.
agile sundial
it shows that the person writing it is not familiar with python
and it indicates that you're gonna find worse things
shell osprey
Hey. Anyone know something about pathfinding library ? I just started using it and i got to the problem about returning empty array of path. Like i have 2 nodes to left to get to target but it just returing empty array of path.
def Move(self,target=()):
print(self.pos)
grid = Grid(matrix=self.world)
try:
start = grid.node(int(self.pos[0]/10),int(self.pos[1]/10))
end = grid.node(int(target.pos[0]/10),int(target.pos[1]/10))
finder = AStarFinder(diagonal_movement=DiagonalMovement.never)
path, runs = finder.find_path(start, end, grid)
print(path)
if path is not None and len(path) > 1:
self.pos = (path[1][0]*10,path[1][1]*10)
print(self.pos)
except IndexError as e:
print(e)
valid_choices = [(i,j) for i, x in enumerate(self.world) for j, y in enumerate(x) if not y]
self.pos = random.choice(valid_choices)
while self.world[self.pos[0]][self.pos[1]] != 0:
valid_choices = [(i,j) for i, x in enumerate(self.world) for j, y in enumerate(x) if not y]
self.pos = random.choice(valid_choices)
its like catch in other programming languages š
old rover
it's to handle errors right?
shell osprey
yeah
old rover
stupid question but what's the point of using that instead of just fixing the code once you hit an error?
shell osprey
First i need to fix that library with A*. Bcs that IndexError is getting from that path. While its empty
dapper sapphire
That is one of the ways of fixing an error.
Suppose, we wanted to fetch data of students who have graduated.
so if a student has graduated there will be a graduation date. But if a student has not graduated there might not be a year_graduated property because the person designing the api thought that would be better api design, so you could do something like
try:
year_graduated = response["yeard_graduated"]
except:
year_graduated = "N/A" # or whatever you wanted
I personally dont know a better way of handling this.
Yeah, I also learned this pretty late in programming. But pretty powerful.
old rover
well I will def try to do it in my code
spring jasper
For dictionaries specifically theres dict.get
dapper sapphire
If you dont do that then the program will throw an error in cli
old rover
For dictionaries specifically theres dict.get
dict.get gets the value for a key right?
spring jasper
Yes and if the key doesnt exist it returns none or another default value you give it
Instead of throwing errors all over the place
shell osprey
im feeling ignorated š
dapper sapphire
Never worked with path finder
old rover
I'm just working on data structures/algos for the first time
pretty much a noob w all of this stuff
fringe spear
Btw, I'm mathematician, but I'm interested in learn programming, all aspects, so if someone would like to learn math, and if you're interested to teach me programming, please DM me
agile sundial
stupid question but what's the point of using that instead of just fixing the co...
some errors are expected, and some aren't your fault. you want your program to be able to handle those situations gracefully
old rover
# 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
are they doing self.head = None bc they're prepending stuff to the linked list?
I'm just curious
# This function is in LinkedList class
# Function to insert a new node at the beginning
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
this is the next function if it helps
oblique panther
@old rover remember to put your documentation comments as triple-quoted strings under the line that starts them
# don't do it like this
class Thing:
...
class Thing:
"""Do it like this"""
...
oh so don't put # Node class before the actual implementation of the class?
I never heard that before but I'll remember to do that from now on
oblique panther
oh so don't put # Node class before the actual implementation of the class?
Nope, in Python you put the comments that officially describe a class or function/method as a string instead of a comment
and it has to be the first line of that thing
as shown in my example
The docstring actually gets saved
old rover
very interesting
oblique panther
!e
def my_func():
"""This function just returns None"""
return None
print(my_func.__doc__)
@oblique panther :white_check_mark: Your eval job has completed with return code 0.
This function just returns None
oh wow
oblique panther
You'll probably see people from g4g putting the doc comments as actual comments above the function or class
and we hate them for it
agile sundial
pythondocstrings
old rover
class Node:
"""Node class"""
def __init__(self,data):
self.data = data #Assign data
self.next = None #Next is null
oh should I change the other two comments too?
is a doc string only the ones with triple quotes?
agile sundial
tbh, #Assign data, is probably one of the most useless comments i've seen
agile sundial
self.data = data tells you "assign data" well enough
agile sundial
did you write the code?
old rover
no I gave up
this is a geeks 4 geeks implementation
i'll write the code myself when I actually know what it does
so can you explain why self.next = None?
agile sundial
there's no next node yet
old rover
bc it's not actually a linked list yet?
agile sundial
well arguably a single node is a linked list
but, there's no next node yet
so self.next = None
old rover
does scope apply to classes?
can I say that these functions are in the scope of the linked List class?
agile sundial
you can just say they're in the class
old rover
yeah that works too
# This function is in LinkedList class
# Function to insert a new node at the beginning
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
what is "self" here?
why are they even using self as a paramater name?
is self a linked list?
agile sundial
well it says "This function is in LinkedList class"
old rover
so does that mean self is a linked list?
agile sundial
yes
agile sundial
self is the convention
the assumption is that you know what class you're programming in
old rover
I thought you only used self with def __ init__
guess I'm wrong
I still think LL would be a better name than self
but whatever
agile sundial
self is passed to all instance methods
compact bloom
im learning about queues rn and for python you dont have to learn about how if you get to the end of an array you have to circle round and implement elements from the 0 index again
because array sizes automatically get revalued and dont have to be predefined in python right?
agile sundial
if you're unfamiliar with basic oop concepts, you probably should learn those before dsa, since they are much more important. i'm not saying you can't, but there are better things to learn
old rover
it's just a question dude
agile sundial
instead of self?
it doesn't matter what you call it, as long as it's there
agile sundial
im learning about queues rn and for python you dont have to learn about how if y...
yeah, you don't have to, but if you're just using a list then popping from the front may be a tad inefficient
old rover
you literally just need to know classes to implement data structures
I can learn OOP as I go
compact bloom
@old rover I wld defo watch a intermediate maybe pro syntax video
Get ur syntax down first
@agile sundial yeah only for other languages that donāt have lists predefined
agile sundial
hm? wdym by predefined
old rover
<@567030124306759710> I wld defo watch a intermediate maybe pro syntax video
I've watched multiple
hey at least geeks 4 geeks uses pascal case for class names
undone mauve
hm? wdym by predefined
predefined can generally be taken to mean "an inherent feature of the language, or a feature which is defined in the stdlib"
agile sundial
gotcha
compact bloom
yeah sorry i didnt say
undone mauve
what is "self" here?
class Thing:
def __init__(self):
self.val = 0
def thingy(self):
print(self.val)
self.val += 1
``````py
thing = Thing()
# this:
thing.thingy()
# is the same as this:
Thing.thingy(thing)
mayhaps it would be more helpful if they weren't all thing
old rover
I'll look at some more videos later
lean dome
self is the instance on which an instance method is operating
old rover
my eyes are kind of tired now
lean dome
it's passed implicitly as the first argument to an instance method.
old rover
def push(self, new_data):
given inst = Class(), inst.meth(a, b) calls Class.meth(inst, a, b)
old rover
I just said that linked list or some other paramter name would be better
undone mauve
class SomeClass:
def __init__(self):
self.val = 0
def some_method(self):
print(self.val)
self.val += 1
``````py
my_obj = SomeClass()
# this:
my_obj.some_method()
# is the same as this:
SomeClass.some_method(my_obj)
but self is customary ig
lean dome
the parameter referring to the instance the method is called on is idiomatically always called self. Technically you can call it something else, but that will confuse everyone who reads your code.
undone mauve
yes
old rover
maybe it would be helpful to add a comment on what self actually is
compact bloom
when people say like n-1 element
inside of an array
is that referring to the last index
of the array
grizzled schooner
shouldnāt it be clear what self is if you know youāre within a linked list class?
old rover
idk dude I only have a quarter of a semester of OOP experience + reading doc + watching some videos
compact bloom
i heard oop is super easy from what my friends have taught me
you just need to find the right videos
and content
old rover
I will eventually
lean dome
maybe it would be helpful to add a comment on what self actually is
self always means exactly the same thing: the instance on which the method is acting.
commenting that every place it occurs would be redundant, since it always means the same thing.
old rover
ok
I did OOP in Scala I never did it in Python
and we never used the term self there so this is new to me
but now that I got a solid explanation I think I got it now
lean dome
in Scala it's called this instead of self, and it doesn't show up in the argument list like self does in Python.
many other languages call it this; self is pretty unique to Python.
agile sundial
i know swift uses self, but that's the only one i can think of
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
#make this node the head
self.head = newNode
```what's up with that last line?
if you already have designated that node as the head
why do you need that last line?
lean dome
the first line creates a brand new node. The second line makes it so that the node after the brand new node is the old first node. The last line makes it so that the brand new node is the new first node.
the new node isn't even in the list until that last line runs.
dapper sapphire
So I was trying to figure out if python list or [] is a linked list. But it's a dynamic array, which means we can grow and shrink the size of the list. But it has methods similar to a Linked List.
lean dome
So I was trying to figure out if python `list` or `[]` is a linked list. But it'...
A common operation on a doubly linked list is inserting a new element at the front of the list. A Python list doesn't have that. A Python Collections.deque has appendleft, but a Python list doesn't, because it can't be implemented efficiently on a dynamic array.
old rover
A python list is not a linked list
lean dome
A deque is a linked list, though - well, a linked list of fixed size blocks. Which is why appendleft can be implemented efficiently on it.
old rover
Donāt you have to write a whole function to insert a node to become the head of a linked list?
itās just 3 lines of code
lean dome
someone has to write a new function to add a new element to the end of a dynamic array, too
it's just that for list and collections.deque, those functions are part of the standard library
old rover
also is the time complexity for inserting a node at the front of the linked list the same as the time complexity for inserting a node at the end of a linked list?
or are they both O(1)?
lean dome
depends on if it's a singly or doubly linked list
old rover
ok what about singly
lean dome
well - that depends on the implementation. If you keep a reference to the tail of the list, you can append a new node after it in O(1). If you don't, you need to walk the entire list to find the tail (which is an O(n) operation) before you can add a new node after it.
keeping a reference to both the head and tail of the list is a common optimization for a singly linked list, but not a requirement.
lean dome
you could do it that way - or, if you have a List class in addition to the Node class, you can make the List store references to two different nodes - the first and the last.
dapper sapphire
Wondering if someone could comment on this implementation of pop:
def _pop(self, index):
current = self.head
previous = None
while(index):
previous = current
current = current.next
index = index - 1
popped_element = current.data
if(previous == None):
self.head = current.next
else:
previous.next = current.next
return(popped_element)
def pop(self, index = None):
if(index != None):
return (self._pop(index))
current = self.head
previous = None
while(current.next != None):
previous = current
current = current.next
popped_element = current.data
if(previous == None):
self.head = None
else:
previous.next = current.next
return(popped_element)
I could have done it all in one 1 method, but that just makes the code a bit harder to follow.
stuck forum
Wondering if someone could comment on this implementation of pop:
```python
...
Wouldn't this be O(1) if you just stored the tail and the tail's previous instead of looping over things? Also I don't know why there are two methods.
fiery cosmos
yea maintaining a tail is legit for linked lists
lean dome
you have to loop in order to pop an arbitrary index, no matter what. To get the 5th item, you need to walk forward 4 from the head
fiery cosmos
i guess it depends how you view a pop (i usually think pop_back) but yea in the code this guy posted it functions more like a remove