|
Pointers and linked lists - Chapter 2 - by Aiwendil
Hi ho, and welcome to part two :)
Linked lists and double-linked lists...
Hope you read part one or know pointers well, since that is needed for this part.
A linked list, how should one explain them. A linked list is a list that also contains a pointer to the next element in the list. Pretty much like a chain.
Imagine that we have an element A that has the child B. A and B are both pointers (typed pointers in most cases). A does somewhere in it points to be, which in turn can point to another child called C, which can point to D and so on... This is called a list, in pascal we can declare it as
follows:
TYPE pItem = ^tItem;
tItem = RECORD
Data : STRING;
Next : pItem;
END;
For this to work it is important that pItem is declared before tItem and that they are declared in the same "block". pItem is a typed pointer of the type tItem, tItem's element Next is of type pItem thus enabling it to point to itself or any identical data structures (actually it can point to anything, but the result can be pretty unpredictable if it doesn't point to another tItem).
Now, let's demonstrate the use of a simple linked list.
TYPE pItem = ^tItem;
tItem = RECORD
Data : STRING;
Next : pItem;
END;
VAR S : STRING; {Temporary String, used for simplicity}
FirstItem,
LastItem,
TempItem : pItem;
Count : Byte; {Only to make the UI easier}
BEGIN
{Reset the pointers -- start}
FirstItem:=NIL;
LastItem:=NIL;
{Reset the pointers -- done}
WriteLn('Enter any number of lines');
WriteLn('End with a line only containing a dot (.)');
REPEAT
ReadLn(S);
IF S<>'.' THEN BEGIN
{Get memory for another tItem}
New(TempItem);
{Assign S to the field Data in the tItem pointed at by TempItem}
TempItem^.Data:=S;
{Make sure that the field Next in TempItem points to NIL, belive
me, if you make it a habit to set all unused pointers to NIL it
will be _much_ easier to code}
TempItem^.Next:=NIL;
{Is the list empty? If so then make this item the first in list}
IF FirstItem=NIL THEN FirstItem:=TempItem
{or if it isn't, just let the element Next in the LastItem point
to this item}
ELSE LastItem^.Next:=TempItem;
{And set the a pointer to this item to that we can find the last
item without having to step thru all items}
LastItem:=TempItem;
END;
UNTIL S='.';
WriteLn;
WriteLn('You wrote');
WriteLn('--Start');
Count:=0;
{As long as there is a list that we point to}
WHILE FirstItem<>NIL DO BEGIN
{Make it so that LastItem points to the same as FirstItem}
LastItem:=FirstItem;
{With indicates that we want to work with the data inside a record,
in this case the record (of type tItem) pointed at by FirstItem}
WITH FirstItem^ DO BEGIN
{Print what's in the buffer}
WriteLn(Data);
{Make FirstItem point to whatever the element Next pointed to, in
other words, following the list one level}
FirstItem:=Next;
END;
{Free the memory occupied by the old FirstItem}
Dispose(LastItem);
IF Count=9 THEN BEGIN
WriteLn('Hit enter for the next ten lines');
ReadLn;
Count:=0;
END ELSE Inc(Count); {Same as Count:=Count+1; or Count++;}
END;
WriteLn('--Stop');
END.
Now, this maybe not look that useful, but as long as your OS allows you to get the memory you can write as many lines as you want. This program doesn't care if you write one line or if you write ten tousand lines. It will simply enough get more memory as it needs it. This is also why it is important to free up some memory.
Now, this program does however have a major flaw, how to we search in it backwards (down-top)? Well, we would have to compare the Next until it is where we was before the search. This is where double-linked lists come handy. We declare them as follows:
TYPE pItem = ^tItem;
tItem = RECORD
Data : STRING;
Next : pItem;
Prev : pItem;
END;
As you can see it's the same as a linked list except for that we now have a Prev pointer as well, it will point to the previous tItem in the chain.
(I have copied in the previous program and modified it, in case you are curious about why it looks like I used the same program twice. And I did also stripped out all the comments from the previous program)
TYPE pItem = ^tItem;
tItem = RECORD
Data : STRING;
Next : pItem;
Prev : pItem;
END;
VAR S : STRING;
FirstItem,
LastItem,
TempItem : pItem;
Count : Byte;
BEGIN
FirstItem:=NIL;
LastItem:=NIL;
WriteLn('Enter any number of lines, end with a line only containing a dot (.)');
REPEAT
ReadLn(S);
IF S<>'.' THEN BEGIN
New(TempItem);
WITH TempItem^ DO BEGIN {With is helpful}
Data:=S;
Next:=NIL;
{We set the previous pointer to point to the last item here
already, since we will insert it right after the last item}
Prev:=LastItem;
END;
IF FirstItem=NIL THEN FirstItem:=TempItem
ELSE LastItem^.Next:=TempItem;
LastItem:=TempItem;
END;
UNTIL S='.';
WriteLn;
WriteLn('Hit D and enter for decreasing order');
WriteLn('anything else and enter for an increasing order');
ReadLn(S);
WriteLn('--Start');
Count:=0;
{If we are working in reversed order we start in the other end}
IF (S='D') OR (S='d') THEN FirstItem:=LastItem;
WHILE FirstItem<>NIL DO BEGIN
WITH FirstItem^ DO BEGIN
WriteLn(Data);
{If we are NOT working in a reversed order then go forward}
IF NOT ((S='D') OR (S='d')) THEN FirstItem:=Next
{Else go backwards}
ELSE FirstItem:=Prev;
END;
IF Count=9 THEN BEGIN
Count:=0;
WriteLn('Hit enter for the next ten lines.');
ReadLn;
END ELSE Inc(Count);
END;
WriteLn('--Stop');
END.
Oh, and most important of all... Never EVER try to play with the memory pointed at by a NIL or unitizialied pointer, that can cause some nasty sideeffects (in DOS, for an example, you will overwrite the interrupt table if you do that, thus causing the computer to crash).
Hope it helped an made any kind of sense --Aiw
Back to previous page
|
