Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Sign In with Facebook Sign In with Google Sign In with OpenID

Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Lists and pointers

SorrowSorrow Posts: 20Member
Hi there!

I know it's probably childish questions for most of you, but I don't know how to create lists by using pointers.
There must be something like:
type recptr=^rectype;
rectype=record
{fields}
next,prev:recptr;
end;
but I don't know how to make it work. Could you please post an example of how to create and maintain such list?

Thanks very much,
Sorrow.

Comments

  • blitzblitz Posts: 620Member
    : Hi there!
    :
    : I know it's probably childish questions for most of you, but I don't know how to create lists by using pointers.
    : There must be something like:
    : type recptr=^rectype;
    : rectype=record
    : {fields}
    : next,prev:recptr;
    : end;
    : but I don't know how to make it work. Could you please post an example of how to create and maintain such list?
    :
    : Thanks very much,
    : Sorrow.
    :

    here's some code i written in a hurry (i got to go home in a couple of moments ;-)):

    [code]
    program _DList_;

    type
    pDLNode = ^DLNode;
    DLNode = record
    x: integer;
    prev, next: pDLNode;
    end;

    type
    DList = object
    private
    head, tail: pDLNode;
    public
    constructor init;
    destructor done;
    function empty: boolean;
    procedure push_front(x: integer);
    procedure push_back(x: integer);
    function pop_front: integer;
    function pop_back: integer;
    end;

    constructor DList.init;
    begin
    head := nil; tail := nil;
    end;

    destructor DList.done;
    var
    tmp: pDLNode;
    begin
    while head <> nil do begin
    tmp := head^.next;
    dispose(head);
    head := tmp
    end
    end;

    procedure DList.push_front(x: integer);
    var
    tmp: pDLNode;
    begin
    tmp := new(pDLNode);
    tmp^.x := x;
    tmp^.prev := nil;
    tmp^.next := head;

    if head <> nil then
    head^.prev := tmp;

    head := tmp;

    if tail = nil then
    tail := tmp
    end;

    procedure DList.push_back(x: integer);
    var
    tmp: pDLNode;
    begin
    tmp := new(pDLNode);
    tmp^.x := x;
    tmp^.next := nil;
    tmp^.prev := tail;

    if tail <> nil then
    tail^.next := tmp;

    tail := tmp;

    if head = nil then
    head := tmp
    end;

    function DList.pop_front;
    var
    tmp: pDLNode;
    begin
    if head <> nil then begin
    pop_front := head^.x;
    tmp := head;
    head := head^.next;
    dispose(tmp);
    if head <> nil then
    head^.prev := nil
    else begin
    head := nil; tail := nil
    end
    end else pop_front := 0
    end;

    function DList.pop_back;
    var
    tmp: pDLNode;
    begin
    if tail <> nil then begin
    pop_back := tail^.x;
    tmp := tail;
    tail := tail^.prev;
    dispose(tmp);
    if tail <> nil then
    tail^.next := nil
    else begin
    head := nil; tail := nil
    end
    end else pop_back := 0
    end;

    function DList.empty;
    begin
    empty := head = nil
    end;

    var
    list: DList;
    i: integer;

    begin
    { working as a stack }
    for i := 1 to 10 do
    list.push_back(i);

    while not list.empty do
    write(list.pop_back, ' ');

    writeln;

    { working as a queue }
    for i := 11 to 20 do
    list.push_front(i);

    while not list.empty do
    write(list.pop_back, ' ');

    writeln
    end.
    [/code]

    Cheers,
    Blitz

    PS: if you have problems with the code (it's not tested and some functions are missing - mainly insertion and deletion in the middle of the list - by now, this one is just a deque) just post a reply ...

    anyway, it was nice to remember the good ol' Pascal :-)



  • jasonpsagejasonpsage Posts: 37Member
    Sorrow, you posted some (for me) kinda hard code to read. I didn't understand how you trying to go about the list. Personally, I'm writing some fancy ones now (trying to use classes) but I'm having trouble too - but using objects it was pretty straight forward. I'll explain in pseudo how I do double linked lists. First of All, I make two objects, one is my Item and the other I call the list. Here are sample definitions (psuedo code). (I use lp as variable name prefix for variables that are really pointers - here pointers for objects)
    type TItem = object
    lpPrevITem: TItem;
    lpNextItem: TItem;
    (Data I want to store in variables here)
    end;

    type TList = object
    lpFirstITem: TItem;
    lpLastItem: TItem;
    lpCurrentItem: TItem;
    (Methods and stuff I put here)
    end;

    Basically the TList constructor sets the three pointers to nil when its created. Then I have methods like Append, MoveFirst, MoveLast, MovePrevious, MoveNext. I try to make my double linked lists work like database recordsets - so you can easily navigate through them. The key is when you call append (a fancy method is insert) it creates a new TList using the lpCurrentItem to hold it. Copy the pointer to FirstITem and to LastItem. Set lpCurrentItem^.PrevItem=nil and lpCurrentITem.NExtITem=nil. Now you have an object called list, with one element (TItem) and all the info to navigate. (One record means squat though) The idea is for each TItem your append (or insert method) in TLIst needs to update the existing TItems PrevItem and NextItem fields so they point to each other correctly. Set the first Item's PrevItem to Nil always and the last Item in mem NextITem to nil.
    This way you know not to navigate to far forward or backward in the list. Last thing I'll say - MoveNext would look something like this:
    procedure movenext;

    if currentitem^.nextItem<>nil then lpCurrentItem:=lpCurrentItem^.NextItem;


    Hope this helps a little.
Sign In or Register to comment.