From d4e4d209c7b750a6ecd50acbe2e53566c2761d67 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Wed, 22 Jan 2014 12:03:59 +0100 Subject: add doubly linked list MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- Makefile | 4 +- .../linkedlists/DoublyLinkedList.java | 40 ++++++++ .../linkedlists/SinglyLinkedList.java | 2 +- .../linkedlists/TaillessSinglyLinkedList.java | 2 +- src/datastructures/linkedlists/template | 103 ++++++++++++++++++++- 5 files changed, 146 insertions(+), 5 deletions(-) create mode 100644 src/datastructures/linkedlists/DoublyLinkedList.java diff --git a/Makefile b/Makefile index 6babc04..c8a47c9 100644 --- a/Makefile +++ b/Makefile @@ -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 . + */ +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 The value stored in the structure + */ +public class DoublyLinkedList +£>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 The value stored in the structure */ public class SinglyLinkedList -£>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 The value stored in the structure */ public class TaillessSinglyLinkedList -£>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 } -- cgit v1.2.3-70-g09d2