Односвязный список, реализованный на массиве (Java)

Question

мне дали задание, реализовать односвязный список на массиве. Я написал свой код, но без массива , не могу понять как сделать его на массиве. Код прикреплю ниже.

 class ListElement {
    ListElement next;
    int data;
}
 class List {
     private ListElement front;
     private ListElement rear;

     void addFront(int data) {
         ListElement a = new ListElement();
         a.data = data;
         if (front == null) {
             front = a;
             rear = a;
         } else {
             a.next = front;
             front = a;
         }

     }

      void addBack(int data) {
         ListElement a = new ListElement();
         a.data = data;
         if (rear == null) {
             front = a;
             rear = a;
         } else {
             rear.next = a;
             rear = a;
         }
     }

     void showElem() {
         ListElement t = front;
         while (t != null) {
             System.out.print(t.data + " ");
             t = t.next;
         }
     }

     void delElem(int data) {
         if (front == null)
             return;
         if (front == rear) {
             front = null;
             rear = null;
             return;
         }
         if (front.data == data) {
             front = front.next;
             return;
         }
         ListElement t = front;
         while (t.next != null) {
             if (t.next.data == data) {
                 if (rear == t.next) {
                     rear = t;
                 }
                 t.next = t.next.next;
                 return;
             }
             t = t.next;
         }
     }
 }

Answer 1

Текущая реализация использует кучу для хранения узлов списка. Это подразумевает:

создание новых узлов с помощью new ListElement(...)
хранение ссылки на голову/хвост/следующий элемент в виде собственно встроенной ссылки

Реализация с помощью массива предполагает хранение узлов в массиве и замену ссылок на индексы массива. Тогда у вас узел будет выглядеть так:

class ListElement {
    int nextElementIndex;
    int data;
}

Ну и сам список:

class List {
     private ListElement[] elements;
     private int frontIndex;
     private int rearIndex;

Теперь нужно:

во всех функциях заменить доступ к голове/хвосту/следующему на доступ по индексу к elements.
заменить new ListElement(...) на поиск незанятого элемента в массиве.

БЛОГ НА HUSL

Односвязный список, реализованный на массиве (Java)

Ответы (1 шт):