add doubly linked list

Signed-off-by: Mattias Andrée <maandree@operamail.com>

1 files changed, 101 insertions, 2 deletions

diff --git a/src/datastructures/linkedlists/template b/src/datastructures/linkedlists/template
index 4ea20ad..b0311b5 100644
--- a/src/datastructures/linkedlists/template
+++ b/src/datastructures/linkedlists/template
@@ -43,6 +43,13 @@
 	 */
 	public Node next = null;
 	
+£>if (( with_prev )); then
+	/**
+	 * The previous node in the list
+	 */
+	public Node previous = null;
+£>fi
+	
     }
     
     
@@ -71,6 +78,10 @@
     {
 	Node node = new Node(value);
 	node.next = this.head;
+£>if (( with_prev )); then
+	if (node.next != null)
+	    node.next.previous = node;
+£>fi
 £>if (( with_tail )); then
 	if (this.head == null)
 	    this.tail = node;
@@ -86,9 +97,13 @@
      */
     public Node removeBeginning()
     {
-	Node node = head;
+	Node node = this.head;
 	if (node != null)
-	    head = head.next;
+	    this.head = this.head.next;
+£>if (( with_prev )); then
+	if (this.head != null)
+	    this.head.previous = null;
+£>fi
 £>if (( with_tail )); then
 	if (this.tail == node)
 	    this.tail = null;
@@ -108,6 +123,11 @@
 	Node node = new Node(value);
 	node.next = predecessor.next;
 	predecessor.next = node;
+£>if (( with_prev )); then
+	node.previous = predecessor;
+	if (node.next != null)
+	    node.next.previous = node;
+£>fi
 £>if (( with_tail )); then
 	if (this.tail == predecessor)
 	    this.tail = node;
@@ -126,12 +146,76 @@
 	Node node = predecessor.next;
 	if (node == null)
 	    predecessor.next = node.next;
+£>if (( with_prev )); then
+	else if (node.next != null)
+	    node.next.previous = predecessor;
+£>fi
 £>if (( with_tail )); then
 	if (this.tail == node)
 	    this.tail = predecessor;
 £>fi
 	return node;
     }
+
+£>if (( with_prev )); then
+    /**
+     * Insert a value before a specified, reference, node
+     * 
+     * @param   value      The value to insert
+     * @param   successor  The reference node
+     * @return             The node that has be created and inserted
+     */
+    public Node insertBefore(T value, Node successor)
+    {
+	Node node = new Node(value);
+	node.previous = successor.previous;
+	successor.previous = node;
+	node.next = successor;
+	if (node.previous != null)
+	    node.previous.next = node;
+	if (this.head == successor)
+	    this.head = node;
+	return node;
+    }
+    
+    /**
+     * Remove the node before a specified, reference, node
+     * 
+     * @param   successor  The reference node
+     * @return             The node that has been removed
+     */
+    public Node removeBefore(Node successor)
+    {
+	Node node = successor.previous;
+	if (node == null)
+	    successor.previous = node.previous;
+	else if (node.previous != null)
+	    node.previous.next = successor;
+	if (this.head == node)
+	    this.head = successor;
+	return node;
+    }
+    
+    /**
+     * Remove the node from the list
+     * 
+     * @param  node  The node to remove
+     */
+    public void remove(Node node)
+    {
+	if (node.previous == null)
+	    this.head = node.next;
+	else
+	    node.previous.next = node.next;
+	
+	if (node.next != null)
+	    node.next.previous = node.previous;
+£>if (( with_tail )); then
+	else
+	    this.tail = node.previous;
+£>fi
+    }
+£>fi
     
 £>if (( with_tail )); then
     /**
@@ -146,6 +230,21 @@
 	    return insertBeginning(value);
 	return insertAfter(value, this.tail);
     }
+
+£>if (( with_prev )); then
+    /**
+     * Remove the node at the end of the list
+     * 
+     * @return  The node that has been removed
+     */
+    public Node removeEnd()
+    {
+	Node node = this.tail;
+	if (node != null)
+	    (this.tail = node.previous).next = null;
+	return node;
+    }
+£>fi
 £>fi
     
 }