Реализация пользовательского LinkedArrayList с расширением AbstractList

Определение проблемы

  • Мне нужна коллекция, которая имеет узлы, и каждый узел имеет частично заполненный массив постоянного размера. Каждый массив может содержать различный размер, если он меньше ранее определенного постоянного размера. Там будет список этих узлов.

Например :

  • Когда требуется добавить элемент в список, list добавляет элемент в первый соответствующий узел, который не заполнен. Если я постоянно добавляю (1) , добавить (2) , добавить (3) , добавить (4) , добавить (1) , список будет показан так:
  • Предположим, DEFAULT_NODE_CAPACITY = 3
    • узел-0 -> "123"
    • узел-1 -> "41"

  • Когда требуется удалить элемент из списка, list удаляет элемент из первого соответствующего узла, который содержит и соответствует данному элементу. Если я удалю (1) из списка, список будет показан так:
    • узел-0 -> "23"
    • узел-1 -> "41"

Что я пробовал?

  • Я рассмотрел использование внутреннего класса, который является статическим, потому что класс узла не должен обращаться к полям и методам внешнего класса. Все типы должны быть универсальными, поэтому я поместил значение универсального ключа, идентичное для каждого конструктора.
  • Критическим моментом было то, что мне пришлось использовать класс AbstractList в моей пользовательской коллекции. В этот момент я действительно путаюсь с тем, какую структуру я буду использовать для вызова класса узла, который имеет частично фиксированный массив.

Вопросы

  • Как я могу переопределить методы AbstractList, которые соответствуют моему внутреннему классу узла. Когда я читаю Документацию по Java API , для создания модифицируемых мне просто нужно переопределить

    • получить()
    • задавать()
    • Удалить()
    • добавлять()
    • size () на этом этапе, как я могу эффективно переопределить их все, соответствуя моему определению проблемы?
  • Какой тип данных мне следует использовать для вызова Node<E> ? и как можно это реализовать?


Как я реализовал?

package edu.gtu.util;

import java.util.AbstractList;
import java.util.Collection;
import java.util.List;

public class LinkedArrayList<E> extends AbstractList<E>
        implements List<E> , Collection<E>, Iterable<E> {

    public static final int DEFAULT_CAPACITY = 10;
    public static final int CONSTANT_NODE_CAPACITY = 3;

    /* Is that wrong ? , how to be conformed to AbstractList ? */
    private Node<E>[] listOfNode = null;
    /*---------------------------------------------------------*/

    private int size;

    private static class Node<E> {

        private Object[] data;
        private Node<E> next = null;
        private Node<E> previous = null;

        private Node( Object[] data , Node<E> next , Node<E> previous ) {

            setData(data);
            setNext(next);
            setPrevious(previous);

        }

        private Node( Object[] data ) {
            this( data , null , null );
        }

        private void setData( Object[] data ) {
            this.data = data;
        }
        private void setNext( Node<E> next ) {
            this.next = next;
        }
        private void setPrevious( Node<E> previous ) {
            this.previous = previous;
        }

        private Object[] getData() {
            return data;
        }
        private Node<E> getNext() {
            return next;
        }
        private Node<E> getPrevious() {
            return previous;
        }

    }


    private void setSize( int size ) {
        this.size = size;
    }

    public LinkedArrayList() {
        super();
    }

    public LinkedArrayList( int size ) {
        super();

        setSize( size );
        listOfNode = (Node<E>[]) new Object[size()];
    }

    public LinkedArrayList(Collection<E> collection ) {
        super();
    }

    @Override
    public E get( int i ) {
    }

    @Override
    public boolean add(E e) {
        return super.add(e);
    }

    @Override
    public boolean remove(Object o) {
        return super.remove(o);
    }

    @Override
    public E set(int index, E element) {
        return super.set(index, element);
    }

    @Override
    public int size() {
        return size;
    }

}

Всего 1 ответ


Во-первых, вам нужно добавить поле в Node которое сообщит вам, сколько элементов данных хранится в этом узле.

Затем:

  • size должен перебирать узлы и вычислять сумму размеров узлов. Или вы можете сохранить отдельный размер и обновлять его при каждом добавлении и удалении.

  • add должен найти узел, в который можно вставить элемент. Если в этом узле есть место, просто добавьте его туда. Если этот узел заполнен, вы должны создать новый узел.

  • remove должен найти правильный узел и удалить элемент из этого узла. Если узел становится пустым, сам узел можно удалить.

  • get должен перебирать узлы, отслеживая, сколько элементов он пропускает, пока не найдет узел, который должен содержать узел.

  • set - аналогично get , за исключением того, что он заменяет элемент в дополнение к его возврату

Вы найдете лучшие описания в Википедии: https://en.wikipedia.org/wiki/Unrolled_linked_list В этой статье также предлагается важная оптимизация для добавления / удаления.


Есть идеи?

10000