How could I make this singly linked list into a doubly linked list?

123

I've created a linked list in Python, and it is singly linked. This works perfectly fine, but I want to implement it so it's doubly linked, but I'm having trouble figuring out how to do it.

# node class
class node:
    def __init__(self):
        self.data = None # contains the data
        self.next = None # contains the reference to the next node

# linked list class
class linked_list:
    def __init__(self):
        self.cur_node = None

    def add_node(self, data):
        new_node = node() # create a new node
        new_node.data = data
        new_node.next = self.cur_node # link the new node to the 'previous' node.
        self.cur_node = new_node # set the current node to the new one.

    def list_print(self):
        node = self.cur_node # cant point to ll!
        while node:
            print(node.data)
            node = node.next

I know I need to add self.previous to the node class, and I think I need to add something to the linked list constructor and add_node function, but I'm not sure where to start.

I don't actually need to use this functionality in a program, I'm just trying to learn about how linked lists are implemented at a lower level.

gil

It's not so much a coding problem as a conceptual problem. You need to figure out how you want your code to behave. Implementing the desired behavior is not (in this case) at all difficult.

Say we want these behaviors:

# construction
dlist = DoublyLinkedList()

# access to head and tail nodes
dlist.head  # should return the head node
dlist.tail  # should return the tail node

dlist.head.prev is None  # should be True
dlist.tail.next is None  # should be True 

# adding nodes at both ends
dlist.add_head()
dlist.add_tail()

# iteration in both directions
for node in dlist:
    # do something to the node
for node in reversed(dlist):
    # do something to the node

When you have written out the desired behavior like this, you'll also have got some test code ready.

Now let's start by modifying the Node class (you should use CamelCase for class names):

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

    def __repr__(self):
        return '<{}, {}>'.format(self.data, self.next)

We add prev since that's obviously needed. But we also improve on your original version by having data and next as parameters, so you can have these values set when a node is created. And __repr__ is always nice to have, for debugging if not for anything else.

Now for the list itself. The key is, (a) instead of one cur_node, you need two handles on the list, which I've been calling head and tail, and (b) when adding nodes, the very first node is a special case where we have to make changes to both head and tail.

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

    def __repr__(self):
        return '<DoublyLinkedList {}>'.format(self.head)

    def add_head(self, data=None):
        if self.head is None:
            self.head = self.tail = Node(data)  # the very fist node
        else:
            new_head = Node(data=data, next=self.head)  # prev is None
            self.head.prev = self.head = new_head

    def add_tail(self, data=None):
        if self.tail is None:
            self.head = self.tail = Node(data)  # the very first node
        else:
            new_tail = Node(data=data, prev=self.tail)  # next is None
            self.tail.next = self.tail = new_tail

    # implements iteration from head to tail
    def __iter__(self):
        current = self.head
        while current is not None:
            yield current
            current= current.next

    # implements iteration from tail to head
    def __reversed__(self):
        current = self.tail
        while current  is not None:
            yield current
            current = current.prev

Let's test this

>>> dlist = DoublyLinkedList()
>>> print(dlist)
<DoublyLinkedList None>
>>> dlist.add_head(1)
>>> dlist.add_tail(2)
>>> dlist.add_tail(3)
>>> dlist.add_head(0)
>>> print(dlist)  # __repr__ is such a nice thing to have
<DoublyLinkedList <0, <1, <2, <3, None>>>>>
>>> print(dlist.head)
<0, <1, <2, <3, None>>>>
>>> print(dlist.tail)
<3, None>
>>> print(dlist.head.prev is None, dlist.tail.next is None)
True, True
>>> print(dlist.tail.prev.next is dlist.tail)
True
>>> [node.data for node in dlist]
[0, 1, 2, 3]
>>> for node in reversed(dlist):
...     print(node.data, node)
3 <3, None>
2 <2, <3, None>>
1 <1, <2, <3, None>>>
0 <0, <1, <2, <3, None>>>>

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related