Question About LinkedList

[Edward H. Fabrega]

My program will implement a flat file database (non-relational). I haven't
started to code yet, as I'm transitioning from C++ MFC to Java. Using MFC I
was able to do this with a linked list of StringArrays. In Java, I'm
thinking about doing it with a LinkedList of ArrayLists, where each item in
each ArrayList is a String. This will model the records. I will have a
simple ArrayList to model the column labels.

My question is: is there a better data model for a database that is
achievable with the API? A store bought component or something from a third
party API is not possible. I'm not worried about the UI at this point, only
the data.

 

[Edward H. Fabrega]

My program will implement a flat file database (non-relational). I haven't
started to code yet, as I'm transitioning from C++ MFC to Java. Using MFC
I was able to do this with a linked list of StringArrays. In Java, I'm
thinking about doing it with a LinkedList of ArrayLists, where each item
in each ArrayList is a String. This will model the records. I will have a
simple ArrayList to model the column labels.

My question is: is there a better data model for a database that is
achievable with the API? A store bought component or something from a
third party API is not possible. I'm not worried about the UI at this
point, only the data.

In my previous post, "My question is: is there a better data model for a
database that is ..."

should read: "My question is: is there a better data model for a flat file
database that is..."

 

[Edward H. Fabrega]

In my previous post, "My question is: is there a better data model for a
database that is ..."

should read: "My question is: is there a better data model for a flat file
database that is..."

One FINAL stipulation. I can't do an array of arrays because the database
must be dynamic, in the sense that records can be added, deleted, plus the
number of fields must be changeable. So I must be able to vary the size of
the ArrayLists in the LinkedList, and the size of the LinkedList itself that
is made up of the ArrayLists.

 

[Boudewijn Dijkstra]

My program will implement a flat file database (non-relational). I haven't
started to code yet, as I'm transitioning from C++ MFC to Java. Using MFC I
was able to do this with a linked list of StringArrays. In Java, I'm
thinking about doing it with a LinkedList of ArrayLists, where each item in
each ArrayList is a String. This will model the records. I will have a
simple ArrayList to model the column labels.

My question is: is there a better data model for a database that is
achievable with the API? A store bought component or something from a third
party API is not possible. I'm not worried about the UI at this point, only
the data.

It depends. For random access, LinkedList is very slow compared to ArrayList.
For adding and removing elements in a not-so-big list, LinkedList is slow
compared to ArrayList. Also, LinkedList uses more memory per element than
ArrayList.

 

[Frank]

My program will implement a flat file database (non-relational). I haven't
started to code yet, as I'm transitioning from C++ MFC to Java. Using MFC I
was able to do this with a linked list of StringArrays. In Java, I'm
thinking about doing it with a LinkedList of ArrayLists, where each item in
each ArrayList is a String. This will model the records. I will have a
simple ArrayList to model the column labels.

My question is: is there a better data model for a database that is
achievable with the API? A store bought component or something from a third
party API is not possible. I'm not worried about the UI at this point, only
the data.

What are you trying to accomplish?

Implementing a general-purpose 'database' sounds like a poor idea. If
you're trying to come up with a solution for something specific, we need
more details to give reasonable advice on data structures. How/if the
data set is manipulated at runtime, data access patterns and so on.

Read up on the collections API here:
http://java.sun.com/docs/books/tutorial/collections/index.html

-Frank

 

[John C. Bollinger]

One FINAL stipulation. I can't do an array of arrays because the database
must be dynamic, in the sense that records can be added, deleted, plus the
number of fields must be changeable. So I must be able to vary the size of
the ArrayLists in the LinkedList, and the size of the LinkedList itself that
is made up of the ArrayLists.

You have not even come close to specifying all your requirements. I
suspect that the term "database" has a very specific meaning to you, at
least in this context, but it does not illuminate us very well.
Enumerate (for yourself) all the functional requirements, and determine
how well your proposed model will handle them. If you need help with
such an evaluation then ask some more specific questions here.

To get you going, here are some of the key characteristics of the two
main List implementations:

ArrayList
---------
()Indexed element access is fast (constant time).
()List additions (at the end) sometimes require copying the entire
backing array (to a larger array), but usually not. Adding a large
number of elements is O(log N), if I've worked it out right.
()List insertions (not at the end) require moving the elements at and
after the insertion position, and sometimes requires moving all the
elements (when a larger array is required).
()List deletions usually require moving some or all of the elements of
the backing array to new positions (O(N)).

LinkedList
----------
()Indexed element access is slow (O(N) for random indices) because the
List must be traversed from one end to the desired element. The
specific cases of access to the first and last elements are fast, however.
()Additions and deletions at beginning or end are O(1)
()_Indexed_ additions and deletions are O(N) for random indices, because
of the time required to traverse the list to the appropriate location.
()List mutations never require copying the backing data structure.
()The List's ListIterator is your friend. Use it instead of indexes
wherever possible.


HTH

John Bollinger
(e-mail address removed)

 

[Edward H. Fabrega]

What are you trying to accomplish?

Implementing a general-purpose 'database' sounds like a poor idea. If
you're trying to come up with a solution for something specific, we need
more details to give reasonable advice on data structures. How/if the data
set is manipulated at runtime, data access patterns and so on.

Read up on the collections API here:
http://java.sun.com/docs/books/tutorial/collections/index.html

-Frank

