Question about link list
Raymond & Calvin
With pointer and struct, i can creat a link list eg.
struct record
{
// some records here
struct record *next
}
The record contains the pointer to the next record. But if the record
are read from a external file, is that link list become useless here?? I
think it doesn't make sense to read the whole database from a file to a link
list at start up. So what is the general use of link list?
Ari Lukumies
To link items into a list :) In memory, the next pointer points to the
next struct in memory (ie. it's a memory address) or NULL if there are
no more records, so there's no sense in saving the value in a file,
since the next time the program is run, it probably gets different
memory addresses. In a file, you could save the ftell position of the
next record in record.next, if the size of the pointer is the same as
the ftell returned value (long), but this is nonportable. When reading
in the file into a list, you'd then replace the record.next value with a
proper memory pointer.
AriL
--
Humans may send email (if absolutely necessary) to the
obvious non-spam address.
Bob Myers
Raymond & Calvin <nos...@nospam.nospam> wrote in message
news:7d7qsn$ao9$1...@imsp009a.netvigator.com...
> Hi,
> With pointer and struct, i can creat a link list eg.
> struct record
> {
> // some records here
> struct record *next
> }
>
> The record contains the pointer to the next record. But if the record
> are read from a external file, is that link list become useless here?? I
> think it doesn't make sense to read the whole database from a file to a link
> list at start up. So what is the general use of link list?
>
You put items into a link list in order to access them quicker
than reading them from a file. It's quicker to traverse the link
list to find a specified record than it is to read the whole file
to do the same. If you're going to be using the data
sequentially, it doesn't make sense to read it into a list.
Random accesses to the data, however, are much quicker
with a link list.
There does come a point, however, where size of the database
becomes an issue. Then you can use a link list which contains
an offset from the beginning of the file and key fields. You still
search the link list, but read the whole record from disk via
fseek() and friends.
By that point you're probably looking at hash tables and
other search/retrieval mechanisms, though.
Stephan Wilms
>
> With pointer and struct, i can creat a link list eg.
> struct record
> {
> // some records here
> struct record *next
> }
>
> The record contains the pointer to the next record. But if the record
> are read from a external file, is that link list become useless here?? I
> think it doesn't make sense to read the whole database from a file to a link
> list at start up. So what is the general use of link list?
Linked lists are mainly used for storing information in memory. Especially
when you want something like a growable array. Another point in favour of
linked lists is that sorted insertion and delete operations are very fast.
Writing a list to file and reading it again are rather complex operations.
As you correctly observed it makes no sense writing the pointers to a
file. Instead you write only the data components and rebuild the entire
list element by element when reading it in.
Ther is one special way to avoid this problem, but at the cost of some of
the flexibility. You can use an array to simulate a linked list. Instead
of pointers to the next element you store the array index of the next
element. With this implementation you can write and read the whole list in
one go. But growing and shrinking the list becomes a bit more complicated
and might involve considerable overhead.
Stephan
(initiator of the campaign against grumpiness in c.l.c)
(-: A brandnew excellent FAQ version has been released !!! :-)
(-: Get it: http://www.eskimo.com/~scs/C-faq/versions.html :-)
G.Pohl
a file:
Guess you are having a adress file. If you want to read it in any sorted
order you may use a linked list. write in each record the adress (file
offset) of the logical next record. To scan in sorted order you only have to
follow the links. But you will have a lot of trouble in inserting, modifieng
and deleting records, because you are to scan probably the complete data
file to insert delete or modify one item.
In this case it might be a better way to write the linked list (if to great
to fit in memory) into an extra index file. The records of this index file
will be much smaller than the records of the data file. IO access should be
faster. Just using OOP techniques it is rather easy to install dynamic
lists: you may have a linked list for name, bithday, uip, city ... Thay
update themself "automaticly" :-)) we have designed an index sequential
database.
In a next step you can add a link which points to the next record (like
above) and to a record in just another database. :-)) we have designed a
relational index sequential database model.
The last step in using linked lists on files is to implement a page swapping
mechanism, wich reads a greater or smaller block of the list in memory. Only
if needed it is going to swap this part of the list back to the index file
(if modified) and reads the next or prev block.
There might be a general rule:
Scanning the database in any sorted order it is in most cases fast enough to
read only from file.If there a big actions database updates and only short
times to give an anser to the user, it should be a better way to hold as
much as possible of the list in memory.
See you
G.Pohl
-------------------------------------------------------------------
Raymond & Calvin schrieb in Nachricht
<7d7qsn$ao9$1...@imsp009a.netvigator.com>...
>Hi,
Will Rose
: Hi,
: With pointer and struct, i can creat a link list eg.
: struct record
: {
: // some records here
: struct record *next
: }
: The record contains the pointer to the next record. But if the record
: are read from a external file, is that link list become useless here?? I
: think it doesn't make sense to read the whole database from a file to a link
: list at start up. So what is the general use of link list?
It's useful when the list is of varying size, and you want to add or
delete things; it's not so good when you want to search for things.
You can initialise it from a file fairly easily; just malloc space
for a node, read the data in from disk, update the pointers, and
repeat.