Linked lists

[Galois271]

Hi all,

I am a fairly new Java programmer, so I am confused a little by some
linked list implementations I've seen. In one book, the author uses 2
separate classes, one for the node and another to manipulate the
nodes, i.e. print, traverse, addNode, etc... The second book uses 2
classes, but the node class is a private inner class inside the class
to manipulate the nodes. The book I am using for a data structures
course uses just 1 class for the node and the methods to manipulate
the nodes. I tried asking my prof., but english is not his first
language, and I really can't understand him.

Does anyone know why the 3 different implementations? And, which one
is better, if that can be answered?

Thanks!

 

[Daniel Pitts]

Hi all,

I am a fairly new Java programmer, so I am confused a little by some
linked list implementations I've seen. In one book, the author uses 2
separate classes, one for the node and another to manipulate the
nodes, i.e. print, traverse, addNode, etc... The second book uses 2
classes, but the node class is a private inner class inside the class
to manipulate the nodes. The book I am using for a data structures
course uses just 1 class for the node and the methods to manipulate
the nodes. I tried asking my prof., but english is not his first
language, and I really can't understand him.

Does anyone know why the 3 different implementations? And, which one
is better, if that can be answered?

Thanks!

Those are just three different choices. I personally prefer the second
one (Private inner class), this is similar to the standard
java.util.LinkedList implementation.

It is a design choice, but the down side to both #1 and #3 is that they
leak implementation details. A user of the list probably doesn't care
that it even has Nodes, let alone how to connect/disconnect them. That
detail should be hidden from the class user.

 

[Mark Space]

Hi all,

I am a fairly new Java programmer, so I am confused a little by some
linked list implementations I've seen. In one book, the author uses 2
separate classes, one for the node and another to manipulate the
nodes, i.e. print, traverse, addNode, etc... The second book uses 2
classes, but the node class is a private inner class inside the class
to manipulate the nodes. The book I am using for a data structures
course uses just 1 class for the node and the methods to manipulate
the nodes.

Your book implementation is probably just a bit too simple, only an
example for beginners. The first and second examples you list before
that are probably better. As mentioned, it does depend on design.

For the most general sort of design, however, I'd add one more class: an
interface for LinkedList which can be implemented by another class.

List
^
/_\
|
|
LinkedList ---> Node
---> Node
---> Object

You might even go further and add an abstract class for implementing
other Lists.

Fortunately, someone thought of this already, and did the work for you.
You of course have to learn this stuff on your own for your
schoolwork, but it doesn't hurt to look at real working implementations
to get ideas from.

<http://java.sun.com/javase/6/docs/api/java/util/List.html>
<http://java.sun.com/javase/6/docs/api/java/util/AbstractList.html>

I tried asking my prof., but english is not his first
language, and I really can't understand him.

When you work in the real world, you might have co-workers or customers
who also are not native English speakers. It won't hurt to get used to
dealing with accents now.

 

[Joshua Cranmer]

Does anyone know why the 3 different implementations? And, which one
is better, if that can be answered?

Mostly a reiteration of what Patricia said, but I'll add my 2¢.

The three implementations come from three different ways of looking at a
linked list. The first sees a linked list as a collection of nodes
bundled into a list. The second sees it as a list, which happens to be
implemented as a collection of nodes. The third sees a list as a node
which links up to all the other nodes.

In the grand scheme of things, none of these is better than the others.
It all depends on the interface.

The second way is probably most common in practice. An interface (e.g.,
java.util.List) requires an ordered, sequential list; the fact that it
is via linked nodes is unimportant.

The third way is less common, but still rather common. An example here
is the DOM interfaces: each node explicitly knows its previous and next
siblings, as well as its parent and first and last children (among other
things). A document is nothing more than the root of this tree hierarchy
[1].

The first way is probably least common in practice, since it is an
uncomfortable middle ground between the other options: the part classes
can fully manipulate themselves in relation to others, but overarching
manipulation is in a separate class. For some strange reason, however,
it always seems to be the most common method found in textbooks.

I most commonly use the second and third types of implementations,
probably in roughly equal amounts.

 

[Tom Anderson]

I am a fairly new Java programmer, so I am confused a little by some
linked list implementations I've seen. In one book, the author uses 2
separate classes, one for the node and another to manipulate the nodes,
i.e. print, traverse, addNode, etc... The second book uses 2 classes,
but the node class is a private inner class inside the class to
manipulate the nodes. The book I am using for a data structures course
uses just 1 class for the node and the methods to manipulate the nodes.

