Design Linked List - Leetcode 707 - Python

[@Javokh1r]

Creating extra dummy nodes is well-thought and makes the double linked list so easy to implement. Thanks a lot!

[@voctor1381]

Commenting as a surprise for myself in a few months during Leetcode season Happy Neetcoding everyone 👍

[@amlivinginhell]

what happened?

[@mannyw_]

💀

[@PerseRos285]

A small improvement is to implement a bidirectional search to perform the get function faster. Basically, based on the index, we decide if is faster to move forward or backward (from the head/tail to the index-th position). if index < self.size // 2: current = self.head.next for _ in range(index): current = current.next else: current = self.tail.prev for _ in range(self.size - index - 1): current = current.prev return current

[@mannyw_]

General idea behind the optimization is good, but this would fail if index is invalid

[@maryabuor2824]

This is very well explained, especially the illustrations. You've gained a new subscriber!

[@vijayvarshinilakshminaraya887]

The jump from ‘you can turn off your brain’ to ‘maybe you don’t have to turn off your brain too much’ had me😂😂😂😂😂😂😂

[@krateskim4169]

your consistency is awesome

[@LEGGOMYEGGO206]

man thanks for the breakdown i just started linked list's and I spent about a day trying to figure out how to solve this problem I would get down to like 2 edge cases that I couldn't solve, so thanks again for the vid

[@Ziad.Dev99]

Thanks a lot 👍 I think the main idea here is 'two dummy nodes', this makes me control the boundaries of linked list. this technique helps in many linked list problems.

[@lembueno894]

Nothing makes me more sad than after 2 hours of this trying to fix the 36th case, I give up and look this video up for a WAY more simpler and short solution. The count down loops would have helped :/

[@kartikgadagalli1008]

The doubly linked list is easy to implement it's the edge cases where a lot of errors happen. The dummy nodes really make it easy to implement a doubly linked list.

[@NikhilAsawadekar]

at 7:33, can we just assume that index is always going to be 0 if cur is not null and cur is not self.right? What't the need to check index == 0 in the while loop?

[@podilichaitanyaakhilkumar4911]

Explained well 👏👏. I am a regular follower of your channel. I have gone through your playlist, but I could only find a few hard problems and many easy and medium problems. Upload more leetcode hard problems. It will be beneficial for cracking Faang companies. Thank you.

[@Disusede]

At the moment of writing this, this solution fails on Leetcode. For it to pass correctly you have to set a right boundary to the while loop list traversal by adding a `node != self.right` condition. Otherwise if you go out of bounds the code will try to access a .next property on a None value and will fail.

[@Disusede]

So for example the while loop condition in the get method will be: while cur and index > 0 and cur != self.right:

[@AmitDeveloper-mg3kl]

For me all the TC passed . I did not change the code but it works fine@@Disusede

[@business_central]

Can anyone please tell me why in his last function: DeleteAtIndex only checked if curr != Self.right ? What about if the pointer is put on the left dummy node self.left ??

[@staceyonuora5329]

The pointer would never be on the self.left dummy node. This is because he started the current node from self.left.next and moved further right from there on.

[@pavanbandaru8180]

He doesnt want to delete the dummy node

[@manojrao9867]

Wonderfull.

[@vuejs1]

that index -- trick in neet

[@iftekharuddin]

💪

[@MrCCronyn]

This solution gives me a memory limit exceeded error. Does anyone know why?

[@raz_dva_]

There is no Memory Leak issue here - both Java and Python will immediately collect node to garbadge as far as it is not referenced from main program grapth.

[@ahmadmtera]

The dummy nodes lead to wasted space. Imagine a user of your LinkedList class wants to make an array of LinkedLists, wherein each LinkedList is a LinkedList as well. The outer array would mean that there's a O(2n) wasted RAM just for the dummy nodes. That wouldn't be a good design, and using such strategy across solutions as a lazy shortcut to make the code easier is the wrong methodology - one should utilize the resources a program uses to provide the best program to the end user, not to the developer's ease of use. PS I was able to build a Doubly Linked List with not much more LOC compared to the video and there's no wasted memory.

[@william.darrigo]

cries in binary

[@KevinDevZ]

Im early

[@noob-xv9yr]

class Node: def __init__(self,val): self.val=val self.next=None self.prev=None class MyLinkedList(object): def __init__(self): self.head=Node(0) self.tail=Node(0) self.head.next=self.tail self.tail.prev=self.head def get(self, index): """ :type index: int :rtype: int """ curr=self.head.next while curr!=self.tail and index>0: curr=curr.next index-=1 if curr and curr!=self.tail and index==0: return curr.val return -1 def addAtHead(self, val): """ :type val: int :rtype: None """ node=Node(val) self.head.next.prev=node self.head.next=node node.prev=self.head return self.head.next def addAtTail(self, val): """ :type val: int :rtype: None """ node=Node(val) self.tail.prev.next=node node.prev=self.tail.prev node.next=self.tail self.tail.prev=node return self.tail.prev def addAtIndex(self, index, val): """ :type index: int :type val: int :rtype: None """ node=Node(val) curr=self.head.next while curr!=self.tail and index>0: curr=curr.next index-=1 if curr!=self.tail and index==0 : curr.prev.next=node node.prev=curr.prev node.next=curr curr.prev=node return curr.prev else: return False def deleteAtIndex(self, index): """ :type index: int :rtype: None """ curr = self.head.next # Start from the first real node # Traverse the list until the correct index or end of the list while curr != self.tail and index > 0: curr = curr.next index -= 1 # Ensure curr is not the dummy tail and index is valid if curr != self.tail and curr != self.head and index == 0: prev_node = curr.prev next_node = curr.next # Ensure next_node is not None before accessing its prev attribute if next_node: prev_node.next = next_node next_node.prev = prev_node # Your MyLinkedList object will be instantiated and called as such: # obj = MyLinkedList() # param_1 = obj.get(index) # obj.addAtHead(val) # obj.addAtTail(val) # obj.addAtIndex(index,val) # obj.deleteAtIndex(index) this code works but if i remove the if next_node: from deletAtindex we get typnone object does not have pre somethig like error why are we getting this is it because the leetcode system is expecting without dummy nodes and trying to delete a dummy node in edge cases ???

[@pabloj1336]

Anyone else get AttributeError: 'NoneType' object has no attribute 'next' ^^^^^^^^^ prev.next = newNode Line 59 in addAtIndex (Solution.py) ^^^^^^^^^^^^^^^ result = obj.addAtIndex( Line 117 in __helper_select_method__ (Solution.py) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ret.append(__DriverSolution__().__helper_select_method__(method, params[index], obj)) Line 163 in _driver (Solution.py) _driver() Line 172 in (Solution.py) with this solution?