Building a DoublyLinkedList in Python - - append method

Greetings Pythonistas!

I am learning how to write basic algorithms in Python but am taking an unusual approach. I am taking a Udemy course which teaches algorithms in JavaScript. What I do is watch the lesson where the instructor uses an interactive and dynamic visual aid to explain how the algorithm’s feature works, provides the pseudo code, asks the student to try writing the script themselves, and then provides the solution in JavaScript. I follow along and do all of that except for the last step, I use Python instead of JS. Based on the pseudo code, I write the algorithm in Python. Afterwards, I look at the solution in JS and make modifications as necessary.

Below is my attempt at building a Doubly Linked List (DLL). So far I’ve written the base Node constructor, the DLL constructor, the DLL append method, and the DLL string method. Below I have also included some testing in my Python REPL shell.

Having said all of that, my script doesn’t work as intended. When I instantiate a test list object and try to append integers one at a time, Python is only recording the most recent value. The list is not being extended by each value. The old value is just being overwritten by the new one in place. Any idea why? What kind of changes do I need to make so that when I call the append method, the list increases by the value being entered?

class Node:
    # Create a new node with the value passed to the function
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def append(self, value):
        # If the head property is null set the head and tail to be the newly created node
        newNode = Node(value)
        if self.length == 0:
            self.head = newNode
            self.tail = newNode
        # If not... 
        else:
            # Set the next property on the tail to be that node
            self.tail.next = newNode
            # Set the previous property on the newly created node to be the tail
            newNode.prev = self.tail
            # Set the tail to be the newly created node
            self.tail = newNode
        # Increment the length
        self.length = self.length + 1
        # Return the Doubly Linked List
        return self
    
    def __str__(self):
        current = self.head
        result = []
        while current:
            result.append(current.value)
            current = current.next
        return str(result)
$ python      
Python 3.11.6 (main, Nov 14 2023, 09:36:21) [GCC 13.2.1 20230801] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from script import Node,DoublyLinkedList
>>> DLL_obj = DoublyLinkedList().append(24)
>>> print(DLL_obj)
[24]
>>> DLL_obj = DoublyLinkedList().append(2)
>>> DLL_obj = DoublyLinkedList().append(256)
>>> print(DLL_obj)
[256]
>>> 

Looks correct. You just never append more than one value to each of your lists.

To be slightly more explicit, all of your lines look like the following:

 DLL_obj = DoublyLinkedList().append(24)

That is, they create a new DLL, and then append (in this case) “24”.

What you want is something like:

myDLL = DoubleLinkedList()
myDLL.append(24)
myDLL.append(27)

Now, you are appending to the same DLL each time.

4 Likes

Or like DoublyLinkedList().append(41).append(43).

Yikes! I can’t believe I missed that. I was just mishandling the way I was calling the method in my shell. Thanks for clarifying @defjaf.

In a class double linked list you do not use a length
Usually have the head simply be an instance of Node with self.value as None.
Or have class Head define next and prev then have class Node(Head) add value fields.

What you do is compare self.next to self.prev, if they are the same the list is empty.
Also when inserting you can insert at ANY node in the list and remove any node with needing to know where the head is.

All you have to do is update the .next and .prev links.

Node should have a remove() method that takes it out of the list.
Again it only needs to know itself and not where the head is.

For a bonus prize write a list validation method that uses finite memory to check an infinite list. (I had to be told the solution, did not solve it myself).

Howdy @barry-scott!

You are right that with doubly linked lists, recording or keeping track of the length or pointer positioning is not necessary. Not sure why my Udemy course instructor includes it. Anyways, I did my best to reformat and cleanup the script with the length and pointer positioning purged. When I call the script and append some values, now inside the string representation, the while loop is triggered infinitely. The shell output doesn’t work as well as before. Below is my script. What might you suggest I try next?

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        newNode = Node(value)
        self.head = newNode
        self.tail = newNode
        self.tail.next = newNode
        newNode.prev = self.tail
        self.tail = newNode
        return self
    
    def __str__(self):
        current = self.head
        result = []
        while current:
            result.append(current.value)
            current = current.next
        return str(result)

