Double Linked List

Chapter 3 -- Double Linked List
PLUS
Circular Linked List

Introduction

Hi! We meet again! Well, well, well! It seems that you've already mastered queue and stack! Now you want more! :-) Or may be you are desparated because you couldn't catch the last lesson? I hope not! :-) Entire lesson has the very same format. I hope you're not bored. :-)

What to Learn

What to learn? Of course double linked list. That is the title right? :-) Yeah...yeah! We'll going to learn more about linked list. Why? Are queue and stack just enough? Well, my son, that is not. Remember the problem how to get to the previous node in queue? We just loop it until it reaches the previous node, right? If the case is you want speed very badly, this could waste CPU time, right? In that case, we need both pointer that points either to the next node or to the previous node. That is called double linked list.

For the snacks, we'll learn circular linked lists as well. It's pretty bit easy. Do you still remember that either queue or stack has a nil pointer at the edge? Sure you do! In circular linked list, we just link the last item to the first item. The management is pretty unique, but simple to understand. You can also circulate the double linked list.

Double Linked List

Double linked list has no type. Yeah, it's because it points to both direction. Just like queue and stack are combined together. Could you imagine that? Look at this diagram:

Well, got a picture in your head about the declaration?

type
  pDbllist = ^tDbllist;
  tDbllist = record
               name    : string[30];
               address : string[40];
               prev, next : pDbllist;
             end;

See? There are two pointers now, prev and next.Yup! The pointer prev points to the previous node and next to the next node. Again, you need to keep track both the head and the tail of the list. The operations done in the list is still the same plus an extra: insert item. Yes, all of the programmers, including academician, agree that insert item may be done in double linked list.

At this point, you may wonder how to create and add items. Like queue and stack, initialization is done best after the user inputs the first data. The step are:

If the list hasn't been created yet, we create it then fills both prev and next with nil.
Otherwise, add it at the tail of the list. Yes, you may add things every where in the list, but I choose the tail.

How can we add item at the tail?

Create a node, let's say cur, then fill it with data.
cur^.prev:=tail;
cur^.next:=nil;
tail^.next:=cur;
Update tail, can be done with returning pointer value.

After cur is created, cur is now the last node. That's why step 3 is done. Its previous node is tail, the node before the last node (cur), so that's why step 2 is done. For the continuation of the list, tail needs to be linked to its neighbor, cur, in step 4. Since tail is no longer the last node, you need to update tail in step 5. Step 1 is the same as in single linked list and it is clear already.

OK! Let's implement it in a procedure, just like the add function in single linked list.

procedure add(var tail : pDbllist; content : tDbllist): pDbllist;
var cur : pDbllist;
begin
  new(cur);
  cur^.name:=content.name;
  cur^.address:=content.address;
  cur^.prev:=tail;
  cur^.next:=nil;
  tail^.next:=cur;
end;

Display all items is just the same as queue. Check this out:

procedure display(head : pDbllist);
var cur : pDbllist;
begin
  cur:=head;
  while cur<>nil do
  begin
    writeln(cur^.name:35,cur^.address);
    cur:=cur^.next;
  end;
end;

No change except the names, right? pMyqueue to pDbllist. How about destroying? Pretty much the same as queue. Do it yourself! I knew you're clever! Searching things done quite the same.

But now, the deletion is done more cleverly. Watch this:

procedure delete(whattodel : pDbllist);
var cur, bef, aft : pDbllist;
begin
  cur:=whattodel;
  if cur=nil then exit;
  bef:=cur^.prev;
  aft:=cur^.next;
  if (bef<>nil) and (aft<>nil) then   { The wanna be deleted item is in the middle }
  begin
    bef^.next:=aft;
    aft^.prev:=bef;
  end
  else
    if (bef=nil) and (aft<>nil) then  { The wanna be deleted item is at the front }
      aft^.prev:=nil
    else

     if (bef<>nil) and (aft=nil) then   { The wanna be deleted item is at the end }
        bef^.next:=nil;

  dispose(cur);
end;

