I was asked to write a linked list in C++ at a job interview today. Immediately I started working on classes and methods and whatnot, but I didn’t have enough time to get it fully working. I gave a poor impression and had to explain inserting into and deleting from linked lists on paper. Afterwards, I realized my interviewer didn’t want a heavy object-oriented linked list. He wanted to make sure I knew the concept (and pointers in C++). A simple struct node and a couple of loops would have done the job.
When I got home, I was compelled to finish what I started. I made the linked list anyway to prove to myself I could do it. Here’s the Xcode project and everything else that’s necessary. Obviously you don’t need Xcode. Compiling main.cpp should do the trick on pretty much any system.
The linked list only has an AddToFront, DeleteFromFront, Next, and GoBackToFront methods, since that’s about all you can do with a singly linked list. I used templates so the thing could actually be useful if not for the total lack of documentation and testing. (Not to mention the fact that everyone writes one of these.) It does have an educational purpose though: Since I made it spit output when nodes are added and deleted, you can see how the destructor is implicitly called once the test object is out of scope. (In this case it’s when the program ends.) Writing this really took me back to my data structures class. I guess I’ve become soft since most languages come with nice data structures.
Kevin Lindeman | 16-Dec-07 at 4:18 pm | Permalink
I know this post is a bit old now, but I felt like I should comment on this. You can do way more than just that with a singly linked list. It isn’t even that hard. It is easy to do things such as insert and remove in the middle of the list. The only reason you couldn’t is if you were improperly taught linked lists by just letting you use a doubly-linked list, which is unnecessary in most cases.
I can only think of two reasons for for needing a doubly-linked list is if you have a goToIndex(int i), and you want it to be fast and start from either end of the list depending on if the index is after the halfway point or not. Or if you want some sort of Java style Iterator where you want to be able to iterate using next() and then remove() would remove the last value given to you using next().
Just thought I should post that your class doesn’t exactly do “about all you can with a singly linked list”
Geoff Greer | 22-Dec-07 at 9:04 pm | Permalink
I guess I should have been more descriptive. You can do a lot with singly linked lists, but seeking to a certain element, removing an arbitrary element, etc, are O(n) or higher. There are much better data structures if you’re going to be doing those operations.