[algogeeks] Re: use of sentinel in linked list

[karthikeya s]

@don,@gene: i know the pros of using it.but pbm occurs when we see
pbm

LIST-SEARCH(l,k)
x <- next[nil[l]] //nil[l] denotes the
sentinel node
while x != nil[l] and key[x] != k
x <- next[x]
return x

here to eliminate extra comparison (x != nil[l] ) in while loop ,
we will use sentinel and will put value to search in data field of
sentinel...but if value to be searched is not found in ll then it will
return the address of sentinel which is non-null. So how will i diff.
whether value is found or not except to remember the address of
sentinel.

-- 
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.

[algogeeks] Re: use of sentinel in linked list

[Gene]

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  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  wrote:
>
>
>
>
>
>
>
> > How to implement a linked list using sentineli 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.

[algogeeks] Re: use of sentinel in linked list

[Don]

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  wrote:
> How to implement a linked list using sentineli 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.