How to remove last node of a linked list (Python)

Question

The goal is to remove the last node of a linked list. (Python) The code that I have written only added to the list instead of taking the tail away. I'm not sure if the error is coming from this part here self.head.next.prev = None. I tried refining that part but another error would occurred. What I have posted is only small section of the code.

def remove_tail(self):
        if self.tail == self.head:
            self.head = None
            self.tail = None
        elif self.head is not None:
            self.head.next.prev = None
            self.tail = self.head.next

print("\n=========== PROBLEM 2 TESTS ===========")
ll.remove_tail()
print(ll) # linkedlist[5, 4, 3, 2, 2, 2, 1, 0]
ll.remove_tail()
print(ll) # linkedlist[5, 4, 3, 2, 2, 2, 1]

I reverse the names of head and tail to see of that was causing the issues.

elif self.head is not None:
            self.head.next.prev = None
            self.tail = self.head.next

Here is the updated code. Errors still occur when I run it.

def remove_tail(self):
    if self.tail == self.head:
     self.head = None
     self.tail = None
    if self.tail is not None:
     self.tail = self.tail.prev
     self.tail.next = None

self.head.next.prev = None This code assumes that there are only two nodes. Why would you assume that? — John Gordon
– John Gordon, Commented Feb 17, 2023 at 3:59
Oh! How can you make it assume that it has more than two nodes? — BRN
– BRN, Commented Feb 17, 2023 at 4:18

Samwise · Accepted Answer · 2023-02-17 02:42:16Z

1

Think about the structure of the list (assuming you have more than one element; your code already handles that special case):

head                 tail
+---+->+---+->+---+->+---+->None
| 1 |  | 2 |  | 3 |  | 4 |
+---+<-+---+<-+---+<-+---+

If you remove the last element, you're going to have:

head          tail 
+---+->+---+->+---+->None  
| 1 |  | 2 |  | 3 |
+---+<-+---+<-+---+

What needs to change in order for that to happen?

tail needs to be set to the second-to-last node (3, aka tail.prev)
the new tail's next pointer needs to be set to None (since the old tail, 4, is no longer part of the list)

So instead of:

self.head.next.prev = None
self.tail = self.head.next

you want:

self.tail = self.tail.prev
self.tail.next = None

answered Feb 17, 2023 at 2:42

Samwise

72.1k3 gold badges36 silver badges52 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

BRN Over a year ago

The example you have make sense. This error came up when I run the code. Attribute error: 'NoneType' object has no attribute 'next'

Shorn Over a year ago

You probably want to check that self.tail != self.head. The only way I can see that error occuring in the example is if self.tail.prev is None, and the only node where prev should be None is self.head. If self.tail == self.head then you probably want to do alternate processing, such as just removing the head like you already had in your code. You may also want to do an additional check to see if there is a head at all, and if there isn't just do nothing.

BRN Over a year ago

I guess you mean I need to remove elif self.tail is not None:.

Collectives™ on Stack Overflow

How to remove last node of a linked list (Python)

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related