LINUX.ORG.RU
решено Форум — Development  

java - как устроен LinkedList?

 


0

1

Привет,

как синтаксически устроен linkedlist?

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/...

Каждый узел - объект - содержащий поля - значения и ссылки на предыдущий и последующий элементы, но как это закодить?

Т.е. как при создании нового node обновить предыдущий узел?



Последнее исправление: cetjs2 (всего исправлений: 1)
← Latex Ширина таблицы
Iterate Haskell →

Каждый узел - объект - содержащий поля - значения и ссылки на предыдущий и последующий элементы

Что не понятного?

Т.е. как при создании нового node обновить предыдущий узел?

Опять же что не понтного? 

prev.setNext(this);
next.setPrev(this);

invy ★★★★★
()

как это закодить

Читаешь описание и пишешь постепенно …

Можешь почитать это.

P.S. по хорошему прочти кормена.

jetuuuu
()
Ответ на: комментарий от invy 
class CustomLinkedList <T> implements CustomList <T> {
    static int counter = -1;

    class Node {
        public Node previous;
        public Node next;

        int number;
        T value;

        Node(T value) {
            this.value = value;
            number = counter;
            counter++;
        }
    }

    Node first = new Node(null);

    Node getLatest() {
        Node temp = first;
        while(temp == null) {
            temp = temp.next;
        }
        return temp;
    }

    public void add(T value) {
        Node latest = this.getLatest();
        latest.next = new Node(value);
        Node current = latest.next;
        current.previous = latest;
    }

    @Override
    public String toString() {
        String representation = "";
        Node temp = first;
        while(temp == null) {
            temp = temp.next;
            representation = representation + temp.value;
        }

        return representation;
    }
}

Примерно так?

misanthropy
() автор топика
Ответ на: комментарий от misanthropy 
public class Runner {
    public static void main(String...args) {
        CustomLinkedList list = new CustomLinkedList();
        for(int i = 0; i <= 32; i++) {
            list.add(i);
        }
        System.out.println(list.toString());
    }
}

Ничего не выводит.

misanthropy
() автор топика
Ответ на: комментарий от deadNightTiger 
class CustomLinkedList <T> implements CustomList <T> {
    static int counter = -1;

    class Node {
        public Node previous;
        public Node next;

        int number;
        T value;

        Node(T value) {
            this.value = value;
            number = counter;
            counter++;
        }
    }

    Node first = new Node(null);

    Node getLatest() {
        Node temp = first;
        while(temp != null) {
            temp = temp.next;
        }
        return temp;
    }

    public void add(T value) {
        Node latest = this.getLatest();
        latest.next = new Node(value);
        Node current = latest.next;
        current.previous = latest;
    }

    @Override
    public String toString() {
        String representation = "";
        Node temp = first;
        while(temp != null) {
            representation = representation + temp.value;
            temp = temp.next;
        }

        return representation;
    }
}

Exception in thread "main" java.lang.NullPointerException
	at CustomLinkedList.add(CustomLinkedList.java:37)
	at Runner.main(Runner.java:10)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)
misanthropy
() автор топика
Ответ на: комментарий от deadNightTiger 
class CustomLinkedList <T> implements CustomList <T> {
    static int counter = -1;

    class Node {
        public Node previous = null;
        public Node next = null;

        int number;
        T value;

        Node(T value) {
            this.value = value;
            number = counter;
            counter++;
        }
    }

    Node first = new Node(null);

    Node getLatest() {
        Node temp = first;
        while(temp.next != null) {
            temp = temp.next;
        }
        return temp;
    }

    public void add(T value) {
        Node latest = this.getLatest();
        latest.next = new Node(value);
        Node current = latest.next;
        current.previous = latest;
    }

    @Override
    public String toString() {
        String representation = "";
        Node temp = first;
        while(temp.next != null) {
            representation = representation + " " +temp.value;
            temp = temp.next;
        }

        return representation;
    }
}

Выводит null 0 1 2 ... Осталось разобраться, откуда null.

misanthropy
() автор топика
Ответ на: комментарий от misanthropy

Запускаю так 

public class Runner {
    public static void main(String...args) {
        System.out.println("Runner has been started.");
        CustomLinkedList list = new CustomLinkedList();
        for(int i = 0; i <= 32; i++) {
            list.add(i);
        }
        System.out.println(list.toString());
    }
}

