diff options
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | src/datastructures/linkedlists/DoublyLinkedList.java | 40 | ||||
| -rw-r--r-- | src/datastructures/linkedlists/SinglyLinkedList.java | 2 | ||||
| -rw-r--r-- | src/datastructures/linkedlists/TaillessSinglyLinkedList.java | 2 | ||||
| -rw-r--r-- | src/datastructures/linkedlists/template | 103 |
5 files changed, 146 insertions, 5 deletions
@@ -6,6 +6,8 @@ SRC = $(shell find src | grep '\.java$$') PPD = $(shell find src | grep '\.java$$' | sed -e 's:^src:obj:') OBJ = $(shell find src | grep '\.java$$' | sed -e 's:^src:obj:' | sed -e 's:java$$:class:') +OBJ_LINKED_LISTS = $(shell find src/datastructures/linkedlists | grep 'LinkedList.java$$' | sed -e 's:^src:obj:') + .PHONY: all all: $(OBJ) @@ -18,7 +20,7 @@ obj/%.java: src/%.java $(foreach F, $(PP), src/$(F)) $(GPP) -s £ < "$<" > "$@" -obj/datastructures/linkedlists/*.java: src/datastructures/linkedlists/template +$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/template obj/algorithms/searching/MultiinterpolationSearch.class: obj/algorithms/searching/InterpolationSearch.class obj/algorithms/searching/MultibinarySearch.class: obj/algorithms/searching/BinarySearch.class diff --git a/src/datastructures/linkedlists/DoublyLinkedList.java b/src/datastructures/linkedlists/DoublyLinkedList.java new file mode 100644 index 0000000..334eee5 --- /dev/null +++ b/src/datastructures/linkedlists/DoublyLinkedList.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; + + +/** + * 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 two refence nodes, the first node + * in the list, and the last node in the list. The + * 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 DoublyLinkedList<T> +£>export 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 50814c6..b0bfc51 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 +£>export with_tail=1 with_prev=0 £>gpp -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' diff --git a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java index a73ab72..6de16b8 100644 --- a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java @@ -34,6 +34,6 @@ package datastructures.linkedlists; * @param <T> The value stored in the structure */ public class TaillessSinglyLinkedList<T> -£>export with_tail=0 +£>export 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 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 } |