add doubly linked list

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

5 files changed, 146 insertions, 5 deletions

diff --git a/Makefile b/Makefile
index 6babc04..c8a47c9 100644
--- a/Makefile
+++ b/Makefile
@@ -6,6 +6,8 @@ SRC = $(shell find src | grep '\.java$$')
 PPD = $(shell find src | grep '\.java$$' | sed -e 's:^src:obj:')
 OBJ = $(shell find src | grep '\.java$$' | sed -e 's:^src:obj:' | sed -e 's:java$$:class:')
 
+OBJ_LINKED_LISTS = $(shell find src/datastructures/linkedlists | grep 'LinkedList.java$$' | sed -e 's:^src:obj:')
+
 
 .PHONY: all
 all: $(OBJ)
@@ -18,7 +20,7 @@ obj/%.java: src/%.java $(foreach F, $(PP), src/$(F))
 	$(GPP) -s £ < "$<" > "$@"
 
 
-obj/datastructures/linkedlists/*.java: src/datastructures/linkedlists/template
+$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/template
 obj/algorithms/searching/MultiinterpolationSearch.class: obj/algorithms/searching/InterpolationSearch.class
 obj/algorithms/searching/MultibinarySearch.class: obj/algorithms/searching/BinarySearch.class
 
diff --git a/src/datastructures/linkedlists/DoublyLinkedList.java b/src/datastructures/linkedlists/DoublyLinkedList.java
new file mode 100644
index 0000000..334eee5
--- /dev/null
+++ b/src/datastructures/linkedlists/DoublyLinkedList.java
@@ -0,0 +1,40 @@
+/**
+ * Copyright © 2014  Mattias Andrée (maandree@member.fsf.org)
+ * 
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+package datastructures.linkedlists;
+
+
+/**
+ * Doubly linked list class. A linked list is a
+ * list constructed from nodes, which hold stored
+ * values, with references to each other, this is
+ * usally an ineffective data structure, especially
+ * on high-level object orientated languages. A
+ * doublely linked list stores nodes with references
+ * to both the following node and the previous node.
+ * It also stores two refence nodes, the first node
+ * in the list, and the last node in the list. The
+ * implemention only implements methods that do not
+ * require iterating over all nodes for find a
+ * specific; all other methods' — those that are
+ * implemented — time complexity is Θ(1).
+ * 
+ * @param  <T>  The value stored in the structure
+ */
+public class DoublyLinkedList<T>
+£>export with_tail=1 with_prev=1
+£>gpp -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d'
+
diff --git a/src/datastructures/linkedlists/SinglyLinkedList.java b/src/datastructures/linkedlists/SinglyLinkedList.java
index 50814c6..b0bfc51 100644
--- a/src/datastructures/linkedlists/SinglyLinkedList.java
+++ b/src/datastructures/linkedlists/SinglyLinkedList.java
@@ -35,6 +35,6 @@ package datastructures.linkedlists;
  * @param  <T>  The value stored in the structure
  */
 public class SinglyLinkedList<T>
-£>export with_tail=1
+£>export with_tail=1 with_prev=0
 £>gpp -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d'
 
diff --git a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java
index a73ab72..6de16b8 100644
--- a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java
@@ -34,6 +34,6 @@ package datastructures.linkedlists;
  * @param  <T>  The value stored in the structure
  */
 public class TaillessSinglyLinkedList<T>
-£>export with_tail=0
+£>export with_tail=0 with_prev=0
 £>gpp -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d'
 
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
     
 }