FAQ: Doubly Linked Lists: Python - Review

Frequently Asked Questions Python FAQ
1

Community%20FAQs%20on%20Codecademy%20Exercises
Community%20FAQs%20on%20Codecademy%20Exercises1000×208 141 KB

This community-built FAQ covers the “Review” exercise from the lesson “Doubly Linked Lists: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Pass the Technical Interview with Python

FAQs on the exercise Review

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!
You can also find further discussion and get answers to your questions over in #get-help.

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head to #get-help and #community:tips-and-resources. If you are wanting feedback or inspiration for a project, check out #project.

Looking for motivation to keep learning? Join our wider discussions in #community

Learn more about how to use this guide.

Found a bug? Report it online, or post in #community:Codecademy-Bug-Reporting

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

2

remove a value by the tail method

class Node:
    def __init__(self, value, next_node=None, prev_node=None):
        self.value = value
        self.next_node = next_node
        self.prev_node = prev_node


    def set_next_node(self, next_node):
        self.next_node = next_node


    def get_next_node(self):
        return self.next_node


    def set_prev_node(self, prev_node):
        self.prev_node = prev_node


    def get_prev_node(self):
        return self.prev_node


    def get_value(self):
        return self.value


class DoublyLinkedList:
    def __init__(self):
        self.head_node = None
        self.tail_node = None


    def add_to_head(self, new_value):
        new_head = Node(new_value)
        current_head = self.head_node


        if current_head != None:
            current_head.set_prev_node(new_head)
            new_head.set_next_node(current_head)

        self.head_node = new_head

        if self.tail_node == None:
            self.tail_node = new_head


    def add_to_tail(self, new_value):
        new_tail = Node(new_value)
        current_tail = self.tail_node

        if current_tail != None:
            current_tail.set_next_node(new_tail)
            new_tail.set_prev_node(current_tail)

            self.tail_node = new_tail

        if self.head_node == None:
            self.head_node = new_tail


    def remove_head(self):
        removed_head = self.head_node

        if removed_head == None:
            return None

        self.head_node = removed_head.get_next_node()

        if self.head_node != None:
            self.head_node.set_prev_node(None)

        if removed_head == self.tail_node:
            self.remove_tail()

        return removed_head.get_value()


    def remove_tail(self):
        removed_tail = self.tail_node

        if removed_tail == None:
            return None

        self.tail_node = removed_tail.get_prev_node()

        if self.tail_node != None:
            self.tail_node.set_next_node(None)

        if removed_tail == self.head_node:
            self.remove_head()

        return removed_tail.get_value()


    def remove_by_value(self, value_to_remove):
        node_to_remove = None
        current_node = self.head_node

        while current_node != None:
            if current_node.get_value() == value_to_remove:
                node_to_remove = current_node
                break

            current_node = current_node.get_next_node()

        if node_to_remove == None:
            return None

        if node_to_remove == self.head_node:
            self.remove_head()
        elif node_to_remove == self.tail_node:
            self.remove_tail()
        else:
            next_node = node_to_remove.get_next_node()
            prev_node = node_to_remove.get_prev_node()
            next_node.set_prev_node(prev_node)
            prev_node.set_next_node(next_node)

        return node_to_remove


    def remove_by_value_reverse(self, value_to_remove):
        node_to_remove = None
        current_node = self.tail_node

        while current_node != None:

            if current_node.get_value() == value_to_remove:
                node_to_remove = current_node
                break

            current_node = current_node.get_prev_node()

        if node_to_remove == None:
            return None

        if node_to_remove == self.tail_node:
            self.remove_tail()
        elif node_to_remove == self.head_node:
            self.remove_head()
        else:
            next_node = node_to_remove.get_next_node()
            prev_node = node_to_remove.get_prev_node()

            next_node.set_prev_node(prev_node)
            prev_node.set_next_node(next_node)

        return node_to_remove


    def stringify_list(self):
        string_list = ""
        current_node = self.head_node

        while current_node:

            if current_node.get_value() != None:
                string_list += str(current_node.get_value()) + "\n"
                current_node = current_node.get_next_node()

        return string_list
3

What if there was a add_by_value() method that adds a node to the linked list even if the value is not the head node or tail node like the reverse of the remove_by_value() method? ? How could I make that and what can a solution code of that be?

4

Try the following. It seems to work… I added a “previous value” parameter in order to specify where exactly to add the new value. You have to provide something since they’re all connected to each other and you want to keep / update the links.