Here is a link to somewhat what I'm trying to accomplish. This is a program
I wrote in C++ MFC

http://members.aol.com/spiritualfields/index.htm

The screenshots will give you a good idea. The underlying data model that I
used was a linked list of StringArrays. Every item in the database is a
string, and when necessary the program does the necessary conversions to do
math. What I am concerned about is how best to model the database. To my
thinking, I was considering a LinkedList of ArrayLists. Perhaps, as the
other commenter suggested (or at least put the bug in my ear), an ArrayList
of ArrayLists is more efficient. Eventually I will couple the database to a
view (in C++ MFC, I had to write it myself, and I will NOT go through that
again), using a JTable. This database will be totally dynamic, every
attribute (number of records, number of columns, the cell data) editable.
This will be a stand alone application. Eventually I'll have questions about
the view, but for now I'm concentrating on the data structure (I will
constrain it such that it will work with one of the JTable constructors).

 

[Edward H. Fabrega]

You have not even come close to specifying all your requirements. I
suspect that the term "database" has a very specific meaning to you, at
least in this context, but it does not illuminate us very well. Enumerate
(for yourself) all the functional requirements, and determine how well
your proposed model will handle them. If you need help with such an
evaluation then ask some more specific questions here.

To get you going, here are some of the key characteristics of the two main
List implementations:

ArrayList
---------
()Indexed element access is fast (constant time).
()List additions (at the end) sometimes require copying the entire backing
array (to a larger array), but usually not. Adding a large number of
elements is O(log N), if I've worked it out right.
()List insertions (not at the end) require moving the elements at and
after the insertion position, and sometimes requires moving all the
elements (when a larger array is required).
()List deletions usually require moving some or all of the elements of the
backing array to new positions (O(N)).

LinkedList
----------
()Indexed element access is slow (O(N) for random indices) because the
List must be traversed from one end to the desired element. The specific
cases of access to the first and last elements are fast, however.
()Additions and deletions at beginning or end are O(1)
()_Indexed_ additions and deletions are O(N) for random indices, because
of the time required to traverse the list to the appropriate location.
()List mutations never require copying the backing data structure.
()The List's ListIterator is your friend. Use it instead of indexes
wherever possible.

Thanks for that information. It looks like an ArrayLists of ArrayLists is
better than a LinkedList of ArrayLists. What my goal is is to write a
database program, similar to the one I wrote a couple of years ago in C++
MFC:

http://members.aol.com/spiritualfields/index.htm

The screenshots will give you a good idea of the view. It looks like a
JTable will work for the UI. I'm not even close to coding yet, as I'm
familiarizing myself with the java language and the jdk api. The underlying
data model that I had used for MyAuctionHelper was a linked list of
StringArrays. The view was modeled after Access, but I didn't use a
component, I painted it myself and coupled it to the database, but I do not
want to go through that again. The only constraint that I can think of right
now is that the data structure must compatible with JTables, and unless I'm
wrong, an ArrayLists of ArrayLists works with the JTable(Object[][] ,
Object[]) constructor. This will be a standalone application, and not
necessarily a remake of my previouis program. Between now and when I
actually start coding I could get other ideas. What is absolutely essential
is that the database is completely encapsulated so I can resuse it. I could
be wrong, but it looks like the javax.swing api almost forces encapsulation
if I use JTables as the view. I'm not sure if I have any more questions
explicitly, I'm still learning the nuts and bolts of java. If you have any
ideas or insights on modeling databases (flat file) with java, I'll be
interested to hear them.

 

[John C. Bollinger]

Edward H. Fabrega wrote:

[...]

and unless I'm
wrong, an ArrayLists of ArrayLists works with the JTable(Object[][] ,
Object[]) constructor.

[...]

Unfortunately, you are wrong. An ArrayList is completely different from
an array, and you cannot pass an argument of type ArrayList to a method
requiring an array. The JTable(Vector, Vector) constructor would almost
work -- Vectors and ArrayLists both implement List -- but you'd still
not be quite there. You could use Vectors instead of ArrayLists, but
for new code a generally recommend ArrayLists.

On the other hand, you are probably approaching the UI problem the wrong
way. The most fruitful approach would probably be to write a TableModel
implementation to adapt whatever data structure you use so that it can
be presented via a JTable. There is help in that direction in the form
of javax.swing.table.AbstractTableModel, which you can extend pretty
easily to support most any table-like data structure.

As far as the data structure itself goes, I would tend to agree that an
ArrayList of elements of type (one of: ArrayLists, arrays, custom
objects) would probably be the best choice.


John Bollinger
(e-mail address removed)

 

[Edward H. Fabrega]

Edward H. Fabrega wrote:

The most fruitful approach would probably be to write a TableModel
implementation to adapt whatever data structure you use so that it can be
presented via a JTable. There is help in that direction in the form of
javax.swing.table.AbstractTableModel, which you can extend pretty easily
to support most any table-like data structure.

That is my A-number one goal with the database. MFC has no View that
represents a table, and the lion's share of the problem with my other
program was the representation, drawing the view, making the "cells"
editable and so on, to react the way a user would expect. It was an
absorbing endeavor, but one which I do not wish to repeat. The database
structure itself was a linked list of CStringArrays. CStringArray lengths
can be dynamically shortened or increased as needed, so this was ideal, and
simple to code. Hopefully, when I become more familiar with the Java
Collections classes, with JTables and their TableModels, a solution will
present itself.

Ed