# Instantiation and testing
DLL_obj = DoublyLinkedList()
print(DLL_obj)
DLL_obj.append(7)
DLL_obj.append(12)
DLL_obj.append(22)
print(DLL_obj)
DLL_obj.append(11)
print(DLL_obj)
print(DLL_obj)

For what it is worth, here is the last known good working state with length and pointer positioning included:

class Node:
    # Create a new node with the value passed to the function
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def append(self, value):
        # If the head property is null set the head and tail to be the newly created node
        newNode = Node(value)
        if self.length == 0:
            self.head = newNode
            self.tail = newNode
        # If not... 
        else:
            # Set the next property on the tail to be that node
            self.tail.next = newNode
            # Set the previous property on the newly created node to be the tail
            newNode.prev = self.tail
            # Set the tail to be the newly created node
            self.tail = newNode
        # Increment the length
        self.length = self.length + 1
        # Return the Doubly Linked List
        return self
    
    def __str__(self):
        current = self.head
        result = []
        while current:
            result.append(current.value)
            current = current.next
        return str(result)

# Instantiation and testing
DLL_obj = DoublyLinkedList()
print(DLL_obj)
DLL_obj.append(7)
DLL_obj.append(12)
DLL_obj.append(22)
print(DLL_obj)
DLL_obj.append(11)
print(DLL_obj)
print(DLL_obj)

Let me share a version I coded up that shows some features of double-linked-lists.
(I had to look at my old implementation, I got my next.prev’s and prev.next’s comfused!)

You will see that I have insert() and remove() on the ListNode() itself.
Then I implemented append() and prepend() on the LIstHeader as that is what you had.
And last I show how to insert in to the middle of the list.

class Links:
    def __init__(self, is_header=False):
        if is_header:
            self.next = self
            self.prev = self
        else:
            # init to None to cause coding errors to traceback
            self.next = None
            self.prev = None

    def __repr__(self):
        return '<%s: self: 0x%x next: 0x%x prev: 0x%x>' % (self.__class__.__name__, id(self), id(self.next), id(self.prev))

    def insert(self, node):
        # insert this node into the queue
        self.next = node.next
        self.prev = node.next.prev
        node.next.prev = self
        node.next = self

    def remove(self):
        self.prev.next = self.next
        self.next.prev = self.prev

class ListNode(Links):
    def __init__(self, value):
        super().__init__()
        self.value = value

class ListHeader(Links):
    def __init__(self):
        super().__init__(is_header=True)

    def prepend(self, value):
        node = ListNode(value)
        node.insert(self)
        return node

    def append(self, value):
        node = ListNode(value)
        node.insert(self.prev)
        return node

    def __str__(self):
        current = self.next
        result = []
        while current != self:
            result.append(current.value)
            current = current.next

        return str(result)

# Instantiation and testing
dll_head = ListHeader()
print('Empty:', dll_head)
val_7 = dll_head.append(7)
print('append 7:', dll_head)
dll_head.append(12)
val_40 = dll_head.prepend(40)
print('append 12, prepend 40:', dll_head)
val_7.remove()
print('remove 7:', dll_head)

val_99 = ListNode(99)
val_99.insert(val_40)
print('insert 99 after 40:', dll_head)

Which outputs:

Empty: []
append 7: [7]
append 12, prepend 40: [40, 7, 12]
remove 7: [40, 12]
insert 99 after 40: [40, 99, 12]

My apologies for the delay in my reply. Nineteen days later and I am back!

Since last time I readded tracking of the length and pointer positions. There is actually a really good rationale for this that I learned as I re-watched some of the instructor’s course material on Udemy. It’s used for determining which half a potential linked list item is to ensure that when searching, performance is always average case (“Theta” in Big-O notation language) or better and never worst case (“Omicron”). For example if there is a doubly linked list with 1,000 items, if you know that a particular item is within 5 positions from the right side, it would be faster and more efficient to perform a floor division calculation first on the length of the list to find the middle and then once you know it’s position, strategically search from the right when performing a get or remove operation. Knowing to search from the right side in certain situations can be optimal. Recording length / index positioning only makes sense for doubly linked lists because seeking / searching can come from either side which isn’t possible in a singly linked list.

