aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMattias Andrée <maandree@operamail.com>2014-01-23 10:25:39 +0100
committerMattias Andrée <maandree@operamail.com>2014-01-23 10:25:39 +0100
commit462bb1bb37d8ab9226f563852e4a53f670237d9c (patch)
treeab8b2c701f56b2f06977327f2642498102dfdd93
parentadd sentinel doubly linked list (diff)
downloadalgorithms-and-data-structures-462bb1bb37d8ab9226f563852e4a53f670237d9c.tar.gz
algorithms-and-data-structures-462bb1bb37d8ab9226f563852e4a53f670237d9c.tar.bz2
algorithms-and-data-structures-462bb1bb37d8ab9226f563852e4a53f670237d9c.tar.xz
add array linked lists
Signed-off-by: Mattias Andrée <maandree@operamail.com>
-rw-r--r--Makefile4
-rw-r--r--src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java31
-rw-r--r--src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java31
-rw-r--r--src/datastructures/linkedlists/ArrayDoublyLinkedList.java31
-rw-r--r--src/datastructures/linkedlists/ArraySinglyLinkedList.java31
-rw-r--r--src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java31
-rw-r--r--src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java31
-rw-r--r--src/datastructures/linkedlists/array-template468
8 files changed, 657 insertions, 1 deletions
diff --git a/Makefile b/Makefile
index 0e85b78..becac32 100644
--- a/Makefile
+++ b/Makefile
@@ -20,7 +20,9 @@ obj/%.java: src/%.java $(foreach F, $(PP), src/$(F))
env GPP="$(GPP)" $(GPP) -s £ < "$<" > "$@"
-$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/template src/datastructures/linkedlists/sentinel-template
+$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/template
+$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/sentinel-template
+$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/array-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/ArrayCircularDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java
new file mode 100644
index 0000000..7e059bd
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java
@@ -0,0 +1,31 @@
+/**
+ * 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;
+
+
+/**
+ * Array circular doubly linked list class. An array
+ * linked list is a linked list constructed by parallel
+ * arrays. In this implementation, when a node is
+ * removed the value stored that that position is not
+ * removed before that position is reused.
+ *
+ * @param <T> The value stored in the structure
+ */
+£>export name=ArrayCircularDoublyLinkedList with_head=0 with_tail=0 with_prev=1
+£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d'
+
diff --git a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java
new file mode 100644
index 0000000..10496d4
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java
@@ -0,0 +1,31 @@
+/**
+ * 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;
+
+
+/**
+ * Array circular singly linked list class. An array
+ * linked list is a linked list constructed by parallel
+ * arrays. In this implementation, when a node is
+ * removed the value stored that that position is not
+ * removed before that position is reused.
+ *
+ * @param <T> The value stored in the structure
+ */
+£>export name=ArrayCircularSinglyLinkedList with_head=0 with_tail=0 with_prev=0
+£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d'
+
diff --git a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java
new file mode 100644
index 0000000..bcc2bc1
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java
@@ -0,0 +1,31 @@
+/**
+ * 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;
+
+
+/**
+ * Array doubly linked list class. An array linked list
+ * is a linked list constructed by parallel arrays. In
+ * this implementation, when a node is removed the value
+ * stored that that position is not removed before that
+ * position is reused.
+ *
+ * @param <T> The value stored in the structure
+ */
+£>export name=ArrayDoublyLinkedList with_head=1 with_tail=1 with_prev=1
+£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d'
+
diff --git a/src/datastructures/linkedlists/ArraySinglyLinkedList.java b/src/datastructures/linkedlists/ArraySinglyLinkedList.java
new file mode 100644
index 0000000..a4668d1
--- /dev/null
+++ b/src/datastructures/linkedlists/ArraySinglyLinkedList.java
@@ -0,0 +1,31 @@
+/**
+ * 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;
+
+
+/**
+ * Array singly linked list class. An array linked list
+ * is a linked list constructed by parallel arrays. In
+ * this implementation, when a node is removed the value
+ * stored that that position is not removed before that
+ * position is reused.
+ *
+ * @param <T> The value stored in the structure
+ */
+£>export name=ArraySinglyLinkedList with_head=1 with_tail=1 with_prev=0
+£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d'
+
diff --git a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java
new file mode 100644
index 0000000..5098bf1
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java
@@ -0,0 +1,31 @@
+/**
+ * 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;
+
+
+/**
+ * Array tailless doubly linked list class. An array
+ * linked list is a linked list constructed by parallel
+ * arrays. In this implementation, when a node is
+ * removed the value stored that that position is not
+ * removed before that position is reused.
+ *
+ * @param <T> The value stored in the structure
+ */
+£>export name=ArrayTaillessDoublyLinkedList with_head=1 with_tail=0 with_prev=1
+£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d'
+
diff --git a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java
new file mode 100644
index 0000000..bd27cee
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java
@@ -0,0 +1,31 @@
+/**
+ * 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;
+
+
+/**
+ * Array tailless singly linked list class. An array
+ * linked list is a linked list constructed by parallel
+ * arrays. In this implementation, when a node is
+ * removed the value stored that that position is not
+ * removed before that position is reused.
+ *
+ * @param <T> The value stored in the structure
+ */
+£>export name=ArrayTaillessSinglyLinkedList with_head=1 with_tail=0 with_prev=1
+£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d'
+
diff --git a/src/datastructures/linkedlists/array-template b/src/datastructures/linkedlists/array-template
new file mode 100644
index 0000000..5fce858
--- /dev/null
+++ b/src/datastructures/linkedlists/array-template
@@ -0,0 +1,468 @@
+/* -*- java -*- */
+/**
+ * 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/>.
+ */
+public class £{name}<T>
+{
+ /**
+ * The default initial capacity
+ */
+ private static final int DEFAULT_INITIAL_CAPACITY = 128;
+
+ /**
+ * Sentinel value indicating that an edge has been reached
+ */
+ public static final int EDGE = -1;
+
+ /**
+ * Sentinel value indicating that the position is unused
+ */
+ public static final int UNUSED = -2;
+
+
+
+ /**
+ * Constructor
+ */
+ public £{name}()
+ {
+ this(DEFAULT_INITIAL_CAPACITY);
+ }
+
+ /**
+ * Constructor
+ *
+ * @param initialCapacity The initial size of the arrays
+ */
+ @SuppressWarnings("unchecked")
+ public £{name}(int initialCapacity)
+ {
+ /* Most be a power of 2 */
+ if ((initialCapacity & initialCapacity - 1) != 0)
+ {
+ initialCapacity >>= 1;
+ initialCapacity >>= 2;
+ initialCapacity >>= 4;
+ initialCapacity >>= 8;
+ initialCapacity >>= 16;
+ initialCapacity++;
+ }
+
+ this.capacity = initialCapacity;
+ this.next = new int[initialCapacity];
+£>(( with_prev )) &&
+ this.previous = new int[initialCapacity];
+ this.reusable = new int[initialCapacity];
+ this.values = (T[])(new Object[initialCapacity]);
+ }
+
+
+
+ /**
+ * The size of the arrays
+ */
+ private int capacity;
+
+ /**
+ * The index after the last used index in
+ * {@link #values} and {@link #next}
+ */
+ public int end = 0;
+
+ /**
+ * Head of the stack of reusable positions
+ */
+ private int reuseHead = 0;
+
+ /**
+ * Stack of indices than are no longer in use
+ */
+ private int[] reusable;
+
+£>if (( with_head )); then
+ /**
+ * The first node in the list
+ */
+ public int head = EDGE;
+£>fi
+
+£>if (( with_tail )); then
+ /**
+ * The last node in the list
+ */
+ public int tail = EDGE;
+£>fi
+
+ /**
+ * The value stored in each node
+ */
+ public T[] values;
+
+ /**
+ * The next node for each node, {@link #EDGE}
+ * if the current node is the last node, and
+ * {@link #UNUSED} if there is no node on this
+ * position
+ */
+ public int[] next;
+
+£>if (( with_prev )); then
+ /**
+ * The previou node for each node, {@link #EDGE}
+ * if the current node is the first node, and
+ * {@link #UNUSED} if there is no node on this
+ * position
+ */
+ public int[] previous;
+£>fi
+
+
+
+ /**
+ * Pack the list so that there are no reusable
+ * positions, and reduce the capacity to the
+ * smallest capacity that can be used. Not that
+ * values (nodes) returned by the list's methods
+ * will become invalid. Additionally (to reduce
+ * the complexity) the list will be defragment
+ * so that the nodes' indices are continuous.
+ * This method has linear time complexity and
+ * linear memory complexity.
+ */
+ public void pack()
+ {
+ int size = this.end - reuseHead;
+ int cap = size;
+ if ((cap & cap - 1) != 0)
+ {
+ cap >>= 1;
+ cap >>= 2;
+ cap >>= 4;
+ cap >>= 8;
+ cap >>= 16;
+ cap++;
+ }
+
+ @SuppressWarnings("unchecked")
+ T[] vals = (T[])(new Object[cap]);
+£>if (( 1 - with_head )); then
+ int head = 0;
+ while ((head < this.end) && (this.next[head] == UNUSED))
+ head++;
+ if (head < this.end)
+ for (int ptr = 0, node = head; (node != head) || (ptr == 0);)
+£>else
+ for (int ptr = 0, node = this.head; node != EDGE;)
+£>fi
+ {
+ vals[ptr++] = this.values[node];
+ node = this.next[node];
+ }
+
+ if (cap != this.capacity)
+ {
+ this.reusable = new int[cap];
+ this.next = new int[cap];
+£>(( with_prev )) &&
+ this.previous = new int[cap];
+ }
+
+ for (int i = 0; i < size;)
+ this.next[i] = ++i;
+ this.next[size - 1] = EDGE;
+
+£>if (( with_prev )); then
+ for (int i = 0; i < size; i++)
+ this.previous[i] = i - 1;
+£>fi
+
+ this.values = vals;
+ this.end = size;
+ this.reuseHead = 0;
+£>(( with_head )) &&
+ this.head = 0;
+£>(( with_tail )) &&
+ this.tail = this.end - 1;
+ }
+
+
+ /**
+ * Gets the next free position, and grow the
+ * arrays if necessary. This methods has constant
+ * amortised time complexity.
+ *
+ * @return The next free position
+ */
+ @SuppressWarnings("unchecked")
+ private int getNext()
+ {
+ if (this.reuseHead > 0)
+ return this.reusable[--this.reuseHead];
+ if (this.end == this.capacity)
+ {
+ this.capacity >>= 1;
+ System.arraycopy(this.values, 0, this.values = (T[])(new Object[this.capacity]), 0, this.end);
+ System.arraycopy(this.reusable, 0, this.reusable = new int[this.capacity], 0, this.end);
+ System.arraycopy(this.next, 0, this.next = new int[this.capacity], 0, this.end);
+£>(( with_prev )) &&
+ System.arraycopy(this.previous, 0, this.previous = new int[this.capacity], 0, this.end);
+ }
+ return this.end++;
+ }
+
+
+ /**
+ * Mark a position as unused
+ *
+ * @param node The position
+ * @return The position
+ */
+ private int unuse(int node)
+ {
+ this.reusable[reuseHead++] = node;
+ this.next[node] = UNUSED;
+£>(( with_prev )) &&
+ this.previous[node] = UNUSED;
+ return node;
+ }
+
+
+£>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 int create(T value)
+ {
+ int node = getNext();
+ this.values[node] = value;
+£>(( with_prev )) &&
+ this.previous[node] = node;
+ return this.next[node] = node;
+ }
+£>fi
+
+
+£>if (( with_head )); then
+ /**
+ * Insert a value in the beginning of the list.
+ * This methods has constant amortised time complexity.
+ *
+ * @param value The value to insert
+ * @return The node that has been created and inserted
+ */
+ public int insertBeginning(T value)
+ {
+ int node = getNext();
+ this.values[node] = value;
+ this.next[node] = this.head;
+£>if (( with_prev )); then
+ if (this.next[node] != EDGE)
+ this.previous[this.next[node]] = node;
+£>fi
+£>if (( with_tail )); then
+ if (this.head == EDGE)
+ this.tail = node;
+£>fi
+ this.head = node;
+ return node;
+ }
+
+ /**
+ * Remove the node at the beginning of the list.
+ * This methods has constant time complexity.
+ *
+ * @return The node that has been removed
+ */
+ public int removeBeginning()
+ {
+ int node = this.head;
+ if (node != EDGE)
+ this.head = this.next[this.head];
+£>if (( with_prev )); then
+ if (this.head != EDGE)
+ this.previous[this.head] = EDGE;
+£>fi
+£>if (( with_tail )); then
+ if (this.tail == node)
+ this.tail = EDGE;
+£>fi
+ return unuse(node);
+ }
+£>fi
+
+
+ /**
+ * Insert a value after a specified, reference, node.
+ * This methods has constant amortised time complexity.
+ *
+ * @param value The value to insert
+ * @param predecessor The reference node
+ * @return The node that has been created and inserted
+ */
+ public int insertAfter(T value, int predecessor)
+ {
+ int node = getNext();
+ this.values[node] = value;
+ this.next[node] = this.next[predecessor];
+ this.next[predecessor] = node;
+£>if (( with_prev )); then
+ this.previous[node] = predecessor;
+ if (this.next[node] != EDGE)
+ this.previous[this.next[node]] = node;
+£>fi
+£>if (( with_tail )); then
+ if (this.tail == predecessor)
+ this.tail = node;
+£>fi
+ return node;
+ }
+
+ /**
+ * Remove the node after a specified, reference, node.
+ * This methods has constant time complexity.
+ *
+ * @param predecessor The reference node
+ * @return The node that has been removed
+ */
+ public int removeAfter(int predecessor)
+ {
+ int node = this.next[predecessor];
+ if (node == EDGE)
+ this.next[predecessor] = this.next[node];
+£>if (( with_prev )); then
+ else if (this.next[node] != EDGE)
+ this.previous[this.next[node]] = predecessor;
+£>fi
+£>if (( with_tail )); then
+ if (this.tail == node)
+ this.tail = predecessor;
+£>fi
+ return unuse(node);
+ }
+
+
+£>if (( with_prev )); then
+ /**
+ * Insert a value before a specified, reference, node.
+ * This methods has constant amortised time complexity.
+ *
+ * @param value The value to insert
+ * @param successor The reference node
+ * @return The node that has been created and inserted
+ */
+ public int insertBefore(T value, int successor)
+ {
+ int node = getNext();
+ this.values[node] = value;
+ this.previous[node] = this.previous[successor];
+ this.previous[successor] = node;
+ this.next[node] = successor;
+ if (this.previous[node] != EDGE)
+ this.next[this.previous[node]] = node;
+£>if (( with_head )); then
+ if (this.head == successor)
+ this.head = node;
+£>fi
+ return node;
+ }
+
+ /**
+ * Remove the node before a specified, reference, node.
+ * This methods has constant time complexity.
+ *
+ * @param successor The reference node
+ * @return The node that has been removed
+ */
+ public int removeBefore(int successor)
+ {
+ int node = this.previous[successor];
+ if (node == EDGE)
+ this.previous[successor] = this.previous[node];
+ else if (this.previous[node] != EDGE)
+ this.next[this.previous[node]] = successor;
+£>if (( with_head )); then
+ if (this.head == node)
+ this.head = successor;
+£>fi
+ return unuse(node);
+ }
+
+
+ /**
+ * Remove the node from the list.
+ * This methods has constant time complexity.
+ *
+ * @param node The node to remove
+ */
+ public void remove(int node)
+ {
+ if (this.previous[node] != EDGE)
+ this.next[this.previous[node]] = this.next[node];
+£>if (( with_head )); then
+ else
+ this.head = this.next[node];
+£>fi
+ if (this.next[node] != EDGE)
+ this.previous[this.next[node]] = this.previous[node];
+£>if (( with_tail )); then
+ else
+ this.tail = this.previous[node];
+£>fi
+ unuse(node);
+ }
+£>fi
+
+
+£>if (( with_tail )); then
+ /**
+ * Insert a value in the end of the list.
+ * This methods has constant amortised time complexity.
+ *
+ * @param value The value to insert
+ * @return The node that has been created and inserted
+ */
+ public int insertEnd(T value)
+ {
+ if (this.tail == EDGE)
+£>(( with_head )) &&
+ return insertBeginning(value);
+£>(( with_head )) ||
+ return this.values[this.tail = getNext()] = value;
+ return insertAfter(value, this.tail);
+ }
+
+£>if (( with_prev )); then
+ /**
+ * Remove the node at the end of the list.
+ * This methods has constant time complexity.
+ *
+ * @return The node that has been removed
+ */
+ public int removeEnd()
+ {
+ int node = this.tail;
+ if (node != EDGE)
+ this.next[this.tail = this.previous[node]] = EDGE;
+ return unuse(node);
+ }
+£>fi
+£>fi
+
+}
+