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/template103
1 files changed, 101 insertions, 2 deletions
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
}