That is why I’ve re-added the length counter.

So I returned to my original script which includes length and position tracking. It worked wel just as beforel. But then I decided to rename my class method from append() to add_right() (and replacing all instances with one for the other accordingly) to help distinguish my method from Python’s native builtin append(). After this refactor, it seemed to break my method. I am not sure why. The traceback in my shell tells me I have an “AttributeError where ‘list’ object has no attribute ‘add_right’” when trying to execute the __str__ representation again. It was working before the method name change. I then compared my __str__ to Barry’s which is slightly different. I made some minor changes back and forth which didn’t seem to help. As I investigated this further, I tried commenting out my string repr and then created a break point and used my debugger to step through each list item addition. No dice. When I just run the script (without a debugger) with the string repr commented out, my print statement checks only show memory locations.

Therefore, my take away and main renewed inquiry for all of you is this: Based on my latest code snippet below, how might you people recommend I change my string repr to return the new list result as intended as before?

Feedback / hints / tips welcome.

It’s also worth mentioning that while this cheap Udemy course I am taking is not for school or a formal college credit, I would still very much prefer to preserve the mystery of figuring out as much as I can by myself. So instead of being provided with a complete solution (as @barry-scott did), here is the kind of support I’d prefer:

  • referrals to documentation around the web,
  • comments pointing out trivial mistakes,
  • nudges in new directions, as well as
  • general and specific guidance.

All I ask is not to be given full solutions. I glanced over your solution Barry but avoided reading every line because it would ruin my learning process. I will try to make this personal preference more clear up front when writing other forum threads and posts in the future going forward. Thank you.

One step at a time. Rather than completing every feature and possible method of a doubly linked list all at once, for now I am focusing on add_right() (a.k.a append() in Python a.k.a. push() in JavaScript). I am tracking all of my changes on a GitHub repo and working on Doubly Linked Lists on this particular Pull Request: Doubly Linked Lists branch by enoren5 · Pull Request #1 · enoren5/algos · GitHub
The reason why I am sharing this link to my PR is that the preamble / opening commentary shows a diagram as well as all 8 methods I intend on writing. It’s kind of like my agenda / itinerary. I am still on Step #1 add_right().

Here is my latest code snippet:

class Node:
  # Create a new node with the value passed to the function
  def __init__(self, value):
      self.value = value
      self.next = None
      self.prev = None


class DoublyLinkedList:
  def __init__(self):
      self.head = None
      self.tail = None
      self.length = 0


  def add_right(self, value):
      # If the head property is null set the head and tail to be the newly created node
      newNode = Node(value)
      if self.length == 0:
          self.head = newNode
          self.tail = newNode
      # If not...
      else:
          # Set the next property on the tail to be that node
          self.tail.next = newNode
          # Set the previous property on the newly created node to be the tail
          newNode.prev = self.tail
          # Set the tail to be the newly created node
          self.tail = newNode
      # Increment the length
      self.length = self.length + 1
      # Return the Doubly Linked List
      return self
 
  def __str__(self):
      current = self.head
      result = []
      while current != self:
          result.add_right(current.value)
          current = current.next
      return str(result)
 
# Instantiation and testing
DLL_obj = DoublyLinkedList()
print(DLL_obj)
DLL_obj.add_right(7)
DLL_obj.add_right(12)
DLL_obj.add_right(22)
print(DLL_obj)
DLL_obj.add_right(11)
print(DLL_obj)
print(DLL_obj)

Expected output:

$ python script3.py
[]
[7, 12, 22]
[7, 12, 22, 11]
[7, 12, 22, 11]

Actual output:

$python script3.py
Traceback (most recent call last):
  File "/home/gnull/dev/projects/python/2018-and-2020/algos/Doubly-Linked-Lists/script3.py", line 43, in <module>
    print(DLL_obj)
  File "/home/gnull/dev/projects/python/2018-and-2020/algos/Doubly-Linked-Lists/script3.py", line 37, in __str__
    result.add_right(current.value)
    ^^^^^^^^^^^^^^^^
AttributeError: 'list' object has no attribute 'add_right'

Well, yes, exactly as it says.

What should .add_right do, and how, given that the initial value for result is an empty list?

