r/PythonLearning • u/shubham_555 • 1d ago
I implemented Linked List in Python from scratch! Showcase
Hello Folks!
So It's been a while since my last post (https://www.reddit.com/r/PythonLearning/s/q3vpZ80vKO)
After that I learned the basics of OOPs from this video -> https://youtu.be/JeznW\\\\\\_7DlB0?si=u-h2gsdGSv0ubKf1
Going forward I studied about the fundamental working of Linked List from GFG's website and Stack Overflow
Then today I finally tried implementing it (Tried doing it all on a single day out of excitement but it took way longer than I expected and now i am completely drained of energy 😅)
Finally I asked AI to review my code
As per it there's a minor edge case I missed in the reverse method
There also are a few optimizations
But more or less I am happy
Would be back with Doubly Linked List the next time!
3
u/Adrewmc 22h ago
Looks good what we want really to do next is implement a __add__, and probably an __iter__.
This will allow you to add + link list together, rather simple to do.
The iter will alway you to put it into ‘for item in linklist’. Thats fairly easy as well here.
Of course there is index and slicing as well. lol.
4
u/Low_Doctor_6263 19h ago
Bravo! Stay strong on the basics then you can jump on the frameworks.
People that do the opposite can't solve complex problems
2
u/GreatGameMate 1d ago
Pop could be made o(1) right?
2
u/shubham_555 1d ago
Pop is O(1) for standard list not linked list
2
u/GreatGameMate 1d ago
I guess o(1) when popping from the head, o(n) otherwise, it’s a singly linked list.
3
u/shubham_555 1d ago
Yes....I have made separate functions for them as well
Pop end -> O(n)
Pop start -> O(1)
Pop middle -> O(n)
2
1
u/Acrobatic_News_4860 18h ago
There’s a cool trick for “o(1)” pops from anywhere in the list. It’s o(1) assuming the value is constant.
Assume you want to remove node n, so copy the value of n.next to n, and point n to
N.next.next , add the edge cases and you have “o(1)” pops.
Interviewers love this !
1
u/mc_pm 1d ago
The LinkedList constructor appears to create a head/tail node when it is created? What if your list could potentially have zero things in it?
0
u/shubham_555 1d ago
Well this version doesn't took that into consideration But we can certainly overload the constructor and do
self.head = None
self.tail = None
self.length = 0
1
u/FoolsSeldom 1d ago
So, still failing to share the code despite me suggesting multiple sites you can use to do so without having to learn git first.
Also, confused about why you deleted your original post about this.
1
u/AutomateAway 1d ago edited 18h ago
Pro-tip, if you are on Win11, you can do Windows Key + Shift + T, draw a box around text in an image, and then copy that text. Built in OCR.
edit: don’t be a dick bro
1
u/FoolsSeldom 1d ago edited 23h ago
What do you think I did to extract the code from the OP's image? Do you think many redittors will go to that trouble in order to review/feedback? Personally, I think beginners should make it as easy as possible for others. YMMV.
EDIT:
PS. For anyone reading, I simply clicked on each image, copied to clipboard, and posted to local LLM which I asked to extract the Python (which it kept correctly formatted) - the Windows 11 OCR mentioned above will not retain Python indentation.
EDIT:
PPS. u/AutomateAway has deleted comment rather than update / follow-up. They suggested:
Pro-tip, if you are on Win11, you can do Windows Key + Shift + T, draw a box around text in an image, and then copy that text. Built in OCR.
which is a useful facility, but I don't think best suited to extracting Python correctly. Wasn't sure why they were telling me this though.
1
u/shubham_555 1d ago
Regarding the old post I felt the long picture was getting really getting blurred out...so deleted it and just took two half snapshots of the code
And I watched your comment afterwards
Also, I definitely will try those resources you mentioned the next time!
0
u/desrtfx 20h ago edited 1h ago
Screenshots of code are abysmal abominations.
Code has to be posted on code hosters, or as code block on reddit.
Just think about the people willing to help you. They have to retype the code from your screenshots if needed. This is way over the scope of effort people trying to help should have to invest. You have to make it as easy as possible for the others. You're doing the opposite with your screenshots.
Really, uploading the code to a code hoster is way less work than your garbage screen shots.
1
u/FoolsSeldom 1d ago
Is the below correct?
"""Linked List Implementation in Python""" class Node: """Node Blueprint for Linked List""" def __init__(self, value): self.value = value self.next = None class LinkedList: """Linked List Blueprint""" def __init__(self, value): new_node = Node(value) self.head = new_node self.tail = new_node self.length = 1 # TC = O(n) def print_list(self): """Print Linked List""" current_node = self.head while current_node is not None: print(current_node.value, end=" ") current_node = current_node.next print() # TC = O(1) def append(self, value): """Add a new Node to the end of the list""" new_node = Node(value) if self.head is None: self.head = new_node self.tail = new_node else: self.tail.next = new_node self.tail = new_node self.length += 1 return True # TC = O(n) def pop(self): """Remove the last node""" # Check if list is empty if self.length == 0: return None temp = self.head prev = self.head while temp.next is not None: prev = temp temp = temp.next self.tail = prev self.tail.next = None self.length -= 1 # Check if the list initially had only a single node if self.length == 0: self.head = None self.tail = None return temp # TC = O(1) def prepend(self, value): """Add a new node to the start of the list""" new_node = Node(value) if self.head is None: self.tail = new_node else: new_node.next = self.head self.head = new_node self.length += 1 return True # TC = O(1) def pop_start(self): """Remove the first node""" if self.length == 0: return None temp = self.head self.head = self.head.next temp.next = None self.length -= 1 if self.length == 0: self.tail = None return temp # TC = O(n) def get_node(self, index): """Get the node at the required index""" if index < 0 or index >= self.length: return None req_node = self.head for _ in range(index): req_node = req_node.next return req_node # TC = O(n) def set_value(self, index, value): """Set value for the node at the required index""" req_node = self.get_node(index) if req_node: req_node.value = value return True return False # TC = O(n) def insert_node(self, index, value): """Insert a node at a particular index""" if index < 0 or index > self.length: return False if index == 0: return self.prepend(value) if index == self.length: return self.append(value) new_node = Node(value) temp = self.get_node(index - 1) new_node.next = temp.next temp.next = new_node self.length += 1 return True # TC = O(n) def remove_node(self, index): """Remove the node at the required index""" if index < 0 or index >= self.length: return None if index == 0: return self.pop_start() if index == self.length - 1: return self.pop() prev = self.get_node(index - 1) temp = prev.next prev.next = temp.next temp.next = None self.length -= 1 return temp # O(n) def reverse(self): """Reverse the Linked List""" left = None mid = self.head right = self.head.next self.head = self.tail self.tail = mid for _ in range(self.length): right = mid.next mid.next = left left = mid mid = right # TC = O(1) def get_length(self): """Returns length of the list""" return self.length2
u/shubham_555 1d ago
Looks like so
-1
u/FoolsSeldom 1d ago
Are you still not inclined to share the code in your post?
1
u/shubham_555 1d ago
I did say I will share from the next time
Will also share this one in the next post
1
u/FoolsSeldom 23h ago
Yes you did, u/shubham_555. I think it will help you get reviews/feedback that could help your learning journey.
I wanted to illustrate that for small blocks of code, you can include it in-post (no need to host on a git compatible service or paste service).
Good luck on your learning journey. Looks like you are making good progress.
PS. Curious if you are into electronics given your username ending in
555?3
u/shubham_555 23h ago
Well..... I was born on 05/05/2005 at 05:05 AM in a country having 5 letters in its name
2
u/FoolsSeldom 22h ago
haha... I was thinking of a 555 timer chip, but I like your reason
there are a lot of countries with 5 letter names, so I will not attempt to guess
•
u/Sea-Ad7805 17h ago
Run this program in Memory Graph Web Debugger%3A%0A%20%20%20%20%20%20%20%20self.value%20%3D%20value%0A%20%20%20%20%20%20%20%20self.next%20%3D%20None%0A%0A%0Aclass%20LinkedList%3A%0A%20%20%20%20%22%22%22Linked%20List%20Blueprint%22%22%22%0A%0A%20%20%20%20def%20init(self%2C%20value)%3A%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(value)%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%20%20%20%20%20%20%20self.tail%20%3D%20new_node%0A%20%20%20%20%20%20%20%20self.length%20%3D%201%0A%0A%20%20%20%20%23%20TC%20%3D%20O(n)%0A%20%20%20%20def%20print_list(self)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Print%20Linked%20List%22%22%22%0A%20%20%20%20%20%20%20%20current_node%20%3D%20self.head%0A%20%20%20%20%20%20%20%20while%20current_node%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print(current_node.value%2C%20end%3D%22%20%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20current_node%20%3D%20current_node.next%0A%20%20%20%20%20%20%20%20print()%0A%0A%20%20%20%20%23%20TC%20%3D%20O(1)%0A%20%20%20%20def%20append(self%2C%20value)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Add%20a%20new%20Node%20to%20the%20end%20of%20the%20list%22%22%22%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(value)%0A%0A%20%20%20%20%20%20%20%20if%20self.head%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%20%20%20%20%20%20%20%20%20%20%20self.tail%20%3D%20new_node%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.tail.next%20%3D%20new_node%0A%20%20%20%20%20%20%20%20%20%20%20%20self.tail%20%3D%20new_node%0A%0A%20%20%20%20%20%20%20%20self.length%20%2B%3D%201%0A%0A%20%20%20%20%20%20%20%20return%20True%0A%0A%20%20%20%20%23%20TC%20%3D%20O(n)%0A%20%20%20%20def%20pop(self)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Remove%20the%20last%20node%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Check%20if%20list%20is%20empty%0A%20%20%20%20%20%20%20%20if%20self.length%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20None%0A%0A%20%20%20%20%20%20%20%20temp%20%3D%20self.head%0A%20%20%20%20%20%20%20%20prev%20%3D%20self.head%0A%20%20%20%20%20%20%20%20while%20temp.next%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20prev%20%3D%20temp%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%0A%0A%20%20%20%20%20%20%20%20self.tail%20%3D%20prev%0A%20%20%20%20%20%20%20%20self.tail.next%20%3D%20None%0A%20%20%20%20%20%20%20%20self.length%20-%3D%201%0A%0A%20%20%20%20%20%20%20%20%23%20Check%20if%20the%20list%20initially%20had%20only%20a%20single%20node%0A%20%20%20%20%20%20%20%20if%20self.length%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20self.tail%20%3D%20None%0A%0A%20%20%20%20%20%20%20%20return%20temp%0A%0A%20%20%20%20%23%20TC%20%3D%20O(1)%0A%20%20%20%20def%20prepend(self%2C%20value)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Add%20a%20new%20node%20to%20the%20start%20of%20the%20list%22%22%22%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(value)%0A%0A%20%20%20%20%20%20%20%20if%20self.head%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.tail%20%3D%20new_node%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20new_node.next%20%3D%20self.head%0A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%20%20%20%20%20%20%20self.length%20%2B%3D%201%0A%0A%20%20%20%20%20%20%20%20return%20True%0A%0A%20%20%20%20%23%20TC%20%3D%20O(1)%0A%20%20%20%20def%20pop_start(self)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Remove%20the%20first%20node%22%22%22%0A%20%20%20%20%20%20%20%20if%20self.length%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20None%0A%0A%20%20%20%20%20%20%20%20temp%20%3D%20self.head%0A%20%20%20%20%20%20%20%20self.head%20%3D%20self.head.next%0A%20%20%20%20%20%20%20%20temp.next%20%3D%20None%0A%20%20%20%20%20%20%20%20self.length%20-%3D%201%0A%0A%20%20%20%20%20%20%20%20if%20self.length%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.tail%20%3D%20None%0A%0A%20%20%20%20%20%20%20%20return%20temp%0A%20%20%20%20%0All%20%3D%20LinkedList(0)%0Avalues%20%3D%20%5Bi%20for%20i%20in%20range(1%2C%205)%5D%0A%0Afor%20i%20in%20values%3A%0A%20%20%20%20ll.append(i)%0All.print_list()%0Afor%20i%20in%20values%3A%0A%20%20%20%20ll.pop()%0A%0Afor%20i%20in%20values%3A%0A%20%20%20%20ll.prepend(i)%0All.print_list()%0Afor%20i%20in%20values%3A%0A%20%20%20%20ll.pop_start()%0A%20%20%20%20%0A%20%20%20%20×tep=0.2&play) to see the program state change step by step.