diff options
Diffstat (limited to 'src/datastructures/linkedlists/template')
-rw-r--r-- | src/datastructures/linkedlists/template | 103 |
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 } |