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.

3 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.