Exactly. The other trick is when maintaining a list in ascending
sorted order, to give the sentinel a key of "infinite". This way you
need not check for the end of list at all. The key comparison will
always stop before the last element. I vaguely recall Wirth uses this
example in his book Algorithms + Data Structures = Programs, but I
haven't picked it up for years, so this could be false.
On Feb 21, 2:00 pm, Don <dondod...@gmail.com> wrote:
> 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.
