aboutsummaryrefslogtreecommitdiffstats
path: root/src/datastructures/linkedlists/template
diff options
context:
space:
mode:
Diffstat (limited to 'src/datastructures/linkedlists/template')
-rw-r--r--src/datastructures/linkedlists/template57
1 files changed, 54 insertions, 3 deletions
diff --git a/src/datastructures/linkedlists/template b/src/datastructures/linkedlists/template
index d2f6c84..d207f5a 100644
--- a/src/datastructures/linkedlists/template
+++ b/src/datastructures/linkedlists/template
@@ -15,6 +15,7 @@
* 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/>.
*/
+public class £{name}<T>
{
/**
* Node for the list
@@ -53,6 +54,12 @@
}
+£>if (( with_sentinel )); then
+ /**
+ * The sentinel node in the list
+ */
+ public Node edge;
+£>fi
£>if (( with_head )); then
/**
@@ -69,8 +76,19 @@
£>fi
-
-£>if (( 1 - with_head )) && (( 1 - with_tail )); then
+
+£>if (( with_sentinel )); then
+ /**
+ * Initialiser
+ */
+ {
+ this.edge = new Node(null);
+ this.edge.next = this.edge;
+£>(( with_prev )) &&
+ this.edge.previous = this.edge;
+ }
+
+£>elif (( 1 - with_head )) && (( 1 - with_tail )); then
/**
* Creates the initial node in a circularly linked list
*
@@ -86,6 +104,7 @@
}
£>fi
+
£>if (( with_head )); then
/**
* Insert a value in the beginning of the list
@@ -94,6 +113,11 @@
* @return The node that has been created and inserted
*/
public Node insertBeginning(T value)
+£>if (( with_sentinel )); then
+ {
+ return insertAfter(value, this.edge);
+ }
+£>else
{
Node node = new Node(value);
node.next = this.head;
@@ -108,6 +132,7 @@
this.head = node;
return node;
}
+£>fi
/**
* Remove the node at the beginning of the list
@@ -115,6 +140,11 @@
* @return The node that has been removed
*/
public Node removeBeginning()
+£>if (( with_sentinel )); then
+ {
+ return removeAfter(this.edge);
+ }
+£>else
{
Node node = this.head;
if (node != null)
@@ -130,6 +160,7 @@
return node;
}
£>fi
+£>fi
/**
* Insert a value after a specified, reference, node
@@ -145,6 +176,7 @@
predecessor.next = node;
£>if (( with_prev )); then
node.previous = predecessor;
+£>(( with_sentinel )) ||
if (node.next != null)
node.next.previous = node;
£>fi
@@ -164,10 +196,12 @@
public Node removeAfter(Node predecessor)
{
Node node = predecessor.next;
+£>(( with_sentinel )) ||
if (node != null)
{
predecessor.next = node.next;
£>if (( with_prev )); then
+£>(( with_sentinel )) ||
if (node.next != null)
node.next.previous = predecessor;
£>fi
@@ -178,7 +212,7 @@
}
return node;
}
-
+
£>if (( with_prev )); then
/**
* Insert a value before a specified, reference, node
@@ -193,6 +227,7 @@
node.previous = successor.previous;
successor.previous = node;
node.next = successor;
+£>(( with_sentinel )) ||
if (node.previous != null)
node.previous.next = node;
£>if (( with_head )); then
@@ -211,9 +246,11 @@
public Node removeBefore(Node successor)
{
Node node = successor.previous;
+£>(( with_sentinel )) ||
if (node != null)
{
successor.previous = node.previous;
+£>(( with_sentinel )) ||
if (node.previous != null)
node.previous.next = successor;
£>if (( with_head )); then
@@ -231,12 +268,14 @@
*/
public void remove(Node node)
{
+£>(( with_sentinel )) ||
if (node.previous != null)
node.previous.next = node.next;
£>if (( with_head )); then
else
this.head = node.next;
£>fi
+£>(( with_sentinel )) ||
if (node.next != null)
node.next.previous = node.previous;
£>if (( with_tail )); then
@@ -254,6 +293,11 @@
* @return The node that has been created and inserted
*/
public Node insertEnd(T value)
+£>if (( with_sentinel )); then
+ {
+ return insertBefore(value, this.edge);
+ }
+£>else
{
if (this.tail == null)
£>(( with_head )) &&
@@ -262,6 +306,7 @@
return this.tail = new Node(value);
return insertAfter(value, this.tail);
}
+£>fi
£>if (( with_prev )); then
/**
@@ -270,6 +315,11 @@
* @return The node that has been removed
*/
public Node removeEnd()
+£>if (( with_sentinel )); then
+ {
+ return removeBefore(this.edge);
+ }
+£>else
{
Node node = this.tail;
if (node != null)
@@ -278,6 +328,7 @@
}
£>fi
£>fi
+£>fi
}