aboutsummaryrefslogtreecommitdiffstats
path: root/src/datastructures/linkedlists
diff options
context:
space:
mode:
authorMattias Andrée <maandree@operamail.com>2014-01-22 12:36:23 +0100
committerMattias Andrée <maandree@operamail.com>2014-01-22 12:36:23 +0100
commit564354ad8ef2044e68f5a26b155bfe0f4c9397c2 (patch)
treec30399b0cab41320a3759c197e198b760800933f /src/datastructures/linkedlists
parentadd circularly linked lists (diff)
downloadalgorithms-and-data-structures-564354ad8ef2044e68f5a26b155bfe0f4c9397c2.tar.gz
algorithms-and-data-structures-564354ad8ef2044e68f5a26b155bfe0f4c9397c2.tar.bz2
algorithms-and-data-structures-564354ad8ef2044e68f5a26b155bfe0f4c9397c2.tar.xz
add headless linked lists
Signed-off-by: Mattias Andrée <maandree@operamail.com>
Diffstat (limited to 'src/datastructures/linkedlists')
-rw-r--r--src/datastructures/linkedlists/HeadlessDoublyLinkedList.java40
-rw-r--r--src/datastructures/linkedlists/HeadlessSinglyLinkedList.java49
-rw-r--r--src/datastructures/linkedlists/template5
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);
}