Doubly linked list (again, sorry)

Doubly linked list (again, sorry)

[Matt Tyler]

Hello.

I have created a doubly linked list. With the procedure (body only)

List:=new cell'(V,Next=>, Prev=>null);

V=integer and prev,next are access types to next and previous cells in list.

I want to loop through the list in both directions. I can loop in the
reverse order to creation using a loop containing:

L:=L.Next;       (where L is also an access type to cell)

To loop from start of list do I need to create a (say) Start_of_list access
type to the first cell in the list or is there a more elegant way that I am
missing.

Also, when I remove (to delete) a record from the list do I have to
de-allocate the memory occupied by the object or is it done for me.

I am sorry to waste your time but I am having a few problems with access
types. Thanks in advance

Matt Tyler

Re: Doubly linked list (again, sorry)

[Ricardo Palomares Martínez]

Matt Tyler wrote:

> Hello.
>
> I have created a doubly linked list. With the procedure (body only)
>
> List:=new cell'(V,Next=>, Prev=>null);
>
> (...)
>
>
> To loop from start of list do I need to create a (say) Start_of_list access
> type to the first cell in the list or is there a more elegant way that I am
> missing.

    You should have a pointer to the first element of the list and other to the
last one. You also need another pointer to the current element when walking
through the list.


> Also, when I remove (to delete) a record from the list do I have to
> de-allocate the memory occupied by the object or is it done for me.

    You need to de-allocate it. I can't recall it right, but it has to do with
Unchecked_Deallocation package or similar. Anyway, read the end of my message.


> I am sorry to waste your time but I am having a few problems with access
> types. Thanks in advance

    You seem to have some lack of knowledge about the basics of the
double-linked lists, rather than implementing it in Ada. Perhaps you may wish to
give a look to some data structure or programming books (Knuth: "Data structures
+ Algorithms = Programs" IIRC, or Schultz: "Data Structures"; there is a long
time since I had my hands over these books and the title may be inaccurate).
Anyway, the newsgroups are to help us each other.

    About the double-linked list, I wrote a generic package to implement
double-linked list with n indexes (ie, n different pairs of pathways to run
through the list; think of every element as a link of a chain: then, every index
lets you put the links in a different order to form the chain). The generic
package lets you use any data type. It is not really a fast implementation,
because due to the nature of the package, you can't access directly to the
pointer type; instead, you have an identifier to which you refer always you need
to access a specific element, and internally to the package the list is walked
until the element is found.

    So, if you have big trouble implementing a double-linked list I can send the
code to you (the identifiers and comments are in spanish, but I can translate
the more important things if you want).

HTH

--
Ricardo Palomares Martínez -------- mailto:ricardo@eucmax.sim.ucm.es
UCM - Servicio Informático Gestión -- http://www.ucm.es/info/gstwsig

Re: Doubly linked list (again, sorry)

[Mats Weber]

Ricardo Palomares Mart�nez wrote:

> Knuth: "Data structures + Algorithms = Programs"

I believe this book is by Niklaus Wirth ("Algorithms + Data Structures =
Programs"). Or have both written books with such similar titles ?

Re: Doubly linked list (again, sorry)

[bwefler]

(scroll down to *** for my message) bw

In article <3677A69C.C197C703@eucmax.sim.ucm.es>,  Ricardo Palomares
=?iso-8859-1?Q?Mart=EDnez?=  <ricardo@eucmax.sim.ucm.es> wrote:

> Matt Tyler wrote:
>
> > Hello.
> >
> > I have created a doubly linked list. With the procedure (body only)
> >
> > List:=3Dnew cell'(V,Next=3D>, Prev=3D>null);
> >
> > (...)
> >
> >
> > To loop from start of list do I need to create a (say) Start_of_list ac=
> cess
> > type to the first cell in the list or is there a more elegant way that =
> I am
> > missing.
>
>     You should have a pointer to the first element of the list and other =
> to the
> last one. You also need another pointer to the current element when walki=
> ng
> through the list.
>
> > Also, when I remove (to delete) a record from the list do I have to
> > de-allocate the memory occupied by the object or is it done for me.
>
>     You need to de-allocate it. I can't recall it right, but it has to do=
>  with
> Unchecked_Deallocation package or similar. Anyway, read the end of my mes=
> sage.
>
> > I am sorry to waste your time but I am having a few problems with acces=
> s
> > types. Thanks in advance
>
>     You seem to have some lack of knowledge about the basics of the
> double-linked lists, rather than implementing it in Ada. Perhaps you may =
> wish to
> give a look to some data structure or programming books (Knuth: "Data str=
> uctures
> + Algorithms =3D Programs" IIRC, or Schultz: "Data Structures"; there is =
> a long
> time since I had my hands over these books and the title may be inaccurat=
> e).
> Anyway, the newsgroups are to help us each other.
>

*** A good book (if you can still get it) I used in data structures class is
"Data Structures with Abstract Data Types and Ada", Stubbs & Webre, 1993 PWS
Publishing company. ***


>     About the double-linked list, I wrote a generic package to implement
> double-linked list with n indexes (ie, n different pairs of pathways to r=
> un
> through the list; think of every element as a link of a chain: then, ever=
> y index
> lets you put the links in a different order to form the chain). The gener=
> ic
> package lets you use any data type. It is not really a fast implementatio=
> n,
> because due to the nature of the package, you can't access directly to th=
> e
> pointer type; instead, you have an identifier to which you refer always y=
> ou need
> to access a specific element, and internally to the package the list is w=
> alked
> until the element is found.
>
>     So, if you have big trouble implementing a double-linked list I can s=
> end the
> code to you (the identifiers and comments are in spanish, but I can trans=
> late
> the more important things if you want).
>
> HTH
>
> --
> Ricardo Palomares Mart=EDnez -------- mailto:ricardo@eucmax.sim.ucm.es
> UCM - Servicio Inform=E1tico Gesti=F3n -- http://www.ucm.es/info/gstwsig
>
>


--
bw  8-{)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Doubly linked list (again, sorry)

[Ricardo Palomares Martínez]

Mats Weber wrote:

> Ricardo Palomares Martínez wrote:
>
> > Knuth: "Data structures + Algorithms = Programs"
>
> I believe this book is by Niklaus Wirth ("Algorithms + Data Structures =
> Programs"). Or have both written books with such similar titles ?

    No, you're right. I had a memory parity error... ;-)


--
Ricardo Palomares Martínez -------- mailto:ricardo@eucmax.sim.ucm.es
UCM - Servicio Informático Gestión -- http://www.ucm.es/info/gstwsig