misanthropy
() автор топика
Ответ на: комментарий от deadNightTiger 
    public void add(T value) {
        if (counter == -1) {
            first.value = value;
        }
        else {
            Node latest = this.getLatest();
            latest.next = new Node(value);
            Node current = latest.next;
            current.previous = latest;
        }
    }

Всё равно первый null

misanthropy
() автор топика
Ответ на: комментарий от misanthropy

Когда ты создаешь класс, у тебя появляется Node first = new Node(null);, в конструкторе делается counter++, следовательно, в ветку counter == -1 ты никогда не попадаешь. Вообще, имхо, first семантически правильнее инициализировать null-ом.

А еще непонятно, зачем counter - static

deadNightTiger ★★★★★
()
Последнее исправление: deadNightTiger (всего исправлений: 1)
Ответ на: комментарий от deadNightTiger

Большое спасибо, теперь работает 

class CustomLinkedList <T> implements CustomList <T> {
    static int counter = -1;

    class Node {
        public Node previous = null;
        public Node next = null;

        int number;
        T value;

        Node(T value) {
            this.value = value;
            number = counter;
            counter++;
        }
    }

    Node first = null;

    Node getLatest() {
        Node temp = first;
        while(temp.next != null) {
            temp = temp.next;
        }
        System.out.println(temp.value);
        return temp;
    }

    public void add(T value) {
        if (counter == -1) {
            first = new Node(value);
        }
        else {
            Node latest = this.getLatest();
            latest.next = new Node(value);

            Node current = latest.next;
            current.previous = latest;
        }
    }

    @Override
    public String toString() {
        String representation = "";
        Node temp = first;
        while(temp.next != null) {
            representation = representation + " " + temp.value;
            temp = temp.next;
        }

        return representation;
    }
}

Статический счётчик используется для нумерации nod-ов списка. Он должен быть общим для всех, и поэтому - статическим.

Или я не прав?

misanthropy
() автор топика
Ответ на: комментарий от deadNightTiger

Я об этом не подумал.

осталось несколько проблем - в список не добавляется последний элемент и не работает remove. 

class CustomLinkedList <T> implements CustomList <T> {
    int counter = 1;

    class Node {
        public Node previous = null;
        public Node next = null;

        int number;
        T value;

        Node(T value) {
            this.value = value;
            number = counter;
            counter++;
        }
    }

    Node first = null;

    Node getLatest() {
        Node temp = first;
        while(temp.next != null) {
            temp = temp.next;
        }
        return temp;
    }

    public void add(T value) {
        if (counter == 1) {
            first = new Node(value);
        }
        else {
            Node latest = this.getLatest();
            latest.next = new Node(value);

            Node current = latest.next;
            current.previous = latest;
        }
    }

    public boolean remove(T value) {
        Node temp = first;
        while(temp.next != null) {
            if (temp.value == value) {
                temp.previous = temp.next;
                return true;
            }
            temp = temp.next;

            if (temp.next == value) {
                temp.previous = temp.next;
                return true;
            }
        }

        return false;
    }

    @Override
    public String toString() {
        String representation = "";
        Node temp = first;
        while(temp.next != null) {
            representation = representation + " " + temp.value;
            temp = temp.next;
        }

        return representation;
    }
}


public class Runner {
    public static void main(String...args) {
        CustomLinkedList list = new CustomLinkedList();
        for(int i = 1; i <= 32; i++) {
            list.add(i);
        }
        list.remove(5);
        System.out.println(list.toString());
    }
}
misanthropy
() автор топика
Ответ на: комментарий от deadNightTiger 
    public boolean remove(T value) {
        Node temp = first;
        while(temp.next != null) {
            if (temp.value == value) {
                temp.previous = temp.next;
                return true;
            }
            if (temp.next != null && temp.value == value) {
                temp.previous = temp.next;
                return true;
            }
            temp = temp.next;
        }

        return false;
    }

Где здесь может быть ошибка, можешь подсказать?

misanthropy
() автор топика
Ответ на: комментарий от misanthropy

переписал remove метод 

    public boolean remove(T value) {
        Node temp = first;
        while(temp.next != null) {
            if(temp.value == value) {
                temp.previous = temp.next;
            }
            if(temp.next.value == value) {
                temp.previous = temp.next;
            }
            temp = temp.next;
        }
        return false;
    }

misanthropy
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Latex Ширина таблицы
Development
Iterate Haskell →