I assume you figured it out, but just in case, the problem lies right here, in the bit you changed:

Can you see why the while loop

would run indefinitely?

This is very good and I commend you for this, as that’s how you learn; Barry presumably shared his implementation in the good faith hope that you might learn by way of example, but unlike yourself far too many students cannot resist the temptation to simply copy code without truly understanding it, defeating the point of the exercise. Thus I greatly prefer the socratic pedagogy practiced by @kknechtel and others here, and typically discourage others (usually newer members here) from unintentionally subverting that by offering full solutions.

And just to be clear…result is a Python list , and your whole motivation for the change was

:wink:

1 Like

Double linked lists (DLL) are very powerful when you want to have O(1) removal from a list. Also it is often the case that you will know of an exiting node that is in the DLL and insert before or after it, again without needing to know about the head.

If you do not care about these use cases then a DLL is often not what you want to use.

Once you are doing the removal in O(1), or insert other then at the head, then maintaining the length is harder. To do a operation you need to know the node and the head, as opposed to only knowing the node.

Why did I provide a full implementation when as I have shown in other replies that I know your goal is to learn about these datastructures and algorithmed by implementing yourself?

I thought that you knew a lot about the problem space, but an implementation was still hard to arrive at. I pondered if more feedback on details would help or you where at the stage where viewing a working example would help your understanding. Sorry if I got this judgement wrong.

I learnt about DLL’s working on the VAX/VMS operating system kernel.
(On the VAX CPU DLL’s where supported by hardware instructions)
None of the OS DLLs had a length as far as I remember (it was a long time ago!).

Also of note is that Linux kernel does not use DLLs becuase its too hard to do lock-less insert and delete on a DLLs that is critical to multi-core performance.

Thank you to all who have replied so far! I am back with some more inquiries.

The message AttributeError: 'list' object has no attribute 'add_right' would usually indicate that the user is trying to use the method add_right() on an object which is not a list. That is what that traceback means. I get that much.

Lists in Python do not have an add_right() method. The right tool is the builin append() method. However for my purposes I am delibereately trying to re-write that builtin’s functionality for my DLL. In my case add_right() does indeed have a class method attribute. On the first pass of the __str__ repr, result is declared as an empty list. So that should work.

To add to that, in the following sceenshot, you can see the 2 scripts. The one on the left works perfectly. The second one breaks with the error discussed above. The only difference between the two is the name of the class method. Why does Python only protest the absence of a list in the second version and not the first?

To answer your questions, I intend .add_right() to emulate append(). I realize that requires a list. But the way my script was originally written, it worked perfectly. For example, when result is declared for the first time, it is declared as an empty list and calling it with append() still seemed to work. All I have done differently is refactored to a slightly different naming scheme. Even if result is an empty list, Python should still recognize the object as list inclde all it’s associated properties, even if it is empty. It’s just the initialization. Soon after items are being added. Not sure why it is still breaking.

The code snippet you refer to is not related to the problematic one I am working with. I apologize for the confusion I’ve caused here because I have experimented with different versions and made different attempts with drastically different approaches. The one you are referring to I scrapped a while ago. That script never reached a working state. It had it’s own issues which were unresolved so it might not be the best reference.

Below is the latest version I am working with. For the add_right() method, I indeed include newNode = Node(value) which I think is the right move. Here it is:

class Node:
    # Create a new node with the value passed to the function
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def add_right(self, value):
        # If the head property is null set the head and tail to be the newly created node
        newNode = Node(value)
        if self.length == 0:
            self.head = newNode
            self.tail = newNode
        # If not... 
        else:
            # Set the next property on the tail to be that node
            self.tail.next = newNode
            # Set the previous property on the newly created node to be the tail
            newNode.prev = self.tail
            # Set the tail to be the newly created node
            self.tail = newNode
        # Increment the length
        self.length = self.length + 1
        # Return the Doubly Linked List
        return self
    
    def __str__(self):
        current = self.head
        result = []
        while current:
            result.add_right(current.value)
            current = current.next
        return str(result)
    
