среда, 1 августа 2012 г.

datastructure: single-linked-list

----------------------------------------------------------------
-- Код:
Какое значение будет у sum после выполнения кода:
public class DynamicDataStructureTest {
    public static void main(String[] args) {
        Node tail = new Node(1, new Node(2, new Node(3, null)));
        int sum = 0;
        while (tail != null) {
            sum = 1000 * sum + tail.value;
            tail = tail.next;
        }
        System.out.println(sum);
    }
}

class Node {
    int value;
    Node next;
    Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}
-- Вопросы/задания:
1) Что выведет данная программа при запуске?
2) Конструкция 
new Node(1, new Node(2, new Node(3, null)))
создала односвязный список из 3-х элементов. Напишите цикл for, создающий односвязный список из 1000 элементов.
-- Словарь: 
Динамическая структура данных, односвязный список, перебор элементов односвязного списка.
-- Примечание: 
Данный код упрощенно демонстрирует структуру данных "односвязный список". В библиотеке коллекций присутствует такой класс как java.util.LinkedList - это структура данных "двусвязный список". Упрощенную модель вы можете посмотреть на странице, посвященной LinkedList.

----------Генерация односвязного списка произвольной длины----------
-- Код:


public class TestLinkedList {
    public static void main(String[] args) {
        println(LLTailGenerator.generate(10));
        println(LLHeadGeneratorRememberHead.generate(10));
        println(LLHeadGeneratorLookForHead.generate(10));
    }
    private static void println(Node node) {
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }
}



class Node {

    int value;
    Node next;

    Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}

class LLTailGenerator {
    public static Node generate(int len) {
        Node tail = null;
        for (int k = len - 1; k >= 0; k--) {
            tail = new Node(k, tail);
        }
        return tail;
    }
}

class LLHeadGeneratorRememberHead {
    public static Node generate(int len) {
        // remember head reference
        Node head = new Node(0, null);
        Node tail = head;
        for (int k = 1; k < len; k++) {
            // add node
            head.next = new Node(k, null);
            // update head reference
            head = head.next;
        }
        return tail;
    }
}

class LLHeadGeneratorLookForHead {
    public static Node generate(int len) {
        Node tail = new Node(0, null);
        for (int k = 1; k < len; k++) {
            // look for head
            Node head = tail;
            while (head.next != null) {
                head = head.next;
            }
            // add node
            head.next = new Node(k, null);
        }
        return tail;
    }
}
-- Вопросы/задания:
1) Почему у класса LLTailGenerator обратный порядок for 
    for (int k = len - 1; k >= 0; k--)?
2) И LLHeadGeneratorRememberHead и LLHeadGeneratorLookForHead добавляют элементы с "головы", так в чем же разница?