The first two ways are basically the same - whether the node class is a
top-level class or an inner class doesn't really make any difference to
how it works.

The third way is different. The basic concepts are the same, but that
approach conflates the idea of list and node.

For most people, the first two approaches make more sense, but for some
people, the latter is more elegant and simple - the former are called
engineers, and the latter are computer scientists. Computer scientists are
people who spend too much time doing maths and not enough time writing
code, and their opinions are not to be trusted.

tom

 

[Joshua Cranmer]

I'm a computer science Ph.D. candidate with a bachelor's degree in
mathematics and a master's degree in CS. By any reasonable
classification I'm a computer scientist, and I have spent a significant
portion of my time thinking about mathematics.

Only a PhD candidate?

FWIW, I'm studying for a bachelor's in CS right now.

 

[Lew]

I am a fairly new Java programmer, so I am confused a little by some
linked list implementations I've seen. In one book, the author uses 2
separate classes, one for the node and another to manipulate the
nodes, i.e. [sic] print, traverse, addNode, etc... The second book uses 2
classes, but the node class is a private inner class inside the class
to manipulate the nodes. The book I am using for a data structures
course uses just 1 class for the node and the methods to manipulate
the nodes. I tried asking my prof., but english [sic] is not his first
language, and I really can't understand him.

Does anyone know why the 3 different implementations? And, which one
is better, if that can be answered?

Those are just three different choices. I personally prefer the second
one (Private inner class), this is similar to the standard
java.util.LinkedList implementation.

It is a design choice, but the down side to both #1 and #3 is that they
leak implementation details. A user of the list probably doesn't care
that it even has Nodes, let alone how to connect/disconnect them. That
detail should be hidden from the class user.

One can achieve similar opaqueness of implementation with a package-private
top-level class for Node, assuming that the Node class has no need for special
access to private details of the outer class.

There have been studies of programming process where some number (say, six) of
programming teams were given a particular programming assignment, and no two
ever come up with the same solution.

Rather than asking which one is better, it is more useful to ask what the
implications of each design choice are. For example, if the Node class is a
public class, then it cannot be replaced later. If there is only one class
that subsumes both the "node" concept and its manipulation, then one cannot so
easily separate out the functionality later. OTOH, it might be much easier to
incorporate into a larger project where such severability provides no benefit.

One relevant best practice is to figure out what client logic needs to see,
i.e., what methods will it use. Define an interface comprising just those
methods, and make only the interface's methods publicly accessible in its
implementing class(es). Details of whether there is a Node, whether it's
separate from the linked list implementation, whether it's a top-level class,
an inner class or a non-inner nested class, and what helper methods it might
provide should not matter to client code.

From the client's perspective, there is only the "linked list" type.

 

[Lew]

Computer scientists are people who spend too much time
doing maths and not enough time writing code, and
their opinions are not to be trusted.

This is one of those rare times when Tom was speaking from the wrong end.

While it's fun and perhaps funny to denigrate computer scientists as
impractical and out of touch with the art of programming, like most
stereotypes it's unnecessarily derogatory and generally far removed from the
truth.

In case you haven't noticed, Tom, Patricia is one of the wisest contributors
to this forum with almost always most pragmatic and useful advice. As an
exemplar of computer scientists, she provides strong evidence against your
shamefully prejudiced remarks.

 

[Mike Schilling]

One relevant best practice is to figure out what client logic needs
to see, i.e., what methods will it use. Define an interface
comprising just those methods, and make only the interface's methods
publicly accessible in its implementing class(es). Details of
whether there is a Node, whether it's separate from the linked list
implementation, whether it's a top-level class, an inner class or a
non-inner nested class, and what helper methods it might provide
should not matter to client code.
From the client's perspective, there is only the "linked list" type.

There are two major types, and the difference between them does affect
the client:

1. A linked list that can take any sort of object (e.g.
java.util.LinkedList)
2. A linked list that can only take objects which extend a specific
Node class

In general, type 1 implies that an object can be in multiple lists at
the same time (or in the same list at multiple positions), while type
2 won't allow that.

 

[Tom Anderson]

Tom Anderson wrote:
...
...

In that case, I had better stop writing articles here, in case my
untrustworthy opinions lead anyone astray.

Yeah, i'm keeping a close eye on you, Shanahan!

