What is the purpose of using NIL for representing null nodes?

Problem Detail: 

In my Algorithms and Data Structures course, professors, slides and the book (Introduction to Algorithms, 3rd edition) have been using the word NIL to denote for example a child of a node (in a tree) that does not exist.

Once, during a lecture, instead of saying NIL, my classmate said null, and the professor corrected him, and I don't understand why professors emphasise this word.

Is there a reason why people uses the word NIL instead of null, or none, or any other word? Does NIL has some particular meaning that the other do not have? Is there some historical reason?

Note that I have seen also a few places around the web where the word null (for example) was used instead of NIL, but usually this last one is used.

Asked By : nbro

Answered By : Gilles

As far as I'm concerned, null, nil, none and nothing are common names for the same concept: a value which represents the "absence of a value", and which is present in many different types (called nullable types). This value is typically used where a value is normally present, but may be omitted, for example an optional parameter. Different programming languages implement this differently, and some languages might not have any such concept. In languages with pointers, it's a null pointer. In many object-oriented languages, null is not an object: calling any method on it is an error. To give a few examples:

• In Lisp, nil is commonly used to stand for the absence of a value. Unlike most other languages, nil has structure — it's a symbol whose name is "NIL". It's also the empty list (because a list should be a cons cell, but sometimes there is no cons cell because the list is empty). Whether it's implemented by a null pointer under the hood, or as a symbol like any other, is implementation-dependent.
• In Pascal, nil is a pointer value (valid in any pointer type) that may not be dereferenced.
• In C and C++, any pointer type includes a NULL value which is distinct from any pointer to a valid object.
• In Smalltalk, nil is an object with no method defined.
• In Java and in C#, null is a value of any object type. Any attempt to access a field or method of null triggers an exception.
• In Perl, undef is distinct from any other scalar value and used throughout the language and library to indicate the absence of a "real" value.
• In Python, None is distinct from any other value and used throughout the language and library to indicate the absence of a "real" value.
• In ML (SML, OCaml), None is a value of the any type in the type scheme 'a option, which contains None and Some x for any x of type 'a.
• In Haskell, the similar concept uses the names Nothing and Just x for the values and Maybe a for the type.

In algorithm presentations, which name is used tends to stem from the background of the presenter or the language that is used in code examples.

In semantics presentations, different names may be used to refer to e.g. the NULL identifier which denotes a pointer constant in the language, and the $\mathsf{nil}$ value in the semantics. I don't think there's any standard naming scheme, and some presentations leave it up to a font difference, or don't go into concrete syntax at all.

It's possible that your lecturer wants to use the word null for a null pointer constant in the programming language used in the course (Java or C#?), and NIL to denote the absence of a node in some data structures, which may or may not be implemented as a null pointer constant (for example, as seen above, in Lisp, NIL is often not implemented as a null pointer). This distinction would be relevant when discussing implementation techniques for data structures. When discussing the data structures themselves, the null-pointer-constant concept is irrelevant, only the not-equal-to-any-other-value concept matters.

There is no standard naming scheme. Another lecturer or textbook could use different names.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44422