Chapter 2 -- Single Linked List

Introduction

Hi folks! Do you eager to munch this lesson? I think so. Do you really understand the first chapter? If you don't, you'd better not continue. Why? It's because the first chapter is the basic for this chapter and so for the third, the fourth, and so on. Yes, I assume you all understand pointer basic. You are smart, aren't you? The progress you've been making so long is not an easy path. Good luck!

OK, I'll explain what this chapter is all about. Well, it extends your comprehension to pointers. J Of course! Single linked list and double linked list are mainly used for database programs. You can also use it for strategy games and RPGs, especially for maintaining its sprite data. What is sprite any way? That's the moving small images on the screen, including the heroes, the enemies, and maybe the moving background, in games.

Maybe it's better for us to know what the lesson is for, because it helps us to keep our interest in studying it. Why? Well, for me, if the chapter or the subject is not interesting, I'd rather not to study it. I think this rule applies world wide, so that now I would rather explaining interesting lessons only. J Although this part is a little bit boring for my taste.

Actually, single linked list is pointers linked to data, then data itself contains only one pointer to link to another data. The other data, which I meant, is either the next data or the previous data. It depends which is which. So, single linked list is divided into two types: queue and stack. In queue, the pointer inside the data links to the next data. In stack, it is linked to the previous data. Confused? Let's take a look at this diagram:

Queue Diagram

1^st data --> 2^nd data --> 3^rd data --> 4^th data --> 5^th data --> … (and so on until the last data)

It means the first data record contains a pointer that links to the second data, the second data has a pointer to the third, and so on. In queue, the first data will always be the head, the last data becomes the tail.

Stack Diagram

1^st data <-- 2^nd data <-- 3^rd data <-- 4^th data <-- 5^th data <-- … (and so on until the last data)

In stack, the first data will always be the tail, the last data becomes the head.

Yeah, it's just the reverse of queue, right? I suppose it all clear now. If you are still confused, you'd better contact me.

The essence of queue and stack is not just like this. Queue behaves like a normal queue. You don’t know queue? Well, if you want to see a movie in a theatre, you've got to queue to buy the ticket. The first visitor in front of the cashier is served. Whoever comes first, it is first served. That's the principle of queue, first in first out (FIFO).

The stack is different. If you stack something, like stacking a pile of plates, you would place the plate you hold over them. If you ever need the plate, you would never want to get the lowermost plate, you always get the top plate. Although the lowermost plate is placed first, it is not be gotten first. The last plate, on the top of the stack, is always be the first to get. So, whichever come last, it is first served. That's the principle of stack, last in first out (LIFO).

In order to satisfy the requirements of FIFO and LIFO, I made all things easy to us, folk programmers, by mentioning how the pointers relationship should be. Look at the previous diagram. Get the picture why and how it should be done to the list?

Why do the lists is widely used? It's because its flexibility. Look at this. It's a queue. Suppose I have the pointer called the head to keep track where the head (1^st data) is. And now, I have a pointer variable called cur.

Cur:=head;           { Now, cur points to the 1^st data }
Writeln(cur^.name);  { Display 1^st data }
Writeln(cur^.address);
Cur:=cur^.next;      { Now, cur points to the 2^nd data }
Writeln(cur^.name);  { Display 2^nd data }
Writeln(cur^.address);
Cur:=cur^.next;      { Now, cur points to the 3^rd data }

It's so flexible, isn't it? Get any idea? How if we place it in a loop? We can access all data in a single hit, right?

Operations to the List

There are several operations that can be done to the lists either queue or stack:

Initialize.
Uproot or destroy.
Add item.
Delete item.
Search item.
Edit item.
Display (either just one item or all items).

The operations behave differently in queue and in stack.

I warn you all academician: Lists can do a lot more! You just make them be accessed sequentially. These things can go very wild and crazy you would never imagine, insert item. Although this may crossed the behavior of queue and stack, this allows the flexibility of lists! But why lecturers always oppose this idea?? Oh well, things go on and on, who cares? L

Another common mistake done by – again – academician is empty headed (or tailed) list. Well, that's not a bug but merely a memory waste. We're supposed to fill in every node in the list, but in this case, we just waste the first (or the last) node. If the node contains only several bytes, it's ok. But when it comes to several kilobytes, that's a problem. We're supposed to optimize the memory usage, aren’t we?

Since the operations behave differently, I would like to discuss queue first.

Queue

Declaring queue is only possible done in a record. The declaration is like this:

Type
  pMyqueue = ^tmyqueue;
  tMyqueue = record
               name    : string[30]; { Data Section }
               address : string[40]; { Another data, as long as you want }
               next    : pMyqueue;   { The link to the next node }
             end;

As you see in the declaration above, the record has a pointer to the next node. By the way, node is anything that points to other links and is pointed by other link(s).

The list diagram is like train, isn't it? It has a head and a tail. Well, for either queue or stack, it's better for us to keep track the head or the tail. Why? It makes us easy in keeping track things. For queue, you may need only the head pointer and stack needs tail pointer. Nevertheless, for best performance, you'll need both head and tail be kept. That really helps you to add items to the list.

