Подтемы
- бинарное дерево
Структуры данных делятся на обладающие статичной структурой и динамичной структурой.
К данным со статичной структурой относят массив и "запись" (record). Они встроены в синтаксис Java. Статичность означает, что хотя можно менять данные в структуре данных, тем не менее нельзя менять структурные свойства структуры данных. Основное структурное свойство массива - его длина. Она неизменна.
Динамические структуры данных (односвязный массив, двусвязный массив, бинарное дерево, стек, очередь, ...) в синтаксис языка не входят, но богато представлены в библиотеках (JDK).
java.util.ArrayList - "динамический массив".
java.util.LinkedList - двусвязный список.
java.util.TreeMap - бинарное сбалансированное дерево (Красно-Черное дерево).
...
"Динамический массив"
Эмуляция "динамичности" у массива.
Односвязный список
Звено:
Структуры данных делятся на обладающие статичной структурой и динамичной структурой.
К данным со статичной структурой относят массив и "запись" (record). Они встроены в синтаксис Java. Статичность означает, что хотя можно менять данные в структуре данных, тем не менее нельзя менять структурные свойства структуры данных. Основное структурное свойство массива - его длина. Она неизменна.
Динамические структуры данных (односвязный массив, двусвязный массив, бинарное дерево, стек, очередь, ...) в синтаксис языка не входят, но богато представлены в библиотеках (JDK).
java.util.ArrayList - "динамический массив".
java.util.LinkedList - двусвязный список.
java.util.TreeMap - бинарное сбалансированное дерево (Красно-Черное дерево).
...
"Динамический массив"
СИНТАКСИС: static import
ИДИОМА: вызов перегруженного (overloaded) метода с "обогащением аргументами по умолчанию"
ПРИНЦИП: косвенность
import static java.lang.System.arraycopy;
public class DynamicArray {
int[] data = {};
void add(int elem) {
add(data.length, elem);
}
void remove() {
remove(data.length - 1);
}
void add(int index, int elem) {
int[] tmp = new int[data.length + 1];
arraycopy(data, 0, tmp, 0, index);
arraycopy(data, index, tmp, index + 1, data.length - index);
tmp[index] = elem;
this.data = tmp;
}
void remove(int index) {
int[] tmp = new int[data.length - 1];
arraycopy(data, 0, tmp, 0, index);
arraycopy(data, index + 1, tmp, index, data.length - index - 1);
this.data = tmp;
}
}
Тестируем "динамический массив":
class DynamicArrayTest {
public static void main(String[] args) {
DynamicArray dynArray = new DynamicArray();
System.out.println(Arrays.toString(dynArray.data));
dynArray.add(10);
dynArray.add(20);
dynArray.add(30);
dynArray.add(40);
dynArray.add(50);
System.out.println(Arrays.toString(dynArray.data));
dynArray.remove();
System.out.println(Arrays.toString(dynArray.data));
dynArray.remove(2);
System.out.println(Arrays.toString(dynArray.data));
dynArray.add(1, 0);
System.out.println(Arrays.toString(dynArray.data));
}
}
>> []
>> [10, 20, 30, 40, 50]
>> [10, 20, 30, 40]
>> [10, 20, 40]
>> [10, 0, 20, 40]
Односвязный список
Звено:
public class Node {
public int value;
public Node next;
Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
"Ручное" создание списка (первая попытка) + итеративный перебор:
public class SingleLinkedListTest0 {
public static void main(String[] args) {
Node node0 = new Node(0, null);
Node node1 = new Node(1, null);
Node node2 = new Node(2, null);
Node node3 = new Node(3, null);
node0.next = node1;
node1.next = node2;
node2.next = node3;
Node ref = node0;
while (ref != null) {
System.out.print(" " + ref.value);
ref = ref.next;
}
}
}
>> 0 1 2 3
"Ручное" создание списка (вторая попытка) + итеративный перебор:
public class SingleLinkedListTest1 {
public static void main(String[] args) {
Node node4 = new Node(3, null);
Node node2 = new Node(2, node4);
Node node1 = new Node(1, node2);
Node node0 = new Node(0, node1);
Node ref = node0;
while (ref != null) {
System.out.print(" " + ref.value);
ref = ref.next;
}
}
}
>> 0 1 2 3
"Ручное" создание списка (третья попытка) + итеративный перебор:
public class SingleLinkedListTest2 {
public static void main(String[] args) {
Node node0 = new Node(0, new Node(1, new Node(2, new Node(3, null))));
Node ref = node0;
while (ref != null) {
System.out.print(" " + ref.value);
ref = ref.next;
}
}
}
>> 0 1 2 3
ШАБЛОН: Фабричный Метод (Factory Method)
"Ручное" создание списка (четвертая попытка) с использованием Фабричного Метода + итеративный перебор:
public class SingleLinkedListTest3 {
public static void main(String[] args) {
Node node0 = node(0, node(1, node(2, node(3, null))));
Node ref = node0;
while (ref != null) {
System.out.print(" " + ref.value);
ref = ref.next;
}
}
public static Node node(int value, Node next) {
return new Node(value, next);
}
}
>> 0 1 2 3
Итеративное создание списка + итеративный перебор:
public class SingleLinkedListTest10 {
public static void main(String[] args) {
Node tail = null;
for (int k = 0; k < 10; k++) {
tail = new Node(k, tail);
}
Node ref = tail;
while (ref != null) {
System.out.print(" " + ref.value);
ref = ref.next;
}
}
}
>> 9 8 7 6 5 4 3 2 1 0
Обратите внимание на выделенную строку - ссылка ref в левой части читается, а в правой изменяется.
Итеративное создание списка + итеративный перебор + рекурсивный перебор:
public class SingleLinkedListTest11 {
public static void main(String[] args) {
Node tail = null;
for (int k = 0; k < 10; k++) {
tail = new Node(k, tail);
}
System.out.println(toStringIter(tail));
System.out.println(toStringRec(tail));
}
public static String toStringIter(Node ref) {
String result = "";
while (ref != null) {
result += "(" + ref.value + ")->";
ref = ref.next;
}
result += "null";
return result;
}
public static String toStringRec(Node ref) {
if (ref == null) {
return "null";
} else {
return "(" + ref.value + ")->" + toStringRec(ref.next);
}
}
}
>> (9)->(8)->(7)->(6)->(5)->(4)->(3)->(2)->(1)->(0)->null
>> (9)->(8)->(7)->(6)->(5)->(4)->(3)->(2)->(1)->(0)->null
Примечание: в случае применения к "зацикленной" структуре
Node node = new Node(0, null);
node.next = node;
Итеративный перебор - упадет, съев всю память "кучи".
Рекурсивный перебор - упадет, съев всю память "стека".
Итеративное создание списка в прямом порядке + итеративное создание списка в обратном порядке + рекурсивное создание списка в прямом порядке + рекурсивное создание списка в обратном порядке + итеративный перебор + рекурсивный перебор:
public class SingleLinkedListTest12 {
public static void main(String[] args) {
Node tailA = generateIter0(9);
Node tailB = generateIter1(9);
Node tail0 = generateRec0(9);
Node tail1 = new Node(9, null); generateRec1(tail1);
System.out.println(toStringRec(tailA));
System.out.println(toStringRec(tailB));
System.out.println(toStringIter(tail0));
System.out.println(toStringIter(tail1));
}
public static Node generateIter0(int max) {
Node result = null;
for (int k = 0; k <= max; k++) {
result = new Node(k, result);
}
return result;
}
public static Node generateIter1(int max) {
Node tail = new Node(max, null);
Node head = tail;
for (int k = max; k > 0; k--) {
head.next = new Node(k - 1, null);
head = head.next;
}
return tail;
}
public static Node generateRec0(int value) {
if (value >= 0) {
return new Node(value, generateRec0(value - 1));
} else {
return null;
}
}
public static void generateRec1(Node node) {
if (node.value > 0) {
node.next = new Node(node.value - 1, null);
generateRec1(node.next);
}
}
public static String toStringIter(Node ref) {
String result = "";
while (ref != null) {
result += "(" + ref.value + ")->";
ref = ref.next;
}
result += "null";
return result;
}
public static String toStringRec(Node ref) {
if (ref == null) {
return "null";
} else {
return "(" + ref.value + ")->" + toStringRec(ref.next);
}
}
}
>> (9)->(8)->(7)->(6)->(5)->(4)->(3)->(2)->(1)->(0)->null
>> (9)->(8)->(7)->(6)->(5)->(4)->(3)->(2)->(1)->(0)->null
>> (9)->(8)->(7)->(6)->(5)->(4)->(3)->(2)->(1)->(0)->null
>> (9)->(8)->(7)->(6)->(5)->(4)->(3)->(2)->(1)->(0)->null
Дополнительные методы для работы со списками:
Лабораторныеpublic class CrazySingleLLUtils {
public static Node copy(Node tail) {
return tail == null ? null : new Node(tail.value, copy(tail.next));
}
public static boolean isEqual(Node t0, Node t1) {
if (t0 != null && t1 != null) {
return (t0.value == t1.value) && isEqual(t0.next, t1.next);
} else {
return t0 == t1;
}
}
public static Node invert(Node tail) {
if (tail == null || tail.next == null) {
return tail;
} else {
Node result = invert(tail.next);
Node ref = result;
while (ref.next != null) {ref = ref.next;}
ref.next = new Node(tail.value, null);
return result;
}
}
}
Тестирующий класс:
import static CrazySingleLLUtils.*;
public class CrazySingleLLUtilsTest {
public static void main(String[] args) {
// toString test
System.out.println(toString(copy(null)));
System.out.println(toString(copy(generate(0))));
System.out.println(toString(copy(generate(1))));
System.out.println(toString(copy(generate(2))));
System.out.println(toString(copy(generate(3))));
// isEqual test
System.out.println(isEqual(generate(3), generate(3)));
System.out.println(isEqual(generate(3), generate(4)));
System.out.println(isEqual(generate(3), null));
// invert test
System.out.println(toString(generate(3)));
System.out.println(toString(invert(generate(3))));
}
public static Node generate(int value) {
if (value >= 0) {
return new Node(value, generate(value - 1));
} else {
return null;
}
}
public static String toString(Node ref) {
if (ref == null) {
return "null";
} else {
return "(" + ref.value + ")->" + toString(ref.next);
}
}
}
>> null
>> (0)->null
>> (1)->(0)->null
>> (2)->(1)->(0)->null
>> (3)->(2)->(1)->(0)->null
>> true
>> false
>> false
>> (3)->(2)->(1)->(0)->null
>> (0)->(1)->(2)->(3)->null