# Instantiation and testing
DLL_obj = DoublyLinkedList()
print(DLL_obj)
DLL_obj.add_right(7)
DLL_obj.add_right(12)
DLL_obj.add_right(22)
print(DLL_obj)
DLL_obj.add_right(11)
print(DLL_obj)
print(DLL_obj)

Here is the traceback:

python script3.py                
[]
Traceback (most recent call last):
  File "/home/gnull/dev/projects/python/2018-and-2020/algos/Doubly-Linked-Lists/script3.py", line 47, in <module>
    print(DLL_obj)
  File "/home/gnull/dev/projects/python/2018-and-2020/algos/Doubly-Linked-Lists/script3.py", line 37, in __str__
    result.add_right(current.value)
    ^^^^^^^^^^^^^^^^
AttributeError: 'list' object has no attribute 'add_right'

Here is the output I am expecting - - and the correct output when add_right() was previously named .append():

[]
[7, 12, 22]
[7, 12, 22, 11]
[7, 12, 22, 11]

result is assigned (there is no “declaration” in Python) an empty Python list - the built-in type. That’s what [] creates. It is not an empty instance of your class. Therefore, it does not have an add_right method.

And, of course, using an empty instance of the class would not help, because you would then just be effectively copying self and then trying to call str on that result, which would recurse without limit.

The point of your algorithm for __str__ is to “convert” an instance of your list into a plain Python list in order to use its already-existing __str__ logic. To do this, you need to use the interface provided by that type. In particular, the code should use result.append, regardless of what you call the method in your own class. The name for that method is irrelevant, because it’s not the method that will be used.

It doesn’t protest “the absence of a list”. It protests the absence of a method named add_right on a list. In the working code, it does not protest, because the built-in Python list does have a method called append, which your code uses. It does not use the method named append in your own class, because you called the method on a Python list, not on an instance of your class.

Please read it more closely - in particular, the “given that the initial value for result is an empty list?” part.

Because result is an empty list, and not an instance of your class, .add_right should not be expected to do anything except raise the error that it raises. Because the built-in type does not have that method.

It’s the other way around.

Yes. That is exactly why calling add_right on it doesn’t work. Because add_right is not such an “associated property”. It belongs to the class you’re implementing - not to the built-in list.

This is irrelevant to the issue. The problem is not the code in add_right. The problem is that you try to use add_right for something that isn’t an instance of your class.

1 Like

Hi @kknechtel. Thank you for your reply. Based on your feedback and insight, I am taking this away: The traceback refers to the fact that my instances do indeed have list type objects, it’s just that the list assigned in the __str__ doesn’t come naturally with my custom add_right(). At that location in my script, I need to use result.append(). When I make that change to __str__, my script works again.

See here:

    def __str__(self):
        if self.length == 0:
            return "Doubly Linked List: []"
        
        current = self.head
        result = []
        while current:
            result.append(current.value)
            current = current.next
        return str(result)

The output shows as expected. That is progress.

I set out to re-write my __str__ method without append() like so:

    def __str__(self):
        if self.length == 0:
            return "Doubly Linked List: []"

        current = self.head
        elements = []
        while current:
            elements += [str(current.value)]
            current = current.next

        return "Doubly Linked List: [" + " <-> ".join(elements) + "]"

This also works.

With my DoublyLinkedList established with my first add_right() method along with a working __str__ repr that I am satisfied with, my next endeavor is to write a custom method to remove an item from the end of a doubly linked list - - the same operation which when performed on a regular Python list is called pop(). If I require further support with that task, I will be sure to create a separate thread.

Thank you again Karl and to all who have provided insight and feedback so far. :slightly_smiling_face:

To emphasize the key point here—the instances of your DoublyLinkedList class are exactly that, instances of an arbitrary custom class, which are entirely distinct from the built-in Python list class and its instances, and have nothing in common from a language syntax, data model or semantics point of view. Your confusion arises due to conflating the two, when the reality is they are as about distinct as any two objects can be in Python; they are not the same type, they do not inherit from one another, and they don’t even share any structural similarity, e.g. duck-typed methods.

Therefore, once this key point is understood, it should then become clear that expecting the built-in Python list to come with the add_right() method of DoublyLinkedList, or vice versa, is analogous to defining a new Spam class with some method eggs() and expecting the builtin int class to have that method.

