Премини към съдържанието
questions

Свързан списък - динамична реализация

Препоръчан отговор


Здравейте. Чета по темата със свързаните списъци и имам нещо, което не ми е ясно. Взел съм примера от книга, която чета. Мястото, което не разбирам е там където добавяме елемент. Този списък освен, че трябва да пази сойността на елемента, трябва да пази и референция към следващия елемент. Но като погледнах метода add като параметри в конструктора на Node класа се добавят новия елемент и tail-а, който е последния елемент, което значи че последния сочи към предпоследния (1<-2<-3<-4<-5 ), а би трябвало да е обратно (1->2->3->4->5 ). Моля някой да ми обясни правилно ли разбирам сегашния пример и като цяло концепцията дали е тази.

public class DynamicList {

    private class Node {

     Object element;
     Node next;

     Node(Object element, Node next) {
                this.element = element;
                this.next = next;
     }

     Node(Object element) {
            this.element = element;
            this.next = null;
     }

    }

    private Node head;
    private Node tail;
    private int count;

    public DynamicList() {
        this.head = null;
        this.tail = null;
        this.count = 0;
    }

    /**
     * Add element at the end of the list
     * @param item - the element you want to add
     */
    public void add(Object item) {
        if (head == null) {
            // We have empty list
            head = new Node(item);
            tail = head;
        } else {
            // We have non-empty list
            Node newNode = new Node(item, tail);
            tail = newNode;
        }
        count++;
    }

    /**
     * Removes and returns element on the specific index
     * @param index - the index of the element you want to remove
     * @return the removed element
     * @exception IndexOutOfBoundsException - when index is invalid
     */

    public Object remove(int index) {
        if (index >= count || index < 0) {
            throw new IndexOutOfBoundsException(
                    "Invalid index: " + index);
        }

        // Find the element at the specified index
        int currentIndex = 0;
        Node currentNode = head;
        Node prevNode = null;
        while (currentIndex < index) {
            prevNode = currentNode;
            currentNode = currentNode.next;
            currentIndex++;
        }

        // Remove the element
        count--;
        if (count == 0) {
            head = null;
            tail = null;
        } else if (prevNode == null) {
            head = currentNode.next;
        } else {
            prevNode.next = currentNode.next;
        }

        return currentNode.element;
    }

    /**
     * Removes the specified item and return its index
     * @param item – the item for removal
     * @return the index of the element or -1 if does not exist
     */

    public int remove(Object item) {
        // Find the element containing searched item
        int currentIndex = 0;
        Node currentNode = head;
        Node prevNode = null;
        while (currentNode != null) {
            if ((currentNode.element != null &&
                    currentNode.element.equals(item)) ||
                    (currentNode.element == null) && (item == null)) {
                break;
            }
            prevNode = currentNode;
            currentNode = currentNode.next;
            currentIndex++;
        }

        if (currentNode != null) {
            // Element is found in the list. Remove it
            count--;
            if (count == 0) {
                head = null;
                tail = null;
            } else if (prevNode == null) {
                head = currentNode.next;
            } else {
                prevNode.next = currentNode.next;
            }

            return currentIndex;
        } else {
            // Element is not found in the list
            return -1;
        }
    }

    /**
     * Searches for given element in the list
     * @param item - the item you are searching for
     * @return the index of the first occurrence of
     * the element in the list or -1 when not found
     */

    public int indexOf(Object item) {
        int index = 0;
        Node current = head;
        while (current != null) {
            if ((current.element!=null && current.element.equals(item))
                    || (current.element==null) && (item==null)) {
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;
    }

    /**
     * Check if the specified element exist in the list
     * @param item - the item you are searching for
     * @return true if the element exist or false otherwise
     */

    public boolean contains(Object item) {
        int index = indexOf(item);
        boolean found = (index != -1);
        return found;
    }

    /**
     * @param index – the position of the element [0 ... count-1]
     * @return the object at the specified index
     * @exception IndexOutOfBoundsException - when index is invalid
     */

    public Object elementAt(int index) {
        if (index>=count || index<0) {
            throw new IndexOutOfBoundsException(
                    "Invalid index: " + index);
        }
        Node currentNode = this.head;
        for (int i = 0; i < index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode.element;
    }

    /**
     * @return the actual list length
     */
    public int getLength() {
        return count;
    }

}

 

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

преди 8 часа, questions написа:

Здравейте. Чета по темата със свързаните списъци и имам нещо, което не ми е ясно. Взел съм примера от книга, която чета. Мястото, което не разбирам е там където добавяме елемент. Този списък освен, че трябва да пази сойността на елемента, трябва да пази и референция към следващия елемент. Но като погледнах метода add като параметри в конструктора на Node класа се добавят новия елемент и tail-а, който е последния елемент, което значи че последния сочи към предпоследния (1<-2<-3<-4<-5 ), а би трябвало да е обратно (1->2->3->4->5 ). Моля някой да ми обясни правилно ли разбирам сегашния пример и като цяло концепцията дали е тази.

Здравейте !
Проблем съществува в кода и той се намира в този конструктор:

 Node(Object element, Node next) {
     this.element = element;
     this.next = next; // <--- Тука става проблема. Трябва да се замени със следното: next.next = this;
 }

Правилно сте разбрали концепцията и много точно отбелязвате, че посоката на chain-ване (т.е. на закачане на елементи) трябва да сочи надясно. 

Tail елемента единствено спомага в случая да се спести търсене на последния елемент, за да се добави нов, което има резон. Освен това, друга функция, той не изпълнява.

Ще приложа малко по-разширен вариант на класа с принтиране, което да помогне за тестване и наблюдения :) (възможно е да се наложи да промените името на пакета на файла).

DynamicList.java

P.S. В реалната реализация на LinkedList-а, посоката е двупосочна - фактически се ползва Deque (Deck) вместо Queue (Deque = Double-Ended Queue). Там наистина се правят манипулации от двете страни и се поддържа основно с цел да се подобри търсенето и прекия достъп по индекс (които са основните минуси на LinkedList-а спрямо ArrayList-а). Реализацията му е доста дебела, поради което Ви препоръчвам добре да се запознаете и с двата вида най-често използвани списъка, преди да задълбавате в JRE имплементациите им :) .

Поздрави !

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Да сера разбрах. Със next.next = this, оказваме че новия елемент, който добавяме (this или this.element) ще отговаря на next полето от Node класа.
Като стана на дума за имплементацията на LinkedList, да наистина е доста дебела и не мисля, че я разбирам, чисто като имплементация след като отворя самия клас, иначе знам как работи, но дали е достатъчно не знам.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Пробвах се да резлизирам двусвързан списък, на който елементите да сочат към предходния и към следващия. Дебъгвам го и виждам, че се така са записани, но като се пробвам да ги принтирам получавам nullpointer-и. Добавям и една снимка, по която съдя, че елементите са добавени в желания ред. 

public class MultiDynamicList {

