Linking at the beginning is easier.
Linking at the end either requires traversing to the end of the list, then linking to it.
Or, more efficient, have an external end pointer in addition to the start pointer:
This time we need an if clause, because the first element needs to be treated differently.
Last edited by MadeInGermany; 02-27-2013 at 02:02 PM..
Reason: Forgot to update the end pointer
i have a linked list set up like
typedef struct client_list {
char *client_name;
int client_socket_fd;
struct client_list *next;
} client;
client *client_list=NULL;
before adding to the list i check if it already exists, only if it does not then i add
if (client_list==NULL... (1 Reply)
can someone provide an example of a struct linked list, where it has strings as its values, and then how do I check if a specific string (say called buffer) exists in the list of structs?
i dont understand how to make a copy of it to check with
this is what i have
... (0 Replies)
Hi, I am programming in kernel, and I want to use a double linked list that holds infos that every process could access and modify THIS list. So, I suppose it is a 'global' variable since every process(thread) can reach it, I am wondering where to put it? by changing some of the kernel files? (1 Reply)
Program to reverse a linked list by traversing only once. (1 Reply)
Discussion started by: VSSajjan
1 Replies
LEARN ABOUT DEBIAN
tree::node
Node(3pm) User Contributed Perl Documentation Node(3pm)NAME
Tree::RedBlack::Node - Node class for Perl implementation of Red/Black tree
SYNOPSIS
use Tree::RedBlack; my $t = new Tree::RedBlack; $t->insert(3, 'dog'); my $node = $t->node(3); $animal = $node->val;
DESCRIPTION
A Tree::RedBlack::Node object supports the following methods:
key ()
Key of the node. This is what the nodes are sorted by in the tree.
val ($)
Value of the node. Can be any perl scalar, so it could be a hash-ref, f'rinstance. This can be set directly.
color ()
Color of the node. 1 for "red", 0 or undef for "black".
parent ()
Parent node of this one. Returns undef for root node.
left ()
Left child node of this one. Returns undef for leaf nodes.
right ()
Right child node of this one. Returns undef for leaf nodes.
min ()
Returns the node with the minimal key starting from this node.
max ()
Returns the node with the maximal key starting from this node.
successor ()
Returns the node with the smallest key larger than this node's key, or this node if it is the node with the maximal key.
predecessor ()
Similar to successor. WARNING: NOT YET IMPLEMENTED!!
You can use these methods to write utility routines for actions on red/black trees. For instance, here's a routine which writes a tree out
to disk, putting the byte offsets of the left and right child records in the record for each node.
sub dump {
my($node, $fh) = @_;
my($left, $right);
my $pos = tell $fh;
print $fh $node->color ? 'R' : 'B';
seek($fh, 8, 1);
print $fh $node->val;
if ($node->left) {
$left = dump($node->left,$fh);
}
if ($node->right) {
$right = dump($node->right,$fh);
}
my $end = tell $fh;
seek($fh, $pos+1, 0);
print $fh pack('NN', $left, $right);
seek($fh, $end, 0);
$pos;
}
You would call it like this:
my $t = new Tree::RedBlack;
...
open(FILE, ">tree.dump");
dump($t->root,*FILE);
close FILE;
As another example, here's a simple routine to print a human-readable dump of the tree:
sub pretty_print {
my($node, $fh, $lvl) = @_;
if ($node->right) {
pretty_print($node->right, $fh, $lvl+1);
}
print $fh ' 'x($lvl*3),'[', $node->color ? 'R' : 'B', ']', $node->key, "
";
if ($node->left) {
pretty_print($this->left, $fh, $lvl+1);
}
}
A cleaner way of doing this kind of thing is probably to allow sub-classing of Tree::RedBlack::Node, and then allow the Tree::RedBlack
constructor to take an argument saying what class of node it should be made up out of. Hmmm...
AUTHOR
Benjamin Holzman <bholzman@earthlink.net>
SEE ALSO
Tree::RedBlack
perl v5.10.0 2008-07-31 Node(3pm)