Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
"""Implement doubly-linked list in Python."""
class Node:
"""Node implementation for doubly-linked list."""
def __init__(self, v=None, next=None, prev=None):
"""Construct a node."""
self.value = v
self.next = next
self.prev = prev
class DoublyLinkedList:
"""Implementation of doubly-linked list."""
def __init__(self, head=None, tail=None, length=0):
"""Construct a doubly-linked list."""
self.head = head
self.tail = tail
self.length = length
def is_empty(self):
"""Return True if the list is empty; False otherwise."""
return self.length == 0
def prepend(self, v):
"""Prepend given value to the linked list."""
new_cell = Node(v, self.head, None)
# prepend when the list is empty
if self.is_empty():
self.head = new_cell
self.tail = new_cell
self.length = 1
return self
# prepend when the list is not empty
self.head.prev = new_cell
self.head = new_cell
self.length = self.length + 1
return self
def seek_from_end(self, i):
"""Return value at index i from the end of the list."""
class TestDoublyLinkedList(object):
"""Test doubly-linked list."""
def test_creation(self):
"""Test __init()__ functionality."""
n = Node(5)
ll = DoublyLinkedList(n, length=1)
assert ll.length == 1
ll.prepend(6)
ll.prepend(19)
ll.prepend(121)
assert ll.length == 4
ll2 = DoublyLinkedList()
assert ll2 is not None
assert ll2.length == 0
assert ll2.head is None
assert ll2.tail is None
ll2.prepend(8)
assert ll2.head is not None
assert ll2.tail is not None
assert ll2.length == 1
assert ll2.head.value == 8
assert ll2.tail.value == 8
assert ll2.head.next is None
assert ll2.tail.next is None
assert ll2.head.prev is None
assert ll2.tail.prev is None
ll2.prepend(9)
assert ll2.length == 2
assert ll2.head.value == 9
assert ll2.tail.value == 8
assert ll2.head.next is not None
assert ll2.tail.next is None
assert ll2.head.prev is None
assert ll2.tail.prev is not None
assert ll2.head.next.value == 8
assert ll2.tail.prev.value == 9
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment