From 3344d6da4af50522d4de0920b010e99f8377cdd0 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Wed, 22 Jan 2014 12:18:42 +0100 Subject: preparation for circularly linked lists MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- .../linkedlists/DoublyLinkedList.java | 2 +- .../linkedlists/SinglyLinkedList.java | 2 +- .../linkedlists/TaillessDoublyLinkedList.java | 6 ++-- .../linkedlists/TaillessSinglyLinkedList.java | 4 +-- src/datastructures/linkedlists/template | 41 +++++++++++++++++----- 5 files changed, 40 insertions(+), 15 deletions(-) (limited to 'src/datastructures/linkedlists') 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 The value stored in the structure */ public class DoublyLinkedList -£>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 The value stored in the structure */ public class SinglyLinkedList -£>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 The value stored in the structure */ public class TaillessDoublyLinkedList -£>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 The value stored in the structure */ public class TaillessSinglyLinkedList -£>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) { -- cgit v1.2.3-70-g09d2