2 Likes

I now see and understand that the .append() method I was previously calling in my __str__ repr is not the same thing as the custom .add_right() method I was trying to design.

Even though I think in my latest iteration in my working __str__ repr I still have a list - - since I am no longer confused with .append(), I proceeded to complete the construction of my doubly linked list. Really the biggest challenge was wrestling with my __str__ repr.

Special thanks to everyone all who helped clarify my doubts and answer my questions.

Here is my end product:

class Node:
    # Create a new node with the value passed to the function
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0


    def add_right(self, value):
        # If the head property is null set the head and tail to be the newly created node
        newNode = Node(value)
        if self.length == 0:
            self.head = newNode
            self.tail = newNode
        # If not... 
        else:
            # Set the next property on the tail to be that node
            self.tail.next = newNode
            # Set the previous property on the newly created node to be the tail
            newNode.prev = self.tail
            # Set the tail to be the newly created node
            self.tail = newNode
        # Increment the length
        self.length = self.length + 1
        # Return the Doubly Linked List
        return self
    
    
    def pop_right(self):
        # If there is no head, return undefined
        if self.head == None:
            return "Undefined"
        else:
            # Store the current tail in a variable to return later
            temp = self.tail
            # If the length is 1, set the head and tail to be null
            if self.length == 1:
                self.head == None
                self.tail == None
            # Update the tail to be the previous Node
            self.tail = self.tail.prev 
            # Set the newTail's next to null
            self.tail.next = None
        # Decrement the length    
        self.length = self.length - 1
        # Return the value removed
        return temp


    def add_left(self, value):
        # If the head property is null set the head and tail to be the newly created node
        newNode = Node(value) # If the length is 0
        if self.length == 0:
            self.head = newNode # Set the head to be the new node
            self.tail = newNode # Set the tail to be the new node
        else: # Oherwise... 
            # Set the prev property on the head of the list to be the new node
            self.head.prev = newNode
            # Set the next property on the new node to be the head property
            newNode.next = self.head
            # Update the head to be the new node
            self.head = newNode
        self.length = self.length + 1 # Increment the length
        return self


    def pop_left(self):
        # If length is 0, return undefined
        if self.length == 0:
            return "Undefined"
        else:
            # Store the current head property in a variable (we'll call it old head)
            old_head = self.head
            # If the length is one 
            if self.length == 1:
                # Set the head to be null 
                self.head == None
                # set the tail to be null
                self.tail == None
            # Update the head to be the next of the old head
            self.head = old_head.next
            # Set the head's prev property to null
            self.head.prev = None
            # Set the old head's next to null
            old_head.next = None
        # Decrement the length
        self.length = self.length - 1
        # Return old head
        return old_head

    def cust_get(self, item_location):
        
        if item_location < 0 or item_location >= self.length:
            return None
        
        if item_location <= (self.length // 2):
            print("Traversing from start")
            count = 0
            current = self.head
            while count != item_location:
                current = current.next
                count = count + 1
            return current
        
        elif item_location >= (self.length // 2):
            print("Traversing backwards from end")
            count = self.length -1
            current = self.tail
            while count != item_location:
                current = current.prev
                count = count - 1            
            return current


    def cust_set(self, item_location, new_value):
        found_node = self.cust_get(item_location)
        
        if found_node != None:
            found_node.value = new_value
            return True
        return False
        

    def cust_insert(self, item_location, new_value):
        if item_location < 0 or item_location > self.length:
           return None
        elif item_location == 0:
            return self.add_left(new_value)
        elif item_location == self.length:
           self.add_right(new_value)
           self.length += 1 
           # print(self.length)
           return self
        new_node = Node(new_value)
        before_node = self.cust_get(item_location-1)
        after_node = before_node.next
        before_node.next = new_node
        new_node.prev = before_node
        new_node.next = after_node
        after_node.prev = new_node
        self.length = self.length + 1
        return True
    

    def cust_remove(self, item_location):
        if item_location < 0: # or item_location > self.length:
           return None
        elif item_location == 0:
            return self.pop_left()
        elif item_location == (self.length-1):
           return self.pop_right()
        removed_node = self.cust_get(item_location)
        removed_node.prev.next = removed_node.next
        removed_node.next.prev = removed_node.prev
        removed_node.next = None
        removed_node.prev = None
        self.length = self.length - 1
        return removed_node
    
    def __str__(self):
        if self.length == 0:
            return "Empty DLL for intialization"

        current = self.head
        elements = []
        while current:
            elements += [str(current.value)]
            current = current.next

        return "Doubly Linked List: [" + " <-> ".join(elements) + "]"
      

# Instantiation and testing
    
DLL_obj = DoublyLinkedList()
print(DLL_obj)
DLL_obj.add_right(7)
DLL_obj.add_right(12)
DLL_obj.add_right(22)
print(DLL_obj)
DLL_obj.cust_insert(0,999)
print(DLL_obj)
DLL_obj.cust_insert(4,90099)
print(DLL_obj)
DLL_obj.cust_insert(2,"'Custom insert test'")
print(DLL_obj)
# DLL_obj.cust_remove(2)
print(DLL_obj.cust_remove(2))
print(DLL_obj)



'''
DLL_obj.add_right(11)
print(DLL_obj)
# DLL_obj.pop_right()
# DLL_obj.pop_right()
print(DLL_obj)
# DLL_obj.pop_left()
print(DLL_obj)
DLL_obj.add_left(496)
print(DLL_obj)
DLL_obj.add_left(777)
DLL_obj.add_left(66)
DLL_obj.add_left(93)
DLL_obj.add_right(89)
print(DLL_obj)
print(DLL_obj.cust_get(5))
print(DLL_obj)
DLL_obj.cust_set(0,18)
print(DLL_obj)

'''

Beware that having a __str__ or __repr__ that can return very large strings will be an issue in any performance sensitive code. If you have 10,000 entries in your DLL then your __str__ will be slow and return a huge string.

1 Like

If it gets called in that code, sure :wink: But performance-sensitive code wouldn’t have a good reason to be using a hand-rolled, native Python doubly-linked list anyway.

2 Likes

I’m also not sure why performance of __str__, of a toy class, of all things, would be such a concern here. Sure, it would be a large string, but it would be much smaller than the 10 000 Node objects floating around, and much faster to construct than them not to mention many other operations on the full DoublyLinkedList. And the relative behavior here is no different from the much higher performance built-in Python list, which would be used in any meaningful applications where performance mattered anyway.

In any case, I did a bit of benchmarking using the IPython %timeit magic to substantiate these claims, using your class from above (with print statements stripped out), and the following code:

def create_dll(n_items):
    dll_test = DoublyLinkedList()
    for idx in range(n_items):
        dll_test.add_right(idx)
    return dll_test

dll_short = create_dll(10)
dll_long = create_dll(10_000)

lst_short = list(range(10))
lst_long = list(range(10_000))

The following was run on Python 3.10 on an old Windows laptop (in Spyder):

%timeit create_dll(10)
22.8 µs ± 1.35 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

%timeit create_dll(10_000)
21.5 ms ± 2.02 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit list(range(10))
693 ns ± 17.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

%timeit list(range(10_000))
282 µs ± 18.9 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

%timeit str(dll_short)
7.56 µs ± 448 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

%timeit str(dll_long)
6.11 ms ± 361 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit str(lst_short)
2.08 µs ± 54.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

%timeit str(lst_long)
1.69 ms ± 40.5 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

To summarize, creating a DoublyLinkedList is over 30x slower than a list for 10 elements, or 75x slower for 10 000. However, calling str() on a DoublyLinkedList is only 3.6x slower than list for both, and around 4x faster than its creation (whereas for list, its 3x slower). Therefore, while DoublyLinkedList wouldn’t ever be considered for a performance-critical application, its relative performance of str() compared to other operations appears to be significantly better than list, and it isn’t that far behind the latter class.

Additionally, some small optimizations (e.g. elements.append(current.value) instead of elements += [str(current.value)], and if not self.length rather than if self.length == 0—to note, it should really instead have __len__ and __bool__ defined instead, so len(self) and if self work properly), improves performance by on the order of up to ≈10%, as well as simplifying the code.