tutorial on linked list

a lot of students studying advanced C++ have some trouble understanding the concept of linked list. this is either due to lack of imagination, or lack of understanding of fundamental operations. but essentially, the problem arises due to students studying basic C++ tend to memorize topics rather than trying to build a deep understanding of the same.

you wouldn't think of memorizing addition, would you? addition is a primitive operation that everyone understands to the bone. a+b refers to the outcome of someone giving you 'b' dollars when you already have 'a' dollars in your purse, or vice versa (i think that concepts are much clearer when money is involved :D). the "vice versa" becomes really important since a+b=b+a which is the commutative property. similarily, it doesn't matter in which order you get the money (a+b)+c = a+(b+c). this is the associative property.

anyways, so much so for kindergarten math. coming to linked lists now. before understanding linked lists, it is necessary to understand pointers. so please refer to my post on pointers if you think that pointers are nasty things planted on earth by the evil cybermen from outer universe. (i'm watching too much dr. who nowadays!)

(once you are happy with pointers, proceed)

a linked list is a linked collection of items of the same type such that first value knows where is the second value stored, the second value knows about the third value and so on. for example, a list of students can be encoded as a linked list (LL). If I want to display the list of students, I need to start from somewhere. Thus, the location of the first student, (to whom no one points - so sad) is important and should be stored somewhere. If the location of the first student is lost, then that of the second student is also lost (since the first student has that info) and so on.

A simple list looks like the following figure. It simply contains a set of integers, not stored in sorted order.

You can view this as ID of students standing in a queue. The person at the front of the queue has ID 8, the next one 3 and so on. It is useful to divide each item (from now on referred to as "node") as containing two parts:

1. data

2. link to next node

Thus we come to our first C++ definition, that of a node. A node is an abstract data type containing value and address of next node. From the discussion on pointers, what contains address of a node -- pointer to a node :) So,

struct node

{

int data; //this can be int, double, even another structure object
node* next;
};

please be clear that the node DOES NOT contain another node, it simply contains address of another node.

Since it's important to have address of the first node somewhere, we call it "head", or "first", or "top" or "front" depending on the situation. I call it head over here. This is implemented as:

node* head;

head = new node;//allocate memory for a node and store it's location in head

head->data=8 //data part of node to which head points becomes 8

head->next=NULL //right now, head does not contain any address, thus it's the only node

If you want to add another node

node* temp=new node;

temp->data=3;

temp->next=NULL;

head->next=temp;

Sorry, the above image is a bit too small, but if you click on it, it will open in a new window/tab and is viewable.

I can also move the "head" around so that the first item changes. This happens when the first person in the queue (head) is served and now is no longer a part of the queue. Look at the following statement:

head=head->next;

the right hand side of this statement (head->next) contains address of temp (87)



so it simplifies to head=87

thus head now contains address 87 rather than the old address 84.
thus head now points to the second node.
thus the second node now becomes the first node :)


what happens to the old first node?!?!?! it is still in the memory. so it you want to remove it from memory, you use:


node* old=head //old points to same location as head (84)
head=head->next;
delete old //delete node contained at address inside old (84)


------------------------------------


Now let us look at some more useful operations on lists.


Operation 1: To check if list is empty or not?


The list is empty if head contains no address. That is, head is NULL. Which also tells us that when we create a list, we should assign NULL to head. Hence, the correct way to initialize a list is:


node* head=NULL;

bool isEmpty(node* head)
{
if(head==NULL)
return true;
else
return false;
}


---------------------------------------

Operation 2: To insert an item at the front of the list

Assuming that the list is containing a set of items where order isn't important. We pass the node pointer by reference (that is the actual head is modified rather than a duplicate copy of head being passed to the function).


We first create a node by reserving memory space.
We contain address of old head in node temp.
We move head so that head now contains address of temp.


void insert(node* &head, int item)
{
node* temp=new node;
temp->data=item;
temp->next=head;
head=temp;
}


Even if head was NULL (inserting item into an empty list), the statement temp->next=head means that temp->next contains NULL which is also correct :)


-----------------------------------


Operation 3: Deleting item from front of list:


void delete(node* &head)
{
if(head!=NULL)
{
node* temp=head;
head=head->next;
delete temp;
}
//if head is already NULL, it means nothing remaining to delete
}


-------------------------------


Operation 4: Traverse through the list (go through the list for some xyz purpose)


void traverse(node* head) //not passing by reference since I don't want to modify actual head
{
while(head)
{
cout<data<<" ";
head=head->next; //please remember the actual head is not modified since a duplicate
//pointer in memory is there, that contains same address as head
}
}


For those of you, who still are freaked out by me modifying "head" in the function, use the following function varient:


void traverse(node* head) //not passing by reference since I don't want to modify actual head
{
node* current=head;
while(current)
{
cout<data<<" ";
current=current->next;
}
}


------------------


Tutorial part 2 coming soon to a cinema near you!


cheers
gaurav