Now, it's easy to get the previous and the next node, isn't it? But now the caution is this: Referencing a nil pointer could crash your computer. That's the common mistakes of programmers. Suppose aft is nil, if you do aft^.pref:=nil; you'll get a beautiful crash. Remember, a nil pointer points nowhere. It actually points to address 0, where vital tables of interrupts are in. So, giving value to a nil pointer means you interfering the system. That's why you'd get crashed. Get any idea why in the deletion part has many ifs? That's to validify the pointers, so that no crash will happen.

However, there are no expert programmers that never experiencing crash. If you are daring, you may modify the if statement and see the result. I suggest you doing this in DOS, not Windows (3.1 or 95 or 95 even in DOS mode). It's because if DOS crashed, you simply reset the computer and nothing has happenned. And: Remember to save your source code often.

There are so many books that is not competent in explaining the linked lists. Some book says, we can just disregard the deleted nodes without disposing it. That's totally wrong! Remember why? I don't know why those books even exist in this world. But now, you, after joining this class, can correct the errors.

The different thing between single and double linked list is that in double linked list, we may (is permitted to) insert items in the middle of the list. It is actually a simple operation. Look at this:

procedure insert(afterwhat : pDbllist; content : tDbllist);
var cur, bef : pDbllist;
begin
  if afterwhat=nil then exit;   { You can't insert item in an empty list }
  new(cur);                     { Create node for the wanna be inserted item }
  cur^.name:=content.name;      { Then fill it with its data }
  cur^.address:=content.address;

  bef:=afterwhat;
  cur^.prev:=bef;        { Cur is after bef, so bef is before cur }
  cur^.next:=bef^.next;  { Take over the next item ** }
  bef^.next:=cur;        { Link the inserted item after the node }
end;

The comment with double star I'll explain here. At this point, right after bef is cur. So the entry of bef^.next is no longer the next node of bef. It is suppose to be the next door neighbor of cur, right? So, we'd set cur's next door to bef^.next.

In summary, delete and insert procedure can be depicted as below:

Deletion:
We want to delete node 13. Note that we don't need to break up the node 13's link. Just make 12 points to 14, and 14 to 12. That's enough to delete 13.

Insertion:
We just want to insert node 16 between 15 and 17.

That should be clear enough. A picture worth more than a thousand word, right?

Circular Linked Lists

What's the different? The different point is there are no nil pointer to mark the end (or the beginning) of the list. That's all. How could it be? Well, we just link the tail's next pointer to the head (or the head's previous pointer to the tail) so that it circles back. Therefore, it gets its name, circular linked list.

Circular linked list has quite a little practical use. But this is often exercised in operating system matter, such as task maintenance things. The main purpose is that we are not bothered reseting to the head pointer after we reach the ends and vice versa.

Because in programming, many things are looped back. Suppose you select 'File' menu in any program in Windows, then you press right arrow several times to reach the end menu 'Help'. After you reach 'Help' and you press right several times, you'll get to 'File' menu again, right? Even you don't press left at all. That means loop back. Did you get the idea?

Pointer links is the same as single linked list, it's either circular queue or circular stack. The declaration is the same too. Circular queue links the tail's next pointer to the head. Circular stack links the head's previous pointer to the tail. Nevertheless, double linked list can be made into double circular list. It's barely the same as circular queue and circular stack are combined together. So, in this issue, I would like to explain circular queue first.

The operations done with circular list (queue, stack, or double) are the same as in the normal forms. The only exception is that in single circular list (queue or stack) we are now allowed to insert item in the middle of the list. However, each operations algorithm is a little bit different from that in the lesson we've learnt so far. It is all because we can not do this: while cur<>nil do ... any longer. Do you know why? Yes! There are no nil pointer any more to mark the end (or the beginning) of the list.

In addition, the operations done in add function (or procedure) is quite a bit different. It is all because we need to loop back. The loop back must be done in add section. Let's take a look at the normal add function then compare it with the code below. I'd rather not to rewrite the normal add function since it is a waste of time and it would be nice to shorten the download time. I suggest you to print out the second chapter then you are now able to compare it with the code below.