class Node: def __init__(self, value, next_node=None, prev_node=None): self.value = value self.next_node = next_node self.prev_node = prev_node def set_next_node(self, next_node): self.next_node = next_node def get_next_node(self): return self.next_node def set_prev_node(self, prev_node): self.prev_node = prev_node def get_prev_node(self): return self.prev_node def get_value(self): return self.value class DoublyLinkedList: def __init__(self): self.head_node = None self.tail_node = None def add_to_head(self, new_value): new_head = Node(new_value) current_head = self.head_node if current_head != None: current_head.set_prev_node(new_head) new_head.set_next_node(current_head) self.head_node = new_head if self.tail_node == None: self.tail_node = new_head def add_to_tail(self, new_value): new_tail = Node(new_value) current_tail = self.tail_node if current_tail != None: current_tail.set_next_node(new_tail) new_tail.set_prev_node(current_tail) self.tail_node = new_tail if self.head_node == None: self.head_node = new_tail def remove_head(self): removed_head = self.head_node if removed_head == None: return None self.head_node = removed_head.get_next_node() if self.head_node != None: self.head_node.set_prev_node(None) if removed_head == self.tail_node: self.remove_tail() return removed_head.get_value() def remove_tail(self): removed_tail = self.tail_node if removed_tail == None: return None self.tail_node = removed_tail.get_prev_node() if self.tail_node != None: self.tail_node.set_next_node(None) if removed_tail == self.head_node: self.remove_head() return removed_tail.get_value() def remove_by_value(self, value_to_remove): node_to_remove = None current_node = self.head_node while current_node != None: if current_node.get_value() == value_to_remove: node_to_remove = current_node break current_node = current_node.get_next_node() if node_to_remove == None: return None if node_to_remove == self.head_node: self.remove_head() elif node_to_remove == self.tail_node: self.remove_tail() else: next_node = node_to_remove.get_next_node() prev_node = node_to_remove.get_prev_node() next_node.set_prev_node(prev_node) prev_node.set_next_node(next_node) return node_to_remove def remove_by_value_tail(self, value_to_remove): node_to_remove = None current_node = self.tail_node while current_node != None: if current_node.get_value() == value_to_remove: node_to_remove = current_node break current_node = current_node.get_prev_node() if node_to_remove == None: return None if node_to_remove == self.head_node: self.remove_head() elif node_to_remove == self.tail_node: self.remove_tail() else: next_node = node_to_remove.get_next_node() prev_node = node_to_remove.get_prev_node() next_node.set_prev_node(prev_node) prev_node.set_next_node(next_node) return node_to_remove def add_by_value(self, prev_value, new_value): new_node = Node(new_value) current_node = self.head_node while current_node != None: if current_node.get_value() == prev_value: new_node.set_next_node(current_node.get_next_node()) current_node.set_next_node(new_node) break current_node = current_node.get_next_node() if new_node == None: return None return new_node def stringify_list(self): string_list = "" current_node = self.head_node while current_node: if current_node.get_value() != None: string_list += str(current_node.get_value()) + "\n" current_node = current_node.get_next_node() return string_list subway = DoublyLinkedList() subway.add_to_tail("Times Square") subway.add_to_tail("Columbus Circle") subway.add_to_tail("Central Park") subway.add_to_tail("Natural History Museum") subway.add_to_tail("Harlem") subway.add_by_value("Natural History Museum", "Park Ave") subway.add_by_value("Columbus Circle", "Bryant Park") print(subway.stringify_list())
5

So, having done all this, I have to wonder, why do we have to create the get/set functions?
why not just directly edit the elements?
I mean typing:
next_node = current_node.get_next_node()
prev_node = current_node.get_prev_node()
new_node.set_next_node(next_node)
new_node.set_prev_node(prev_node)
vs
new_node.next_node = current_node.next_node
new_node.prev_node = current_node.prev_node

I mean, I suppose if you wanted to do more in your get/set functions other than just assignment, I would understand.

6

There’s some nice discussion here that might help- Linked lists - Two ways of writing the same thing?

For some general discussion about this style of programming (accessors or getters/setters) I think Wikipedia has a nice generic introduction but you can get more information suited to your level if you search around-

In Python you might find more use of properties than straightforward setters as they’re directly supported as a built-in in the language. There’s some discussion on what a property is here:

When it comes to the lessons the tests are strict and expect a certain style so that’s what you’ll need to stick with. Hopefully the given links helps with the why and the potentially more convenient alternatives available in Python.

7

def remove_by_value(self, value_to_remove):
node_to_remove = None
current_right = self.tail_node
current_left = self.head_node

while current_left is not None and current_right is not None:
 
  if current_left.get_value() == value_to_remove:
    node_to_remove = current_node
    break

  if current_right.get_value() == value_to_remove:
    node_to_remove = current_node
    break
  
  if current_left.get_prev_node() == current_right:
    return None
  
  current_right = current_right.get_prev_node()
  current_left = current_left.get_prev_node()


if node_to_remove == None:
  return None

if node_to_remove == self.head_node:
  self.remove_head()
elif node_to_remove == self.tail_node:
  self.remove_tail()
else:
  next_node = node_to_remove.get_next_node()
  prev_node = node_to_remove.get_prev_node()
  next_node.set_prev_node(prev_node)
  prev_node.set_next_node(next_node)

return node_to_remove

Does this run at O(log n) time complexity ? Since standard process has O(n) time complexity as you might have to traverse the whole linked list, nth time to find the value. But, this process you have two pointers looking for the value from left and right which I assume will reduce the time by half.