Я хочу реализовать электронную таблицу в java. Было бы лучше использовать связанный список (строки) связанного списка ячеек (столбцов) для хранения данных или хэш-карты (каждая ячейка сопоставляется с ключом, например, A1 -> 1, A2 -> 2 и т. д.)?
Или есть еще лучшая структура данных для использования?
Спасибо!
Использование Map может позволить вам искать значения быстрее и проще. Вам не нужно более одной структуры данных, достаточно одной HashMap. Например, вы можете сделать что-то вроде этого: -
public class Location {
private Integer x;
private Integer y;
public Location(Integer x, Integer y) {
this.x = x;
this.y = y;
}
// implement the equals and hashcode methods
}
public class MySpreadSheet {
private Map<Location, String> spreadsheet = new HashMap<Location, String>();
public String getCellValue(Integer x, Integer y) {
return spreadsheet.get(new Location(x, y));
}
public void setCellValue(Integer x, Integer y, String value) {
spreadsheet.put(new Location(x, y), value);
}
}
При проектировании структуры данных для таких задач проще начать с определения интерфейса для SpreadSheet. Как только все операции (операции чтения, операции создания, операции изменения и операции удаления) определены, становятся очевидными требуемые характеристики (последовательный доступ, прямой доступ и т. д.) структуры данных.
В электронной таблице потребуются механизмы для прямого доступа к столбцам, строкам или ячейкам с использованием индексов/имен, которые вызывают карту. Также потребуется последовательный доступ (итерация) по строкам и столбцам, который требует списка. Итак, интерфейс MapList — это то, что вам нужно. Теперь нам нужно выбрать реализацию. Поскольку удаление может произойти в любом месте списка строк или столбцов, реализация LinkedList кажется лучшей. Это также позволило бы выполнять операции с постоянным временем для переупорядочивания списка. Подводя итог, можно сказать, что LinkedListMap будет лучшим выбором для строк и столбцов.
Электронная таблица класса:
LinkedListMap<String,Row> rows;
// RowKey --> Row. Row has data. This allows direct access and looping.
LinkedListMap<String,Col> cols;
//only metadata - name,sort status, visible/invisible...
//This allows direct access and looping.
класс Ряд:
LinkedListMap<String,Cell> cells; //colKey --> cell
//This allows direct access and looping.
ячейка класса:
Object value;
EType dataType; //enum for data type
класс Кол:
String name;
ESortState sortState; //ASC, DESC, NONE
boolean visible;
Чтобы получить доступ к определенной ячейке из листа:
rows.get(rowKey).getValue(cells.get(colKey).getName())
С приведенными выше структурами данных вы сможете легко реализовать даже сложные операции, такие как получение подтаблицы (прямоугольный выбор).
HashMap в качестве базовой структуры данных (я говорю «базовая», потому что вы можете комбинировать несколько структур, чтобы получить наиболее оптимальное хранилище), вероятно, будет лучшим решением. Если вам нужно получить доступ к одной из ячеек и вы внедрили связанный список, потребуется время O (n) для итерации списка, чтобы добраться до этой ячейки, тогда как HashMap потребуется только время O (1) для доступа к тому, что вы хотите . То же самое касается вставок и удалений в структуру данных.
Зависит от того, что вы собираетесь делать с этой электронной таблицей - если ТОЛЬКО итерации - тогда подойдут связанные списки, но я действительно сомневаюсь, что электронная таблица необходима для этого. Для быстрого и масштабируемого доступа к ячейкам следует использовать HashMap с внутренними хеш-картами. Не забудьте предварительно задать размеры этих карт, если столбцы вашей электронной таблицы не являются динамическими и вы точно знаете их количество.