function add(var last : pMycircqueue; content : tMycircqueue): pMycircqueue;
var cur : pMycircqueue;
begin
  new(cur);
  cur^.name:=content.name;
  cur^.address:=content.address;
  if last=nil then cur^.next:=cur  { If it's the first item, cur points to itself }
    else
    begin         { cur is now the last, head is still pointed by last^.next (loopback) }
      cur^.next:=last^.next;   { cur^.next points to head }
      last^.next:=cur;         { last^.next points to cur }
    end;
  add:=cur;
end;

If cur is the first item, cur^.next points to itself in order to satisfy the circular behavior. If cur is not the first item, we need to tackle it. First of all, last is the last item of the circular list. Last^.next hold the value of head. Remember the loop back manner. But after creating cur, cur is now the last item, not last. Last is the pointer before cur, right? So, we need to make cur^.next equal to the head (i.e. last^.next), then make last^.next equal to cur. Finally, the add function returns cur, as usual. I hope above explanation is clear enough.

All operations are done similarly with one exception as I have mentioned above. Only destroy is quite different. To tackle that, we just replace while cur<>nil do ... with while cur^.next<>head do ... It's quite a bit similar. However, you need to check if the circular list contains only one item. Since if the circular list contains only one item, the next pointer points to itself, so the while loop will not work. Look at this code:

procedure display (head : pMycircqueue);
var cur : pMycircqueue;
begin
  cur:=head;
  if head^.next = head then writeln(cur^.name:35, cur^.address);
  while cur^.next<>head do
  begin
    writeln(cur^.name:35, cur^.address);
    cur:=cur^.next;
  end;
end;

If you are curious about the if statement, let's remark it for a while then run it. See the difference. You got it? Yep! If you remark (make it into comment) the if statement, you'll never see the first item printed. Yes, you may change it into repeat ... until block.

Now, the destroy part. I suppose this changes quite a lot and now we use repeat ... until block. Examine this:

procedure destroy (head : pMycircqueue);
var cur, aft : pMycircqueue;
begin
  cur:=head;
  repeat
    aft:=cur^.next;
    dispose(cur);
    cur:=aft;
  until cur=head;
end;

We must use two variables, cur and aft. In a simple queue, we can look for the nil pointer as the last item. Now we cannot. Then, we look the next pointer value of head. That's the last item. Pretty bit tricky, eh? Delete part is also as tricky. Don't forget to check the special conditions too. Watch this:

procedure delete (var head : pMycircqueue; whattodel : pMycircqueue);
var bef, cur, aft : pMycircqueue;
begin
  cur:=whattodel;
  aft:=cur^.next;
  if cur=aft then    { The only item in the list }
  begin
    dispose(cur); head:=nil; exit;
  end;

  { Search for the previous item }
  bef:=head;
  while bef^.next<>cur do bef:=bef^.next;

  { If it is head to be disposed, set head to the next item, avoiding crash }
  if cur=head then head:=aft;

  { The rest is normal }
  bef^.next:=aft;
  dispose(cur);
end;

Insertion path? It is the same as normal queue. So, you'd just modify it a bit and go! Wrapping it all together? See the main begin...end block of the simple queue of the last lesson. The same.

Circular stack? Well, it is pretty bit the same as circular queue. In circular queue diagram, items are arranged clockwisely. In circular stack we arrange things counter-clockwisely. You can use either circular list. It is the same. I leave it to you as exercise.

How about double circular list? It's pretty bit the same as double linked list but we try to make it circular. It is the same as circular queue and circular stack combined together.

Ahhhh! Finally, we came to the end of the lesson. Pretty lengthy, huh? Yeah! You finally made it! :-) OK, that's all for now. Shall we go to the quiz or the next lesson?

Where to go?

Back to main page
Back to Pascal Tutorial Lesson 2 contents
To the quiz
To Chapter 4 about tree and binary tree
My page of programming link
Contact me here