The first operation I would like to explain is initialization. The initialization is best done when user enters the first data. Otherwise, you would cause the empty headed syndrome. Thus, the initialization is better merged with add. You can split them if you want to. Then, the adding algorithm is like this:

Whatever the list is exist or not, you need to create a new pointer and filled it with data.
Suppose the newly created pointer is called cur, set the next field to nil. Why? Because the newly added item is always be the last item.
In that case, the last item in the list (not cur) is no longer be the last one. So, if the list has been made, you need to link the last item to cur by filling the next field equal to cur.
Because from now one cur is the last pointer, we need to update the last pointer.

Easy, no? Well, I cannot list the source code yet because in writing linked list, you should write at least initialization, add item, display (all) item and destroy item to test whether your program is correct or not. Why? It's because linked list is an abstract idea. That's why. So, before I write the code, I'd like to advance a bit, explaining display item.

For practical programmers, it's a bit boring, right? We can't get straight to the practice. That's why I said that this chapter is pretty boring. But I warn you, folks. This chapter is very important, especially if you'd like to build database program of your own. So, please be patient. Patience is golden! J

The easiest part of linked list is probably display item. Displaying all items in the list is best described in this algorithm:

Suppose you have the pointer cur, then you set cur to head.
If cur is not nil, then display the data, otherwise quit.
Set cur to cur^.next, then repeat step 2.

'Hey, what's nil?' you asked. Oh, that's a pointer value that usually used to mark the end of list. A nil pointer is a pointer that points to nowhere. Well, that's all you need to know I think, for at least – this moment. The truth behind it is quite complicated.

OK. Now, how to destroy the list. Why must we destroy it? It's all because it IS a good programming habit. If you don't, you simply can't keep track the reserved memory for existing data. And the data is still alive even after exiting to the operating system! So what? Just do it and ask no more! J

Destroying queue is best done from the head. How can we do that? Here's the algorithm:

Suppose you have the pointer cur, then you set cur to head.
If cur is not nil, then set cur to cur^.next, otherwise quit.
Destroy the head pointer (with dispose).
Set head to cur, then repeat step 2.

Well, cur that is mentioned above is a pointer that is compatible to the head. Try different pointers and you'll get error message. If you don't believe me, just try it. J

So, I'm dizzy, too much theorem. OK! Now the source part. You can refine much better than this. This is just a rough idea.

Uses crt;
Type
  pMyqueue = ^tMyqueue;
  tMyqueue = record
               name    : string[30];
               address : string[40];
               next    : pMyqueue;
             end;
var
  head, last : pMyqueue;
  temp       : tMyqueue;  { Temporary record }

{ This function add content to the last, then output the last pointer }
function add(last : pMyqueue; content : tMyqueue):pMyqueue;
var cur : pMyqueue;
begin
  new(cur);                       { Create a new pointer, step a }
  cur^.name:=content.name;        { fill it up with data; still step a }
  cur^.address:=content.address;
  cur^.next:=nil;                     { step b }
  if last<>nil then last^.next:=cur;  { step c }
  add:=cur;             { Last is no longer the tail, but cur is; step d }
end;

procedure display(head : pMyqueue);
var cur : pMyqueue;
begin
  cur:=head;           { Step 1 }
  while cur<>nil do    { Step 2 }
  begin
    writeln(cur^.name:35,cur^.address);  { Step 3 }
    cur:=cur^.next;
  end;
end;

procedure destroy(var head : pMyqueue);
var cur : pMyqueue;
begin
  cur:=head;           { Step 1 }
  while cur<>nil do    { Step 2 }
  begin
    cur:=cur^.next;
    dispose(head);     { Step 3 }
    head:=cur;         { Step 4 }
  end;
end;

begin
  head:=nil; last:=nil;               { Set all pointers to nil }
  repeat
    write('Name    = '); readln(temp.name);
    if temp.name='' then break;       { Stop if name or address is empty }
    write('Address = '); readln(temp.address);
    if temp.address='' then break;

    { Otherwise, add them to the list }
    last:=add(last,temp);
    { If this is the first item, set the head equal to the last because
      this is the only item }
    if head=nil then head:=last;
  until false;          { Repeat forever }

  display(head);
  readkey;
  destroy(head);
end.

The pointer that is inputted into add function is the last pointer. Why? It's because if we adding things in the queue we must do it at the last pointer, right?

Now, how could we delete items? The way to do it is quite the same as uprooting. But, we only do it once, not to all items as depicted in uprooting. In queue we must delete the front-most item. Well, actually you can delete any item in the list. But, most academician suggested this. They said deleting any item either in the middle or at the last item would cause the queue lost its attribute (or behavior). Blah blah blah. Whatever you say. This is the way we should do it:

If the node to be erased is nil, quit. Otherwise, go on.
Suppose you have three pointer: bef, cur, and aft. Make bef points to the node before the node you want to erase. Then cur itself points to the node you want to erase, and aft should point to the next node of cur.
Make bef.next:=aft, then dispose(cur).

That's the way you can delete any items in the list, either at the front, or in the middle, or even at the last! Making aft point after cur is easy. This is done by aft:=cur^.next. But how could we make bef points before cur? There are no pointers pointing to the back of cur? How could we do that? By this:

