I would define them as the interface they provide, including complexity of the operations.
One could after all implement a linked list with an array and vice versa (and recursivly), but it would be impossible to keep the complexity.
Update: To clarify: A stack is defined as a datastructure with constant-time add to top, and constant-time remove at top. It doesn't say how we implement it.
One could implement it using an array, or a linked list, but also a double linked list, but that is irrelevant.
The atomic we have on a computer is (binary) memmory, and the most basic form of memmory is an array, thus one can create every kind of datastructure using an array.
One could imagine we had another atomic (maybe a qubit). Then a stack would still be a stack, but maybe we couldn't implement it with that atomic.
Data is now (after parsing) stored in just a list, searching for a specific peace of data is not very well optimized. Are there other structures I could use, which I can search using file(string) - level(integer) - sub-level(integer) so I can quickly get a specific data object.
Assuming that you want to search by File, Level, Sub-Level only, you have a clear hierarchical structure in that description, it sounds like you can divide one ArrayList
into multiple steps. You could even make each hierarchy level a class itself to make it more clear, for example:
class SomeFileData {
List<LevelData> levels;
}
class LevelData {
List<SubLevelData> sublevels;
}
class SubLevelData {
// Probably similar to your current `FileData` implementation
}
And if you need to save multiple files at once, you can use a Map
with the file name as key.
class LotsOfFileData {
Map<String, SomeFileData> files;
}
Using this hierarchy, you can easily get file "mydata.dat", level 3, sublevel 4.
LotsOfFileData allData;
allData.getFile("mydata.dat").getLevel(3).getSublevel(4)
Each step in the get
process looks at the current class' list or map to retrieve the data.
By the way, declare variables according to their interface, not their implementation. Declare your ArrayList
s as List
to allow for easy change of implementation.
Best Answer
Stacks and queues are ways of working with contiguous memory. Linked lists are not. Now sure, any problem that you can solve with one structure you could solve with another and slap enough abstraction on it that you couldn't tell the difference. So what's the real difference? Performance. Choosing between these structures is about what you DON'T do with them because they don't do that well.
Linked lists make insertions into their middle easy. They make traversing hard.
Stacks and queues prefer to do insertions and removal at an end.
None make it impossible to do anything since you can rebuild the entire structure. The issue is the cost that comes at.
One thing that's helped me along the way is this little guy:
Here's one that includes the less popular structures:
Under the hood it's all one big array called random access memory. Using these structures doesn't change that. But if you can predict what you don't need you can choose the right structure that will help you use that memory very well.