Doubly Linked List
Gotchas: when implementing delete()
you need to handle in their own way head, tails and middle nodes.
class Node(object): def __init__(self, value): self.value = value self.next = None self.prev = None class LinkedList(object): head = None tail = None def push(self, value): new_node = Node(value) if self.head is None: self.head = self.tail = new_node else: new_node.next = self.head self.head.prev = new_node self.head = new_node def append(self, value): new_node = Node(value) if self.tail is None: self.tail = self.head = new_node else: new_node.prev = self.tail self.tail.next = new_node self.tail = new_node def delete(self, value): n = self.head # first node if n.value == value: if n.next is None and n.prev is None: self.head = self.tail = None print 'list is empty' return else: self.head = self.head.next self.head.prev = None return # middle nodes while n.next is not None: if n.value == value: n.prev.next = n.next n.next.prev = n.prev return n = n.next # last node if n.value == value: n.prev.next = None def show(self): n = self.head while n is not None: print n.value, n = n.next print def showBack(self): n = self.tail while n is not None: print n.value, n = n.prev print l = LinkedList() l.append(20) l.append(30) l.push(10) l.show() l.showBack() l.delete(20) l.show() l.delete(10) l.show() l.delete(30) l.show()
I personally like delete()
implementation better:
def delete(self, value): # delete head if self.head.value == value: # if head is the last node if self.head.next is None: self.head = self.tail = None else: self.head = self.head.next self.head.prev = None # delete tail elif self.tail.value == value: self.tail = self.tail.prev self.tail.next = None # delete middle nodes else: n = self.head while n.value != value: n = n.next n.prev.next = n.next n.next.prev = n.prev