diff options
author | Mattias Andrée <maandree@operamail.com> | 2014-01-22 12:18:42 +0100 |
---|---|---|
committer | Mattias Andrée <maandree@operamail.com> | 2014-01-22 12:18:42 +0100 |
commit | 3344d6da4af50522d4de0920b010e99f8377cdd0 (patch) | |
tree | 809cca612304c4fc47f316b1d043a9117873bb8a | |
parent | m doc (diff) | |
download | algorithms-and-data-structures-3344d6da4af50522d4de0920b010e99f8377cdd0.tar.gz algorithms-and-data-structures-3344d6da4af50522d4de0920b010e99f8377cdd0.tar.bz2 algorithms-and-data-structures-3344d6da4af50522d4de0920b010e99f8377cdd0.tar.xz |
preparation for circularly linked lists
Signed-off-by: Mattias Andrée <maandree@operamail.com>
5 files changed, 40 insertions, 15 deletions
diff --git a/src/datastructures/linkedlists/DoublyLinkedList.java b/src/datastructures/linkedlists/DoublyLinkedList.java index 7bb091d..c84172c 100644 --- a/src/datastructures/linkedlists/DoublyLinkedList.java +++ b/src/datastructures/linkedlists/DoublyLinkedList.java @@ -35,6 +35,6 @@ package datastructures.linkedlists; * @param <T> The value stored in the structure */ public class DoublyLinkedList<T> -£>export with_tail=1 with_prev=1 +£>export with_head=1 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 6633941..9e39809 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 with_prev=0 +£>export with_head=1 with_tail=1 with_prev=0 £>gpp -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' diff --git a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java index 0304ea9..fa3c3e6 100644 --- a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java @@ -18,8 +18,8 @@ package datastructures.linkedlists; /** - * Doubly linked list class. A linked list is a - * list constructed from nodes, which hold stored + * Tailless 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 @@ -35,6 +35,6 @@ package datastructures.linkedlists; * @param <T> The value stored in the structure */ public class TaillessDoublyLinkedList<T> -£>export with_tail=0 with_prev=1 +£>export with_head=1 with_tail=0 with_prev=1 £>gpp -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' diff --git a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java index aecd612..2c66eb3 100644 --- a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java @@ -18,7 +18,7 @@ package datastructures.linkedlists; /** - * Taileess singly linked list class. A linked list + * Tailless singly 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, @@ -34,6 +34,6 @@ package datastructures.linkedlists; * @param <T> The value stored in the structure */ public class TaillessSinglyLinkedList<T> -£>export with_tail=0 with_prev=0 +£>export with_head=1 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 b0311b5..0a24a89 100644 --- a/src/datastructures/linkedlists/template +++ b/src/datastructures/linkedlists/template @@ -54,10 +54,12 @@ +£>if (( with_head )); then /** * The first node in the list */ public Node head = null; +£>fi £>if (( with_tail )); then /** @@ -67,12 +69,29 @@ £>fi + +£>if (( 1 - with_head )) && (( 1 - with_tail )); then + /** + * Creates the initial node in a circularly linked list + * + * @param value The value of the initial node + * @return The node that has been created and inserted + */ + public Node create(T value) + { + Node node = new Node(value); +£>(( with_prev )) && + node.previous = node; + return node.next = node; + } +£>fi +£>if (( with_head )); then /** * Insert a value in the beginning of the list * * @param value The value to insert - * @return The node that has be created and inserted + * @return The node that has been created and inserted */ public Node insertBeginning(T value) { @@ -110,13 +129,14 @@ £>fi return node; } +£>fi /** * Insert a value after a specified, reference, node * * @param value The value to insert * @param predecessor The reference node - * @return The node that has be created and inserted + * @return The node that has been created and inserted */ public Node insertAfter(T value, Node predecessor) { @@ -163,7 +183,7 @@ * * @param value The value to insert * @param successor The reference node - * @return The node that has be created and inserted + * @return The node that has been created and inserted */ public Node insertBefore(T value, Node successor) { @@ -173,8 +193,10 @@ node.next = successor; if (node.previous != null) node.previous.next = node; +£>if (( with_tail )); then if (this.head == successor) this.head = node; +£>fi return node; } @@ -191,8 +213,10 @@ successor.previous = node.previous; else if (node.previous != null) node.previous.next = successor; +£>if (( with_head )); then if (this.head == node) this.head = successor; +£>fi return node; } @@ -203,11 +227,12 @@ */ public void remove(Node node) { - if (node.previous == null) - this.head = node.next; - else + if (node.previous != null) node.previous.next = node.next; - +£>if (( with_head )); then + else + this.head = node.next; +£>fi if (node.next != null) node.next.previous = node.previous; £>if (( with_tail )); then @@ -222,7 +247,7 @@ * Insert a value in the end of the list * * @param value The value to insert - * @return The node that has be created and inserted + * @return The node that has been created and inserted */ public Node insertEnd(T value) { |