I'm a computer science Ph.D. candidate with a bachelor's degree in
mathematics and a master's degree in CS. By any reasonable
classification I'm a computer scientist, and I have spent a significant
portion of my time thinking about mathematics.

I'm sorry if anyone took offense at my, er, offensive comment. I certainly
didn't mean any. It was tongue-in-cheek, and as with any generalisation
about people it can't actually be true. I know plenty of computer
scientists who are extremely good at actually getting things done, so i'm
well aware that you're not all ivory-tower angel-counters.

Nonetheless, i do believe that there's a strong strain of aesthetics
within CS that has a very different idea of what's beautiful and good and
worthwhile to the idea that prevails in the fields and mines of the
software industry (and to which i'm implicitly attaching a sort of halo of
empirical validness). The kind of thinking that leads to this sort of
thing:

http://lambda-the-ultimate.org/node/3210

Which is pretty much guaranteed never to actually be any use to anyone.
Furthermore, i think this highly abstracted, mathematicised strain of
thinking has been dominant in CS for much of its history, and has led to a
lot of smart people putting all their efforts into things which from a
distance seem pretty pointless.

The result of this is that people who are heading for a career writing
code get an education which doesn't actually help them do that. This is
purely anecdotal, but i've often heard people in industry say that they
don't consider a CS degree any kind of preparation of a job writing code
(my currrent bosses say, only semi-jokingly, that they won't hire computer
scientists - we currently have people with degrees in maths, software
engineering, electronic engineering, architecture and biochemistry).
Indeed, i know of a university department that made its reputation by
specifically *not* being a CS department - it was part of the electrical
engineering faculty, and gave its students a much more craft-oriented
education.

I think the OP in the previous thread is being subjected to such a
non-practical education, at least through some of his reading materials,
and that's what i was kicking against.

Again, that's not to say that all people who call themselves computer
scientists are that way. There's a huge amount of very serious but also
useful work being done, on operating systems, databases, languages, all
sorts of things, in CS departments around the world (although perhaps more
so in the US than Europe).

I guess it all comes down to whether you think Alan Turing or Tom Kilburn
is the real father (or midwife, perhaps) of the computer. Alan Turing
wrote some brilliant papers about the idea of computability, but it was
Tom Kilburn who actually made the first program run.

tom

 

[Tom Anderson]

This is one of those rare times when Tom was speaking from the wrong end.

While it's fun and perhaps funny to denigrate computer scientists as
impractical and out of touch with the art of programming, like most
stereotypes it's unnecessarily derogatory and generally far removed from
the truth.

I've argued in my other post that it's actually not far from the truth. I
would concede that it's unnecessarily derogatory.

In case you haven't noticed, Tom, Patricia is one of the wisest
contributors to this forum with almost always most pragmatic and useful
advice.

Lew, i've been reading this group for almost half my life (on and off),
and i am well aware of Patricia's consistent and enduring contribution to
it - indeed, she's the only person active now who i recognise from my
previous era of reading it, and the quality of her thinking is unwavering.
I greatly respect and admire her.

As an exemplar of computer scientists, she provides strong evidence
against your shamefully prejudiced remarks.

Ah, but that's just it, i don't believe she is an exemplar of computer
scientists, or at least not of the breed of computer scientists that i'm
grumpy about - she has an immense amount of experience of getting her
hands dirty and actually doing things, as well as the training and
experience in formal thinking, which is what i think too many computer
scientists lack.

tom

 

[Martin Gregorie]

