Data structure linked arrays

This is a hyperid implementation of a linked list and ArrayList:



The total capacity is divided into \$\sqrt{n} \text{ "arrays count"} \sqrt{n} \text{ "array size"}\$. This will lead to, as I assume, \$O(\sqrt{n})\$ for operations like indexing, insertion and deletion, along with \$O(1)\$ for adding

We start with one array and when it become filled we create another one calculating its size based on the value of the current capacity of the LinkedArrays \$\sqrt{\text{current capacity}}\$ when the full capacity is reached we increase it

Performance test time in nano seconds for 10000 operations:

Testing linked arrays...................testing ArrayList.................testing linked list

Time of adding is 349735................time of adding is 264192..........time of adding is 348790

Time of inserting is 60478240...........time of inserting is 840246516....time of inserting is 161743668

Time of delete is 54515250..............time of delete is 593944378.......time of delete is 264977066

Time of indexing is 510897..............time of indexing is 445676........time of indexing is 281091364

Time of search is 373683352.............time of search is 306989747.......time of search is 2512449873


The ArrayNode class:

`/*
* Copyright (C) 2016 Ahmed Mazher
*
* This file "ArrayNode" is part of ahmed.library.
* ahmed.library is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* ahmed.library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
package ahmed.lib.utilit

Do you need to reinvent the wheel?

class ArrayNode {

and

Object[] elements; // the array of elements

If I were doing this, I'd make it

class ArrayNode implements List {

and

List elements = new ArrayList<>();

Then you don't have to manage resizing manually and can get rid of the four int fields.

You can just pass through the List operations, as the ArrayList will know what to do with them.

But most importantly, this way you can have a normal generics implementation. You don't need to play around with casting to and from Object.

Why not List?

public class LinkedArrays implements Collection {

You have this implementing the Collection interface. Why? The operations that you are doing match the List interface. Why not implement that? You already have equivalents of most if not all of the required operations.

Why roll your own?

int arrCount;//current number of arrays
    int maxArraySize;//maximum allowed size of array
    ArrayNode head;//point to the head array
    ArrayNode tail; //point to the tail array

Why not just do

int maxArraySize;//maximum allowed size of array
    List> chunks = new LinkedList<>();

or even

int maxArraySize;//maximum allowed size of array
    List> chunks = new LinkedList<>();

Each chunk can be an ArrayList in the last version.

Then you can do the normal operations and don't have to implement your own. You don't even need to implement ArrayNode if you don't want to do so.

Why \$\mathcal{O}(\sqrt{n})\$?

You can implement a tree and get \$\mathcal{O}(\log n)\$ operations. Asymptotically, logarithmic is better than the square root.

1     1  0
4     2  2
1024 32 10

It only gets worse from there.

StackExchange Code Review Q#138882, answer score: 3