add headless linked lists

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

3 files changed, 93 insertions, 1 deletions

diff --git a/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java b/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java
new file mode 100644
index 0000000..23a59f1
--- /dev/null
+++ b/src/datastructures/linkedlists/HeadlessDoublyLinkedList.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;
+
+
+/**
+ * Headless 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 one refence nodes, the last node
+ * in the list. This 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 HeadlessDoublyLinkedList<T>
+£>export with_head=0 with_tail=1 with_prev=1
+£>gpp -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d'
+
diff --git a/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java b/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java
new file mode 100644
index 0000000..4bbff31
--- /dev/null
+++ b/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java
@@ -0,0 +1,49 @@
+/**
+ * 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;
+
+
+/**
+ * Headless singly 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 singly linked list only stores nodes
+ * with references to the following node. It also
+ * stores one refence nodes, the last node in the
+ * list. This 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).
+ * 
+ * A headless singly linked list some features that
+ * could be an advantage depending on what you are
+ * using it for: Because it is singly linked it uses
+ * slightly less memory and it is slightly faster.
+ * Because it is also headless there is not need to
+ * remove nodes from the beginning of the list if you
+ * are iterating over the list, they are automatically
+ * lost and freed by the garbage collector (assuming
+ * there is one.)
+ * 
+ * @param  <T>  The value stored in the structure
+ */
+public class HeadlessSinglyLinkedList<T>
+£>export with_head=0 with_tail=1 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 0a24a89..71c6a84 100644
--- a/src/datastructures/linkedlists/template
+++ b/src/datastructures/linkedlists/template
@@ -193,7 +193,7 @@
 	node.next = successor;
 	if (node.previous != null)
 	    node.previous.next = node;
-£>if (( with_tail )); then
+£>if (( with_head )); then
 	if (this.head == successor)
 	    this.head = node;
 £>fi
@@ -252,7 +252,10 @@
     public Node insertEnd(T value)
     {
 	if (this.tail == null)
+£>(( with_head )) &&
 	    return insertBeginning(value);
+£>(( with_head )) ||
+	    return this.tail = new Node(value);
 	return insertAfter(value, this.tail);
     }