After the recent discussion involving the term "virtual memory," I'd say
that your concerns are well-founded. :-(

Judging by that discussion things may not have changed all that much in
the last 30 years.

When I was working in NYC back in the mid '70s I had an American
colleague with a bachelors in computer science. It turned out that the
school he'd been at had done little more than teach him how to write
COBOL plus the basics of commercial systems analysis.

 

[Stefan Ram]

I tend to be a little concerned about comments that might discourage a
young programmer from trying to learn the academic foundations of their
profession.

This is called a

http://en.wikipedia.org/wiki/Defence_mechanism

. When one learns of people with a higher level of education
than one's own level of education, one's

http://en.wikipedia.org/wiki/Self-esteem

is threatened. Possibly a

http://en.wikipedia.org/wiki/Cognitive_dissonance

is formed (»I know I am so very smart, but my formal level of
education actually is less than her's?«) . In order to resolve
this one uses the defence mechanism of devaluation

http://en.wikipedia.org/wiki/Idealization_and_devaluation

of people with a higher level of education (»They only know
theories, but can not get any practical work done, therefore I
can be glad I'm not one of them.«¹ or so.)

1) This sounds somewhat like:

»Alpha children wear grey. They work much harder than we
do, because they are so clever. I'm very glad I'm a Beta,
because I don't work so hard. And then we are much better
than the Gammas and Deltas. Gammas are stupid. They all
wear green, and Delta children wear khaki ...«

Aldous Huxley (1894-1963), Brave New World (1932).

 

[Stefan Ram]

Though one must really say that one can be a programmer without any
higher educational background.

Sounds like Peter Norvig:

»If you want, put in four years at a college (or more at a
graduate school). This will give you access to some jobs
that require credentials, and it will give you a deeper
understanding of the field, but if you don't enjoy school,
you can (with some dedication) get similar experience on
the job. In any case, book learning alone won't be enough.

"Computer science education cannot make anybody an expert
programmer any more than studying brushes and pigment can
make somebody an expert painter" says Eric Raymond, author
of The New Hacker's Dictionary. One of the best
programmers I ever hired had only a High School degree;
he's produced a lot of great software, has his own news
group, and made enough in stock options to buy his own
nightclub.«

http://norvig.com/21-days.html

 

[Lew]

Sounds like Peter Norvig:

»If you want, put in four years at a college (or more at a
graduate school). This will give you access to some jobs
that require credentials, and it will give you a deeper
understanding of the field, but if you don't enjoy school,
you can (with some dedication) get similar experience on
the job. In any case, book learning alone won't be enough.

"Computer science education cannot make anybody an expert
programmer any more than studying brushes and pigment can
make somebody an expert painter" says Eric Raymond, author
of The New Hacker's Dictionary. One of the best
programmers I ever hired had only a High School degree;
he's produced a lot of great software, has his own news
group, and made enough in stock options to buy his own
nightclub.«

http://norvig.com/21-days.html

The best artists go to art school, or at least take art classes. The best
film makers go to film school, or at least take classes in it. The best
musicians go to music school, or at least take classes in it. The best
football players go to college and are on the college football team. The best
business people go to business school, or at least take classes in it. The
best actors go to acting school, or at least take classes in it. The best
engineers go to engineering school, or at least take classes in it. The best
practitioners in all skilled professions take continuing-education classes,
seminars, private lessons or some form of education in their craft, and spend
massive amounts of time studying it on their own.

This anti-academic sentiment is misplaced and harmful to practitioners.

 

[Martin Gregorie]

There are a lot of people that get through university and get a
Bachelors degree without learning anything ...

I wasn't clear enough: sorry. My colleague was pretty bright, a useful
programmer and was obviously going to be very good with more experience.
He didn't learn more than COBOL programming and some systems analysis
because that was all that was on offer at his school.

They didn't reach any of the theory or design principles that I'd expect
in a CS degree. They didn't teach any other languages than COBOL either.
In short, what he'd been taught was little more than what I'd have
expected from a polytech COBOL programming course.

Though one must really say that one can be a programmer without any
higher educational background.

Indeed. I do have a degree, but its in physical chemistry. My university
didn't offer Computer Science degrees in the mid 60s.

The only student-accessible computer was an Elliott 503 (a scientific
machine rather than a commercial one) that belonged to the Applied Maths
department. I learnt Algol 60 to crunch through a lot of messy data from
a multi-channel analyser for my thesis, though an IBM 1130 arrived a year
or two after I'd graduated.

The CS background .../... helps you to see patterns in problems.
Especially it helps you to see what kind of problems are possible to
solve and where you need to do tricks and be satisfied with an
approximation.
Agreed.

My oppinion is: Don't expect any programming ability from someone with a
degree in CS.

One of the best managers I had the fortune to work for was a really
bright guy (1st from Oxford in Maths), top class system designer and also
a very good manager with exactly the right ability to delegate to the
appropriate person.

His approach to hiring was unique: he always said he didn't care what a
new graduate knew or had studied: that was irrelevant. What he wanted to
hire was brain power and the ability to think, learn and solve problems.

 

[Martin Gregorie]

This anti-academic sentiment is misplaced and harmful to practitioners.

I think its grown up because so many IT people have learned on the job
and don't have academic qualifications. In addition theres no requirement
to be chartered, making IT unlike any other engineering discipline.
Additionally, employers don't look for professional qualifications: I'm a
member of the BCS but have never, ever been asked if I was a member in
any job or contract interview.

In view of the above its hardly surprising that there's an anti-academc
sentiment. Its a defence mechanism used by the many programmers who don't/
won't bother to educate themselves except on company time.

 

[Lars Enderin]

Indeed. I do have a degree, but its in physical chemistry. My university
didn't offer Computer Science degrees in the mid 60s.

In the sixties I met a few chemists who had become programmers. Maybe
chemists and programmers have similar mindsets.

 

[Arved Sandstrom]

On Sat, 14 Feb 2009 21:05:03 +0100, Christian wrote:

[ SNIP ]

My oppinion is: Don't expect any programming ability from someone with a
degree in CS. Though without a degree in CS the highest ranks of
understanding of the things you do are simply closed before you... There
are things you just can't or better won't learn in practice. There are
datastructures/algorithms that solve some problems that you just can't
reinvent on the fly. You might never need them ... or may be you just
will use something slower that might or might not fit your needs... in
the end you end up optimizing by shifting around simple lines of code to
exchange one O(n) solution against another ..while some theory has a
O(log n)-solution to your problem.

Christian

I absolutely agree with the first sentence here. I wish the rest of the
quote was true more often than it really is. In practise, the "highest
ranks of understanding" of data structures and algorithms (and everything
else that one would expect a CS degree to give you an education on) seems
to be missing for a large percentage of programmers (the majority)
regardless of whether they have a CS degree or not.

When I started programming as a career I recognized eventually that my
background in data structures and algorithms was deficient. After all,
you don't learn that in physics or engineering. So I went out and bought,
and studied, texts like Sedgewick's "Algorithms in C". Having done that
(and I'm still doing it), it's been disconcerting over the years to find
out that I know more about CS basics than many recent CS graduates do.
Makes me wonder what the hell they get taught. Well, actually, I have an
inkling...a number of CS grads I've recently talked to seem to know quite
a lot about data mining...even if they couldn't have this same
conversation we've been having about linked lists. I guess if there was a
data mining project somewhere they'd be just the ticket.

AHS

 

[Arved Sandstrom]

I think its grown up because so many IT people have learned on the job
and don't have academic qualifications. In addition theres no
requirement to be chartered, making IT unlike any other engineering
discipline. Additionally, employers don't look for professional
qualifications: I'm a member of the BCS but have never, ever been asked
if I was a member in any job or contract interview.

In view of the above its hardly surprising that there's an anti-academc
sentiment. Its a defence mechanism used by the many programmers who
don't/ won't bother to educate themselves except on company time.

I don't buy that. Probably about a third of the programmers I have worked
with over the years have a CS background. They are, as a group, neither
particularly better nor particularly worse than non-CS graduates, as
programmers. I haven't noticed any difference at all between CS grads and
non-CS grads amongst the ranks of those programmers who actually give a
damn enough to pursue continuing professional education. If there was any
kind of bias along the lines of what you suggest, I'd expect to see CS
grads being more likely to study on their own time, but they're no
different than anyone else.

Furthermore, the kind of continuing education one needs as a professional
programmer has very little to do with academia. So I don't see why
there'd be a bias against it, since higher CS education is essentially
irrelevant for most working programmers. The kind of professional
development that actually is useful to programmers is largely non-
academic, and is easily accessible outside the academic environment. Not
that it matters - most programmers (CS background or not) tend to leave
programming to company time, as you suggested.

Myself I follow nearly a dozen technical mailing lists, half a dozen
carefully chosen programming newsgroups, and frequent some high-value
programming blogs. I may have more than superficial knowledge of only a
small percentage of what I read about, but at least I've heard of what's
out there. I also keep up on emerging standards and work in the areas
that pertain to what I usually work on, or may work on. As a result I can
usually find out in the course of just a few casual conversations whether
another programmer does any professional development, and I can always
find out if they are doing any professional development in the areas that
pertain to us at work.

Personally I assign some blame to the languages we use nowadays. I had to
tutor a co-worker a few weeks ago on how to implement the compare()
method for an anonymous Comparator, because they stumbled across a
Collections.sort() in existing code and were required to modify it. It
took some explaining before I could get across the point that there was
an actual sort algorithm being called, let alone get to explaining what
the compare() method was there for. The only reason this came up at all
is because the objects being compared weren't simple...I suspect the
programmer in question had already used Collections.sort() many times on
simple objects and never had to understand what he was doing. I started
talking mergesort and quicksort to him too, but his eyes glazed over, and
I quit that effort.

I might add - the gentleman in question has a CS degree...

AHS