    public static void main(String[] args) {

        MultiDynamicList d = new MultiDynamicList();
        d.add(1);d.add(2);d.add(3);d.add(4);
        d.printItems();

    }

    private class Node {

        Object element;
        Node previous;
        Node next;

        public Node(Object element, Node previous, Node next) {
            this.element = element;
            this.previous = previous;
            next.next = this;
        }

        public Node(Object element) {
            this.element = element;
            this.previous = null;
            this.next = null;
        }

    }

    private Node head;
    private Node tail;
    private int count;

    public MultiDynamicList() {
        this.head = null;
        this.tail = null;
        this.count = 0;
    }


    public void add(Object element) {

        if(head == null) {
            head = new Node(element);
            head.previous = null;
            head.next = null;
            tail = head;
        } else {
            Node node = new Node(element, tail, tail);
            tail = node;
        }
        count ++;
    }

    public void printItems() {
        MultiDynamicList.Node iterator = head;
        if (iterator == null) {
            System.out.println("[]");
        } else {
            while (iterator != null) {
                System.out.println();
                System.out.print("[ previous: " + iterator.previous.previous.element + "] [ element: " + iterator.element + "] [ next: " + iterator.next.next.element);
                iterator = iterator.next;
            }
            System.out.print("NULL");
            System.out.println();
        }
    }


}

 

list.png

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
преди 3 часа, questions написа:

System.out.print("[ previous: " + iterator.previous.previous.element + "] [ element: " + iterator.element + "] [ next: " + iterator.next.next.element);

Този подход е опасен - в случай, че нямаме предишен (т.е. iterator е първия елемент) или нямаме следващ (т.е. iterator е на последния елемент), как ще имаме iterator.next или iterator.previous ?
В случая, преди приниране, ще трябва да се направи проверка - дали реално имаме предишен и следващ елемент спрямо текущия. 

В текущия си код, iterator.next е следващия, докато iterator.next.next е по-следващия - това означава, че принтираните стойности за previous и next ще са всъщност по-предходен и по-следващ ... няма логика в това ...

Променете следния код:

преди 3 часа, questions написа:

while (iterator != null) { 
    System.out.println(); 
    System.out.print("[ previous: " + iterator.previous.previous.element + "] [ element: " + iterator.element + "] [ next: " + iterator.next.next.element); 
    iterator = iterator.next; }

 

по този начин (Малко повече System.out.print() обръщения, за да се разбира какво става :) ):

while (iterator != null) {
	Node previous = iterator.previous;
	Node next = iterator.next;
	System.out.print("[previous: " + (previous != null ? previous.element : "NULL") + "]");
	System.out.print("[element: " + iterator.element + "] ");
	System.out.print("[next: " + (next != null ? next.element : "NULL") + "]");
	System.out.println();
	iterator = iterator.next;
}

Поздрави !


  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Здравейте отново!

Този път показвам кода малко по-различно, за да е по четим поста(поне така се надявам)

Може ли да погледнете имплементациите, които направих и ако имам неточности или пък не съм се справил изобщо да коментирате. Благодаря предварително!
статичен стек - https://pastebin.com/zHEAW2JD

свързан стек - https://pastebin.com/R0MXF2ii

 

Добавих и имплементация на опашка
статична опашка - https://pastebin.com/LVxwZwcu

свързана опашка - https://pastebin.com/uBUVcYqK

 

Имам проблем със метода за премахване на елемент както и не можах да напиша метод за зануляване на структурата.

Редактирано от questions (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Здравейте !

Прикачавам коментари по нещата за стековите имплементации. 

След като прегледах и опашките, нещата важат и за тях.

Утре, ако успея да намеря малко време, ще Ви разпиша няколко версии на стековете и опашките, по отношение на коментарите, които да ползвате като референции.

Поздрави !

DynamicStack.java

StatickStack.java

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Супер ! Благодаря за отделеното време. Дано имате време, за да видя какво пропускам в имплементациите.

Редактирано от questions (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Регистрирайте се или влезете в профила си за да коментирате

Трябва да имате регистрация за да може да коментирате това

Регистрирайте се

Създайте нова регистрация в нашия форум. Лесно е!

Нова регистрация

Вход

Имате регистрация? Влезте от тук.

Вход

×

Информация

Поставихме бисквитки на устройството ви за най-добро потребителско изживяване. Можете да промените настройките си за бисквитки, или в противен случай приемаме, че сте съгласни с нашите условия за ползване.