aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMattias Andrée <maandree@operamail.com>2014-01-22 12:18:42 +0100
committerMattias Andrée <maandree@operamail.com>2014-01-22 12:18:42 +0100
commit3344d6da4af50522d4de0920b010e99f8377cdd0 (patch)
tree809cca612304c4fc47f316b1d043a9117873bb8a
parentm doc (diff)
downloadalgorithms-and-data-structures-3344d6da4af50522d4de0920b010e99f8377cdd0.tar.gz
algorithms-and-data-structures-3344d6da4af50522d4de0920b010e99f8377cdd0.tar.bz2
algorithms-and-data-structures-3344d6da4af50522d4de0920b010e99f8377cdd0.tar.xz
preparation for circularly linked lists
Signed-off-by: Mattias Andrée <maandree@operamail.com>
-rw-r--r--src/datastructures/linkedlists/DoublyLinkedList.java2
-rw-r--r--src/datastructures/linkedlists/SinglyLinkedList.java2
-rw-r--r--src/datastructures/linkedlists/TaillessDoublyLinkedList.java6
-rw-r--r--src/datastructures/linkedlists/TaillessSinglyLinkedList.java4
-rw-r--r--src/datastructures/linkedlists/template41
5 files changed, 40 insertions, 15 deletions
diff --git a/src/datastructures/linkedlists/DoublyLinkedList.java b/src/datastructures/linkedlists/DoublyLinkedList.java
index 7bb091d..c84172c 100644
--- a/src/datastructures/linkedlists/DoublyLinkedList.java
+++ b/src/datastructures/linkedlists/DoublyLinkedList.java
@@ -35,6 +35,6 @@ package datastructures.linkedlists;
* @param <T> The value stored in the structure
*/
public class DoublyLinkedList<T>
-£>export with_tail=1 with_prev=1
+£>export with_head=1 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 6633941..9e39809 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 with_prev=0
+£>export with_head=1 with_tail=1 with_prev=0
£>gpp -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d'
diff --git a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java
index 0304ea9..fa3c3e6 100644
--- a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java
@@ -18,8 +18,8 @@ package datastructures.linkedlists;
/**
- * Doubly linked list class. A linked list is a
- * list constructed from nodes, which hold stored
+ * Tailless 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
@@ -35,6 +35,6 @@ package datastructures.linkedlists;
* @param <T> The value stored in the structure
*/
public class TaillessDoublyLinkedList<T>
-£>export with_tail=0 with_prev=1
+£>export with_head=1 with_tail=0 with_prev=1
£>gpp -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d'
diff --git a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java
index aecd612..2c66eb3 100644
--- a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java
@@ -18,7 +18,7 @@ package datastructures.linkedlists;
/**
- * Taileess singly linked list class. A linked list
+ * Tailless 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,
@@ -34,6 +34,6 @@ package datastructures.linkedlists;
* @param <T> The value stored in the structure
*/
public class TaillessSinglyLinkedList<T>
-£>export with_tail=0 with_prev=0
+£>export with_head=1 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 b0311b5..0a24a89 100644
--- a/src/datastructures/linkedlists/template
+++ b/src/datastructures/linkedlists/template
@@ -54,10 +54,12 @@
+£>if (( with_head )); then
/**
* The first node in the list
*/
public Node head = null;
+£>fi
£>if (( with_tail )); then
/**
@@ -67,12 +69,29 @@
£>fi
+
+£>if (( 1 - with_head )) && (( 1 - with_tail )); then
+ /**
+ * Creates the initial node in a circularly linked list
+ *
+ * @param value The value of the initial node
+ * @return The node that has been created and inserted
+ */
+ public Node create(T value)
+ {
+ Node node = new Node(value);
+£>(( with_prev )) &&
+ node.previous = node;
+ return node.next = node;
+ }
+£>fi
+£>if (( with_head )); then
/**
* Insert a value in the beginning of the list
*
* @param value The value to insert
- * @return The node that has be created and inserted
+ * @return The node that has been created and inserted
*/
public Node insertBeginning(T value)
{
@@ -110,13 +129,14 @@
£>fi
return node;
}
+£>fi
/**
* Insert a value after a specified, reference, node
*
* @param value The value to insert
* @param predecessor The reference node
- * @return The node that has be created and inserted
+ * @return The node that has been created and inserted
*/
public Node insertAfter(T value, Node predecessor)
{
@@ -163,7 +183,7 @@
*
* @param value The value to insert
* @param successor The reference node
- * @return The node that has be created and inserted
+ * @return The node that has been created and inserted
*/
public Node insertBefore(T value, Node successor)
{
@@ -173,8 +193,10 @@
node.next = successor;
if (node.previous != null)
node.previous.next = node;
+£>if (( with_tail )); then
if (this.head == successor)
this.head = node;
+£>fi
return node;
}
@@ -191,8 +213,10 @@
successor.previous = node.previous;
else if (node.previous != null)
node.previous.next = successor;
+£>if (( with_head )); then
if (this.head == node)
this.head = successor;
+£>fi
return node;
}
@@ -203,11 +227,12 @@
*/
public void remove(Node node)
{
- if (node.previous == null)
- this.head = node.next;
- else
+ if (node.previous != null)
node.previous.next = node.next;
-
+£>if (( with_head )); then
+ else
+ this.head = node.next;
+£>fi
if (node.next != null)
node.next.previous = node.previous;
£>if (( with_tail )); then
@@ -222,7 +247,7 @@
* Insert a value in the end of the list
*
* @param value The value to insert
- * @return The node that has be created and inserted
+ * @return The node that has been created and inserted
*/
public Node insertEnd(T value)
{