bef:=head;

while (bef^.next<>cur) and (bef<>nil) do

bef:=bef^.next;

But be careful! We need special attention if we delete the first pointer. We need not do steps as I have mentioned above. But, we just need the cur pointer. If the deleted pointer is equal to the head then:

We set cur:=head^.next.
Dispose(head).
set head:=cur.

Easy right? Now, you should be able to implement it. I'd rather not giving you the source code, but to leave this as your exercise. :-) If you don't understand mail me. Oh, alright, alright! I'll give you the code:

procedure delete(var head : pMyqueue; whattodel : pMyqueue);
var bef, cur, aft : pMyqueue;
begin
if head=nil then exit;
cur:=whattodel; aft:=cur^.next;
bef:=head;
if bef<>cur then
begin
while (bef^.next<>cur) and (bef<>nil) do bef:=bef^.next;
bef^.next:=aft;
dispose(cur);
end
else
begin
dispose(head); head:=aft;
end;
end;

How about searching items? First, you need a pointer, name it cur. I assume you've already asked user the will-be-searched data. Suppose you want to search the name of the item. This is the way:

function find(head : pMyqueue):pMyqueue;
var cur : pMyqueue; found : boolean;
begin
cur:=head;
while cur<>nil do
begin
if cur^.name=searchedname then
begin
found:=true; break;
end;
cur:=cur^.next;
end;
if found then find:=cur else find:=nil;
end;

Did you understand? If the search is success, the function find will return the pointer to that data. Otherwise, it will return nil.
If you don't understand mail me. How about the edit? Well, that easy part is yours to tackle. I think that is easy enough. :-) It just change the contents of the node.

Stack

Phew! Quite a lengthy explanation. Well, in stack, I just use the analogy as a turned-back queue. Declaration is pretty the same. Check this out.

  Type
    pMystack = ^tMystack;
    tMystack = record;
                 name    : string[30];
                 address : string[40];
                 prev    : pMystack;
               end;

The anatomy is just the same. To avoid ambiguousity, I just rename queue to stack. Since the link of stack nodes points to their ancestors (previous node), so I rename next to prev. Yeah, easy! :-)

Adding items in stacks is pretty much similar to the queue, but now the direction of the pointers is reversed. Look at the steps above, then reverse it and voila! Here is the code:

{ This function add content to the front, then
  output the first pointer }
function add(first : pMystack; content : tMystack):pMystack;
var cur : pMystack;
begin
  new(cur);                      { Create a new pointer, step a }
  cur^.name:=content.name;       { fill it up with data; still step a }
  cur^.address:=content.address;
  if first=nil then cur^.prev:=nil   { step b }
     else cur^.prev:=first;  { step c }
  add:=cur;                  { first is no longer the head, but cur is; step d }
end;

Very similar, isn't it? Compare it with stack then you'll know the process. Remember, in stack, the first data always be the tail! Then, the display part and destroy part is just the same. You just change the word 'queue' to 'stack' and 'next' to 'prev'. Then the main begin...end block is pretty much the same, but has some differences.

begin
  head:=nil; last:=nil;               { Set all pointers to nil }
  repeat
    write('Name    = '); readln(temp.name);
    if temp.name='' then break;       { Stop if name or address is empty }
    write('Address = '); readln(temp.address);
    if temp.address='' then break;

    { Otherwise, add them to the list }
    head:=add(head,temp);    { If this is the first item, set the last equal to the head because
      this is the only item }
    if last=nil then last:=head;
  until false;          { Repeat forever }

  display(head);
  readkey;
  destroy(head);
end.

The boldfaced code denotes the difference between stack and queue. Run it step by step and you'll see the difference.

How about the searching part? Pretty much the same, just rearranging names. Try it! Delete part is too. But I warn you, you must do it very carefully, otherwise, you'll create a very nice hang-ups in your computer :-) But, don't be affraid, it won't crash your hard disk! :-)

Some Notes

Some academician prefers the function get_item. In queue, it is the same as return the data of the first item (only the data, not the pointer) and then dispose it (dispose the pointer). In stack, it is the reverse: return the data of the last item, then dispose the pointer (the last pointer). That's all. Easy, right?

Edit item is usually worked with search item. Edit item is done only if the data is exist and user has an opportunity to change its contents. I think that's a very easy part for you to do, so I don't have to explain everything here.

After you have learnt queue and stack, is there any chance to insert items in the middle of stack or queue? Yes, it absolutely can! Think of it because I'll ask you in the quiz! Well, how about retaining the behavior of the queue or stack. I'll say people is able to cut the queue, why can't we insert items in the middle of the queue? :-)

Ah, this chapter is boring. Ummm... this is an important part, fella! Even many famous multitasking operating system uses this to maintain multiple tasks running in the background, although in an advanced manner.

OK, that's all for now. Shall we go to the quiz or the next lesson? Or you still don't understand? Mail me!

Where to go?

Back to main page
Back to Pascal Tutorial Lesson 2 contents
To the quiz
To Chapter 3 about double linked list
My page of programming link
Contact me here