What are you using the sentinel for? A marker for the end of the list?
A common way to implement a linked list is to use a sentinal as the
head of a circularly linked list.
Thus, an empty list is a pointer to the sentinal which is linked to
itsself.
The advantage is that there are fewer special cases to consider when
you need to insert or delete an item from the list.
For example, to delete an item from the list, you don't need a special
case to handle deleting the first item.
For instance:
class node
{
public:
int data;
struct node *next;
};
class list
{
public:
list() // Construct an empty list
{
_head = new node;
_head->next = _head;
_head->data = 0;
}
bool isEmpty() { return _head == _head->next; }
void insert(int n) // Insert n at head of list
{
node *tmp = new node;
tmp->data = n;
tmp->next = _head->next;
_head->next = tmp;
}
void delete(int n) // Delete first node with value n
{
node *p;
for(p = _head; p != _head; p = p->next)
{
if (p->next->data == n)
{
node *tmp = p->next;
p->next = tmp->next;
delete tmp;
break;
}
}
etc...
}
private:
node *_head;
};
On Feb 21, 12:00 pm, karthikeya s <karthikeya.a...@gmail.com> wrote:
> How to implement a linked list using sentinel....i mean sentinel will
> be having some non-null address.....then how would u identify it
> except remembering the address.....
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
