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